CAPITAL – alignment of single-cell trajectory trees

Global alignment of complex pseudotime trajectories between different single-cell RNA-seq datasets is challenging, as existing tools mainly focus on linear alignment of single-cell trajectories. Osaka University researchers have developed CAPITAL (comparative analysis of pseudotime trajectory inference with tree alignment), a method for comparing single-cell trajectories with tree alignment whereby branching trajectories can be automatically compared. Computational tests on synthetic datasets and authentic bone marrow cells datasets indicate that CAPITAL has achieved accurate and robust alignments of trajectory trees, revealing various gene expression dynamics including gene-gene correlation conservation between different species.

Overview of CAPITAL algorithm

a From an expression matrix of each dataset, a nearest neighbor graph is constructed where cells and their expression-based similarities are represented as vertices and weighted edges, respectively, and then clustered with community detection. Next, a centroid in each cluster is calculated to infer a trajectory of clusters by computing the minimum spanning tree. Finally, a tree alignment of trajectories of clusters is obtained by aligning one minimum spanning tree with the other across different datasets on the basis of a dynamic programming algorithm (“Methods”). b When a pair of aligned paths from the trajectory cluster alignment is chosen, all single cells are recovered with each labeled by the corresponding cluster, and ordered by diffusion pseudotime in each dataset. Linear alignment with dynamic time warping is then performed for a set of genes to investigate the dynamic relationship among single cells for those genes along the pseudotime.