Scelestial: Fast and accurate single-cell lineage tree inference based on a Steiner tree approximation algorithm

Mohammad-Hadi Foroughmand-Araabi, Sama Goliaei and Alice C McHardy

PLOS Computational Biology, 2022, vol. 18, issue 8, 1-27

Abstract: Single-cell genome sequencing provides a highly granular view of biological systems but is affected by high error rates, allelic amplification bias, and uneven genome coverage. This creates a need for data-specific computational methods, for purposes such as for cell lineage tree inference. The objective of cell lineage tree reconstruction is to infer the evolutionary process that generated a set of observed cell genomes. Lineage trees may enable a better understanding of tumor formation and growth, as well as of organ development for healthy body cells. We describe a method, Scelestial, for lineage tree reconstruction from single-cell data, which is based on an approximation algorithm for the Steiner tree problem and is a generalization of the neighbor-joining method. We adapt the algorithm to efficiently select a limited subset of potential sequences as internal nodes, in the presence of missing values, and to minimize cost by lineage tree-based missing value imputation. In a comparison against seven state-of-the-art single-cell lineage tree reconstruction algorithms—BitPhylogeny, OncoNEM, SCITE, SiFit, SASC, SCIPhI, and SiCloneFit—on simulated and real single-cell tumor samples, Scelestial performed best at reconstructing trees in terms of accuracy and run time. Scelestial has been implemented in C++. It is also available as an R package named RScelestial.Author summary: Reconstructing the evolutionary history from the genome sequences of single cells can provide a detailed understanding of evolutionary events and changes on a very fine-grained scale, for instance in the development of organs and cancer. Due to the increasing sizes of single-cell datasets, scalable and accurate methods are required. In this work we describe Scelestial, a software implementing an adapted Steiner tree approximation algorithm for evolutionary tree reconstruction from the analysis of single-cell datasets. The Steiner tree approximation algorithm, unlike other heuristics and sampling-based methods (e. g. Markov chain Monte Carlo), provides guarantees of its performance. A comparison of Scelestial with state of the art methods showed that it performed favourably in terms of quality of the inferred trees as well as speed across a large number of simulated data sets, and produced the most plausible evolutionary scenarios on single cell data sets from cancer patients. Taken together, our results show that Scelestial provides a valuable addition to current single cell lineage inference techniques.

Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1009100 (text/html)
https://journals.plos.org/ploscompbiol/article/fil ... 09100&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pcbi00:1009100

DOI: 10.1371/journal.pcbi.1009100

Access Statistics for this article

More articles in PLOS Computational Biology from Public Library of Science
Bibliographic data for series maintained by ploscompbiol ().