Reconstructing the Temporal Progression of Biological Data Using Cluster Spanning Trees

Identifying the temporal progression of a set of biological samples is crucial for comprehending the dynamics of the underlying molecular interactions. It is often also a basic step in data denoising and synchronization. Finally, identifying the progression order is crucial for problems like cell lineage identification, disease progression, tumor classification, and epidemiology and thus impacts the spectrum of disciplines spanning basic biology, drug discovery, and public health. Current methods that attempt solving this problem, face difficulty when it is necessary to factor-in complex relationships within the data, such as grouping, partial ordering or bifurcating or multifurcating progressions. We propose the notion of cluster spanning trees (CST) that can model both linear as well as the aforementioned complex progression relationships in temporally evolving data. Through a number of experimental investigations involving synthetic data sets as well as data sets from the cell cycle, cellular differentiation, phenotypic screening, and genetic variation, we show that the proposed CST approach outperforms existing methods in reconstructing the temporal progression of the data.