Reconstructing Partial Orders from Linear Extensions
Proceso L. Fernandez, Lenwood S. Heath, Naren Ramakrishnan, John R. Paul, C. Vergara · 2006
Reconstructing system dynamics from sequential data traces is an important algorithmic challenge with applications in computational neuroscience, systems biology, paleontology, and physical plant engineering. Here, we formalize a key computational task in network reconstruction, namely recovering complex order-theoretic constraints among the system variables underlying a given dataset. Specifically, we focus on the problem of reconstructing partial orders (posets) from their linear extensions. We discuss the theoretical complexity of this problem, a general framework to pose and study various inference tasks, and sketch algorithmic results for mining restricted classes of posets.