Computational comparison of developmental cell lineage trees by alignments

Meng Yuan, Xujiang Yang, Jinghua Lin, Xiaolong Cao, Feng Chen, Xiaoyu Zhang, Zizhang Li, Guifeng Zheng, Xueqin Wang, Xiaoshu Chen, Jian‐Rong YangbioRxiv 2019 · DOI

TL;DR

This paper introduces DELTA, a novel computational framework for aligning developmental cell lineage trees (CLTs). DELTA enables the comparison of CLTs, much like sequence alignment for DNA, opening new avenues for understanding developmental programs, gene function, and evolutionary relationships between cell types.

What Problem Does This Paper Address?

Multicellular organisms develop from a single cell through a complex series of divisions and differentiations, meticulously recorded in a cell lineage tree (CLT). These trees are crucial for understanding fundamental biological questions, from developmental robustness to disease origins. However, while experimental techniques for generating CLTs have advanced significantly, a standardized computational framework for comparing them has been lacking. This gap hinders our ability to identify similarities between developmental programs, understand the impact of genetic mutations, and trace the evolutionary history of cell types across different species.

Methods

The core contribution of this paper is the Developmental Cell Lineage Tree Alignment (DELTA) algorithm. DELTA treats CLTs as structured entities and employs a dynamic programming approach, analogous to sequence alignment algorithms like Needleman-Wunsch and Smith-Waterman. Key aspects of DELTA include:

  • Homeomorphic Sub-CLT Identification: DELTA searches for similar subtrees (sub-CLTs) within two lineage trees, assuming that similar developmental programs lead to similar sub-CLTs.
  • Global and Local Alignment: DELTA supports both global alignment (aligning entire trees) and local alignment (finding the best matching sub-CLTs).
  • Scoring Matrix: A customizable scoring matrix defines the similarity between different cell types, allowing for flexibility in how cell types are defined and compared.
  • Pruning Cost: A pruning cost penalizes the removal of sub-CLTs, balancing the alignment score against the complexity of the alignment.
  • Statistical Significance: DELTA estimates the statistical significance of alignments by comparing them to alignments of pseudo-CLTs generated by random permutations.
  • ggVITA R Package: The authors developed an R package for visualizing DELTA alignments.

Datasets

The authors evaluated DELTA using:

  • Simulated CLTs: Generated using a previously published model that incorporates gene regulatory networks and epigenetic states. These simulations were used to test DELTA's ability to identify developmental similarities under various conditions, including perturbations like cell loss and non-autonomous expression.
  • Real CLTs from C. elegans: The well-characterized embryonic cell lineage of Caenorhabditis elegans was used for validation.
  • EPIC Database: This database provided gene expression data for C. elegans cells during embryonic development, used to assess expression similarities between aligned cells.
  • Digital Development Database: This database contains CLT data for C. elegans strains with individual gene knockouts, enabling the study of phenotypic changes in CLTs due to genetic alterations.
  • Real CLTs from Pellioditis marina: CLTs from this nematode were used to test DELTA's ability to find evolutionary correspondences between cell types across species with non-uniformly defined cell types.

Key Insights and Ideas

  • CLT Alignment as a Foundational Tool: DELTA establishes a computational foundation for comparative CLT analysis, akin to how sequence alignment revolutionized genomics. This opens the door to systematic, large-scale studies of lineage data.
  • Developmental Programs Leave Similar Signatures: The core assumption that similar developmental programs result in similar sub-CLTs is validated, allowing DELTA to identify these resemblances.
  • DELTA Bridges Genotype and Phenotype: The algorithm can link CLT phenotypes (observed lineage patterns) to underlying genetic mechanisms (gene knockouts), providing insights into gene function and evolutionary relationships.
  • Evolutionary Correspondence of Cell Types: DELTA can uncover evolutionary relationships between cell types across species, even when cell type definitions are not uniform, by optimizing a scoring matrix.

