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

Area of Science:

• Genomics
• Computational Biology
• Evolutionary Biology

Background:

• Single-cell genome sequencing offers high resolution but suffers from significant error rates, allelic bias, and uneven coverage.
• These data limitations necessitate specialized computational approaches for accurate biological interpretation, particularly for inferring cell lineage trees.
• Understanding cell lineage is crucial for studying tumor formation, growth, and normal organ development.

Purpose of the Study:

• To develop and evaluate Scelestial, a novel computational method for robust cell lineage tree reconstruction from noisy single-cell genomic data.
• To address the challenges of missing data and computational efficiency in single-cell lineage inference.

Main Methods:

• Scelestial employs an approximation algorithm for the Steiner tree problem, extending the neighbor-joining method.
• The algorithm efficiently selects key sequences as internal nodes and utilizes lineage tree-based imputation for missing values.
• Performance was benchmarked against seven leading single-cell lineage reconstruction algorithms using simulated and real tumor data.

Main Results:

• Scelestial demonstrated superior performance compared to existing methods in terms of both accuracy and computational runtime.
• The method effectively handles the complexities of single-cell data, including high error rates and missing information.
• Comparative analysis confirmed Scelestial's robustness on diverse datasets.

Conclusions:

• Scelestial provides a highly accurate and efficient solution for cell lineage tree reconstruction from single-cell genome sequencing data.
• The method's ability to manage data imperfections makes it a valuable tool for biological research.
• Scelestial is available as a C++ implementation and an R package (RScelestial).