Summarizing the solution space in tumor phylogeny inference by multiple consensus trees.

Area of Science:

• Computational Biology
• Bioinformatics
• Cancer Genomics

Background:

• Cancer phylogenies are vital for understanding tumorigenesis and clinical outcomes.
• Current methods struggle with cancer's heterogeneity, yielding numerous plausible phylogenies.
• Existing summary methods, limited to single trees or graphs, may obscure critical topological features.

Purpose of the Study:

• To address the challenge of summarizing large sets of cancer phylogenies.
• To introduce a novel approach for clustering and inferring consensus trees from multiple candidate phylogenies.
• To develop methods that capture topological diversity within cancer evolution.

Main Methods:

• Introduced the Multiple Consensus Tree (MCT) problem.
• Developed an exact algorithm using mixed integer linear programming (MILP).
• Designed a heuristic algorithm for efficient, high-quality consensus tree inference.

Main Results:

• Demonstrated that the MCT problem is NP-hard.
• The MILP approach provides an exact solution.
• The heuristic algorithm efficiently recovers optimal solutions, significantly faster than MILP.
• The method successfully adapts the number of clusters based on solution space complexity.
• Applicability confirmed on both simulated and real cancer data.

Conclusions:

• The proposed MCT framework and algorithms effectively summarize complex cancer phylogeny solution spaces.
• This approach overcomes limitations of single-tree summaries, revealing richer evolutionary insights.
• The developed methods offer a powerful tool for cancer genomics research and clinical applications.