Key Results

  • Identification of Developmental Similarities: DELTA successfully identified highly similar sub-CLTs in simulated and real data, including bilaterally symmetric lineage pairs in C. elegans.
  • Detection of Homeotic Cell Fate Transformations: DELTA accurately identified known homeotic cell fate transformations in C. elegans mutants and discovered novel ones.
  • Quantifying Gene Functional Importance: DELTA scores between wildtype and knockout CLTs correlated with the evolutionary rate (dN/dS) of deleted genes, suggesting that DELTA can quantify the phenotypic impact of gene deletions and infer gene functional importance.
  • Revealing Functional Relationships Between Genes: DELTA analysis of knockout strains revealed that genes whose deletions result in similar CLT phenotypes are more likely to be functionally related, supported by enrichment for experimentally determined interactions.
  • Evolutionary Cell Type Mapping: DELTA optimized a scoring matrix to align CLTs from C. elegans and P. marina, revealing biologically plausible correspondences between cell types, such as "Muscle" in C. elegans mapping to "Muscle" in P. marina.

Limitations and Future Work

  • Parameter Sensitivity: DELTA's results are sensitive to the choice of scoring matrix and pruning cost. While the authors used biologically informed parameters, objective estimation of their optimality is challenging and requires more CLT data.
  • Qualitative vs. Quantitative Cell Types: Currently, DELTA considers qualitative cell types or epigenetic states. Future work could extend DELTA to handle quantitative cell type definitions derived from single-cell transcriptomics.
  • Ignoring Cell Cycle Duration: The current study did not incorporate cell cycle duration, although it did not prevent the discovery of developmental similarities. Future improvements could allow for cell cycle duration adjustment in DELTA.
  • Data Quality Issues: Experimental CLTs are often incomplete due to cell losses. DELTA shows robustness to cell loss, but more data could further alleviate this limitation, similar to how sequence alignment handles short reads.
  • Potential Applications: The authors suggest DELTA's applicability to assessing developmental repeatability (e.g., in iPS cells), bridging genotype-phenotype mapping across scales, and quantitatively answering questions about autonomous vs. regulatory development.

Summary updated

Abstract

ABSTRACT The developmental cell lineage tree, which records every cell division event and the terminal developmental state of each single cell, is one of the most important traits of multicellular organisms, as well as key to many significant unresolved questions in biology. Recent technological breakthroughs are paving the way for direct determination of cell lineage trees, yet a general framework for the computational analysis of lineage trees, in particular an algorithm to compare two lineage trees, is still lacking. Based on previous findings that the same developmental program can be invoked by different cells on the lineage tree to produce highly similar subtrees, we designed D evelopmental C e ll L ineage T ree A lignment (DELTA), an algorithm that exhaustively searches for lineage trees with phenotypic resemblance in lineal organization of terminal cells, meanwhile resolving detailed correspondence between individual cells. Using simulated and nematode lineage trees, we demonstrated DELTA’s capability of revealing similarities of developmental programs by lineal resemblances. Moreover, DELTA successfully identifies gene deletion-triggered homeotic cell fate transformations, reveals functional relationship between mutants by quantifying their lineal similarities, and finds the evolutionary correspondence between cell types defined non-uniformly for different species. DELTA establishes novel foundation for comparative study of lineage trees, much like sequence alignment algorithm for biological sequences, and along with the increase of lineage tree data, will likely bring unique insights for the myriads of important questions surrounding cell lineage trees.
BibTeX
@misc{yuan2019computational,
  author = {Meng Yuan and Xujiang Yang and Jinghua Lin and Xiaolong Cao and Feng Chen and Xiaoyu Zhang and Zizhang Li and Guifeng Zheng and Xueqin Wang and Xiaoshu Chen and Jian‐Rong Yang},
  title = {{Computational comparison of developmental cell lineage trees by alignments}},
  year = {2019},
  doi = {10.1101/577809},
  howpublished = {bioRxiv},
}
Figure