PhISCS

PhISCS reconstructs sub-perfect tumor phylogenies by integrating single-cell sequencing (SCS) and bulk sequencing data to minimize errors from allele dropout, read errors, variable coverage, and violations of the infinite sites assumption (ISA).

Key Features:

• Optimal subperfect phylogeny formulation: Minimizes a linear combination of potential false negatives (e.g., allele dropout), false positives (e.g., read errors), and ISA-violating mutations.
• Integration of SCS and bulk data: Incorporates variant allele frequencies (VAFs) from bulk sequencing to impose lineage constraints on SCS-derived phylogenies.
• Explicit modeling of ISA violations: Accounts for mutations that violate the infinite sites assumption, including those arising from incorrect copy number estimation.
• Combinatorial formulations: Expresses the inference problem as both an integer linear program (ILP) and a Boolean constraint satisfaction problem (CSP).
• Solver-based optimization: Solves the ILP/CSP formulations using ILP and CSP solvers to obtain optimal solutions.
• Robustness to SCS limitations: Addresses SCS-specific issues such as frequent allele dropout and variable sequence coverage.
• Performance evaluation: Demonstrated superior generality and accuracy on simulated and real datasets.

Scientific Applications:

• Tumor phylogeny reconstruction: Reconstructs evolutionary histories of tumors from combined SCS and bulk sequencing data.
• Analysis of ISA-violating events: Detects and models biological phenomena that violate ISA such as loss of heterozygosity, deletions, and convergent evolution.
• Lineage constraint inference: Uses bulk-derived VAFs to constrain lineage relationships among single cells, improving inference of clonal structure.
• Benchmarking and validation: Applicable to evaluation of phylogeny inference methods using simulated and real cancer sequencing datasets.

Methodology:

PhISCS formulates the optimal subperfect phylogeny problem as an integer linear program (ILP) and as a Boolean constraint satisfaction problem (CSP), minimizes a linear combination of false negatives, false positives, and ISA-violating mutations, incorporates variant allele frequencies (VAFs) from bulk sequencing as lineage constraints, and solves the formulations using ILP/CSP solvers.