PhISCS-BnB: a fast branch and bound algorithm for the perfect tumor phylogeny reconstruction problem

Area of Science:

• Computational Biology
• Genomics
• Cancer Research

Background:

• Single-cell sequencing (SCS) advances tumor evolution insights but current phylogeny reconstruction methods are slow and lack guarantees.
• Existing computational approaches, including integer linear programming and Monte Carlo Markov Chain, face scalability challenges with large, noisy SCS datasets.

Purpose of the Study:

• To develop a novel, efficient, and guaranteed method for reconstructing tumor phylogenies from single-cell sequencing data.
• To address the limitations of existing computational tools in handling the scale and noise of SCS data for tumor evolution studies.

Main Methods:

• Introduction of PhISCS-BnB (phylogeny inference using SCS via branch and bound), a branch and bound algorithm.
• Application to simulated tumor SCS data and a large melanoma dataset with 20 clones and 2367 mutations.

Main Results:

• PhISCS-BnB computes the most likely perfect phylogeny with an optimality guarantee.
• Demonstrated 10-100 times speed improvement over existing methods on simulated data.
• Successfully reconstructed the optimal tumor phylogeny for a melanoma dataset in under 4 hours, agreeing with and extending previous findings.

Conclusions:

• PhISCS-BnB offers a scalable and accurate solution for tumor phylogeny reconstruction from SCS data.
• The method enhances the understanding of clonal evolution in tumors.
• PhISCS-BnB is available via GitHub for broader research application.