Machine Learning Based Lineage Tree Reconstruction Improved with Knowledge of Higher Level Relationships Between Cells and Genomic Barcodes

Overview

Journal NAR Genom Bioinform

Publisher Oxford University Press

Specialty Biology

Date 2023 Aug 23

PMID 37608801

Authors

Alisa Prusokiene

Augustinas Prusokas

Renata Retkute

Affiliations

Soon will be listed here.

Abstract

Tracking cells as they divide and progress through differentiation is a fundamental step in understanding many biological processes, such as the development of organisms and progression of diseases. In this study, we investigate a machine learning approach to reconstruct lineage trees in experimental systems based on mutating synthetic genomic barcodes. We refine previously proposed methodology by embedding information of higher level relationships between cells and single-cell barcode values into a feature space. We test performance of the algorithm on shallow trees (up to 100 cells) and deep trees (up to 10 000 cells). Our proposed algorithm can improve tree reconstruction accuracy in comparison to reconstructions based on a maximum parsimony method, but this comes at a higher computational time requirement.

Citing Articles

A Bayesian phylodynamic inference framework for single-cell CRISPR/Cas9 lineage tracing barcode data with dependent target sites.

Zwaans A, Seidel S, Manceau M, Stadler T Philos Trans R Soc Lond B Biol Sci. 2025; 380(1919):20230318.

PMID: 39976408 PMC: 11867110. DOI: 10.1098/rstb.2023.0318.

Computational Methods for Lineage Reconstruction.

Salvador-Martinez I Methods Mol Biol. 2025; 2886:355-373.

PMID: 39745650 DOI: 10.1007/978-1-0716-4310-5_18.

References

Chapal-Ilani N, Maruvka Y, Spiro A, Reizel Y, Adar R, Shlush L . Comparing algorithms that reconstruct cell lineage trees utilizing information on microsatellite mutations. PLoS Comput Biol. 2013; 9(11):e1003297. PMC: 3828138. DOI: 10.1371/journal.pcbi.1003297. View

Chow K, Budde M, Granados A, Cabrera M, Yoon S, Cho S . Imaging cell lineage with a synthetic digital recording system. Science. 2021; 372(6538). DOI: 10.1126/science.abb3099. View

Ceto S, Sekiguchi K, Takashima Y, Nimmerjahn A, Tuszynski M . Neural Stem Cell Grafts Form Extensive Synaptic Networks that Integrate with Host Circuits after Spinal Cord Injury. Cell Stem Cell. 2020; 27(3):430-440.e5. PMC: 7484050. DOI: 10.1016/j.stem.2020.07.007. View

Chen C, Liao Y, Peng G . Connecting past and present: single-cell lineage tracing. Protein Cell. 2022; 13(11):790-807. PMC: 9237189. DOI: 10.1007/s13238-022-00913-7. View

Salvador-Martinez I, Grillo M, Averof M, Telford M . Is it possible to reconstruct an accurate cell lineage using CRISPR recorders?. Elife. 2019; 8. PMC: 6349403. DOI: 10.7554/eLife.40292. View

Smith M . Information theoretic generalized Robinson-Foulds metrics for comparing phylogenetic trees. Bioinformatics. 2020; 36(20):5007-5013. DOI: 10.1093/bioinformatics/btaa614. View

Yang D, Jones M, Naranjo S, Rideout 3rd W, Min K, Ho R . Lineage tracing reveals the phylodynamics, plasticity, and paths of tumor evolution. Cell. 2022; 185(11):1905-1923.e25. PMC: 9452598. DOI: 10.1016/j.cell.2022.04.015. View

Li L, Bowling S, McGeary S, Yu Q, Lemke B, Alcedo K . A mouse model with high clonal barcode diversity for joint lineage, transcriptomic, and epigenomic profiling in single cells. Cell. 2023; 186(23):5183-5199.e22. DOI: 10.1016/j.cell.2023.09.019. View

Gong W, Kim H, Garry D, Kwak I . Single cell lineage reconstruction using distance-based algorithms and the R package, DCLEAR. BMC Bioinformatics. 2022; 23(1):103. PMC: 8944039. DOI: 10.1186/s12859-022-04633-x. View

10.

McKenna A, Gagnon J . Recording development with single cell dynamic lineage tracing. Development. 2019; 146(12). PMC: 6602349. DOI: 10.1242/dev.169730. View

11.

Cardona G, Rossello F, Valiente G . Extended Newick: it is time for a standard representation of phylogenetic networks. BMC Bioinformatics. 2008; 9:532. PMC: 2621367. DOI: 10.1186/1471-2105-9-532. View

12.

Gong W, Granados A, Hu J, Jones M, Raz O, Salvador-Martinez I . Benchmarked approaches for reconstruction of in vitro cell lineages and in silico models of C. elegans and M. musculus developmental trees. Cell Syst. 2021; 12(8):810-826.e4. DOI: 10.1016/j.cels.2021.05.008. View

13.

Kim J, Rosenberg N, Palacios J . Distance metrics for ranked evolutionary trees. Proc Natl Acad Sci U S A. 2020; 117(46):28876-28886. PMC: 7682335. DOI: 10.1073/pnas.1922851117. View

14.

Kretzschmar K, Watt F . Lineage tracing. Cell. 2012; 148(1-2):33-45. DOI: 10.1016/j.cell.2012.01.002. View

15.

Greener J, Kandathil S, Moffat L, Jones D . A guide to machine learning for biologists. Nat Rev Mol Cell Biol. 2021; 23(1):40-55. DOI: 10.1038/s41580-021-00407-0. View

16.

Wang S, Herriges M, Hurley K, Kotton D, Klein A . CoSpar identifies early cell fate biases from single-cell transcriptomic and lineage information. Nat Biotechnol. 2022; 40(7):1066-1074. DOI: 10.1038/s41587-022-01209-1. View

17.

Seidel S, Stadler T . TiDeTree: a Bayesian phylogenetic framework to estimate single-cell trees and population dynamic parameters from genetic lineage tracing data. Proc Biol Sci. 2022; 289(1986):20221844. PMC: 9653226. DOI: 10.1098/rspb.2022.1844. View

18.

Quinn J, Jones M, Okimoto R, Nanjo S, Chan M, Yosef N . Single-cell lineages reveal the rates, routes, and drivers of metastasis in cancer xenografts. Science. 2021; 371(6532). PMC: 7983364. DOI: 10.1126/science.abc1944. View

19.

Weinreb C, Klein A . Lineage reconstruction from clonal correlations. Proc Natl Acad Sci U S A. 2020; 117(29):17041-17048. PMC: 7382289. DOI: 10.1073/pnas.2000238117. View

20.

Frieda K, Linton J, Hormoz S, Choi J, Chow K, Singer Z . Synthetic recording and in situ readout of lineage information in single cells. Nature. 2016; 541(7635):107-111. PMC: 6487260. DOI: 10.1038/nature20777. View