SubMARine

SubMARine reconstructs tumor clone trees in polynomial time to summarize cancer evolutionary histories and represent uncertainty in subclonal ancestral relationships.

Key Features:

• Polynomial-Time Efficiency: Operates in polynomial time to reconstruct clone trees, enabling analysis of larger subclonal populations compared with exponential-time methods.
• Partial Clone Trees: Defines partial clone trees that record subsets of pairwise ancestral relationships to implicitly represent all clone trees consistent with those constraints.
• Maximally-Constrained Ancestral Reconstruction (MAR): Identifies the MAR, a partial clone tree that encapsulates all clone trees fitting the input data equally well, and computes an approximation (subMAR) whose defined relationships are consistent with the MAR.
• Scalability and Performance: Scales to clone trees with up to 50 nodes, running in under 70 seconds and using less than 1 GB of memory on reported datasets.
• Handling Uncertainty: Summarizes all valid phylogenies to capture uncertainty in evolutionary histories and ambiguous ancestral relationships.
• Extension to Copy Number Aberrations: Extends the framework to incorporate subclonal copy number aberrations (CNAs) in the reconstruction.
• Validity Conditions: Provides a complete set of validity conditions under which a partial clone tree is consistent across all possible phylogenies.
• Validation and Performance Statistics: In simulations and lung cancer data, the approximated MAR matched the actual MAR in over 99.9% of single-solution cases and recovered uncertain relationships in >80% of multi-solution cases.

Scientific Applications:

• Tumor Phylogeny Reconstruction: Reconstructs and summarizes tumor evolutionary histories from subclonal mutation and copy number data.
• Subclonal CNA Analysis in Cancer Genomics: Incorporates subclonal copy number aberrations to analyze their impact on tumor evolution.
• Uncertainty Quantification: Quantifies and reports uncertainty across possible clone trees to inform interpretation of evolutionary trajectories.
• Benchmarking and Validation: Supports validation and benchmarking via simulations and analysis of real lung cancer datasets.

Methodology:

Implements a polynomial-time algorithm that constructs partial clone trees, identifies and approximates the maximally-constrained ancestral reconstruction (MAR/subMAR), enforces validity conditions, and extends the reconstruction to include subclonal copy number aberrations, validated using simulations and lung cancer dataset analysis.