PhISCS-BnB

PhISCS-BnB reconstructs optimal tumor phylogenies from single-cell sequencing (SCS) genotype matrices by identifying the most likely perfect phylogeny.

Key Features:

• Optimality Guarantee: Uses a Branch and Bound framework that guarantees convergence to the most likely perfect phylogeny from an input genotype matrix derived from SCS data, in contrast to heuristic or MCMC approaches.
• Speed: Achieves runtimes reported to be 10 to 100 times faster than the best available methods on simulated tumor SCS datasets.
• Scalability and Noise Handling: Designed to manage the size and noise characteristics inherent in emerging single-cell sequencing data.
• Validation with Real Data: Successfully reconstructed an optimal tumor phylogeny for a melanoma dataset of 24 clones and 3,574 mutations in under two hours.
• Consistency with Other Data Types: Generated phylogenies that agree with bulk exome sequencing data from in vivo tumors derived from the same cell line.

Scientific Applications:

• Tumor evolution reconstruction: Infers evolutionary trees of cancer cell populations at single-cell resolution using genotype matrices from SCS data.
• Analysis of tumor heterogeneity and clonal evolution: Enables examination of genetic diversity and clonal relationships within tumors.
• Cross-data validation: Facilitates comparison and validation of single-cell-derived phylogenies against bulk exome sequencing from related in vivo tumors.
• Large-scale SCS dataset analysis: Applicable to large and noisy single-cell sequencing datasets generated from tumor cell lines and related samples.

Methodology:

Applies a Branch and Bound algorithm to solve the perfect phylogeny problem on genotype matrices from SCS data by systematically exploring solutions and pruning suboptimal branches.