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

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.