MCT

MCT identifies multiple consensus trees and clusters input phylogenetic trees to summarize heterogeneous cancer phylogenies by minimizing distances between input trees and their corresponding consensus trees.

Key Features:

• Multiple Consensus Tree Optimization: Computes k consensus trees and a corresponding k-clustering of input trees to minimize the sum of distances between each input tree and its assigned consensus tree.
• Brute Force Solver: Explores the complete solution space through exhaustive enumeration of possible consensus tree assignments.
• Mixed Integer Linear Programming (MILP) Formulation: Applies a mixed integer linear programming approach to compute exact optimal solutions to the multiple consensus tree problem.
• Coordinate Ascent Heuristic: Uses a coordinate ascent heuristic to efficiently identify high-quality consensus trees and cluster assignments.
• Topology-Preserving Clustering: Groups phylogenetic trees into clusters to capture diverse topological patterns within heterogeneous phylogeny sets.

Scientific Applications:

• Cancer Phylogeny Inference: Summarizes heterogeneous tumor evolutionary histories from multiple inferred phylogenetic trees.
• Tumor Evolution Analysis: Identifies representative consensus trees that capture major evolutionary patterns in cancer progression.
• Phylogenetic Tree Set Analysis: Analyzes collections of phylogenetic trees to identify major structural patterns through clustering and consensus inference.

Methodology:

MCT solves the multiple consensus tree problem by computing k consensus trees and a k-clustering of input trees that minimize distances between trees using brute force enumeration, mixed integer linear programming (MILP), or a coordinate ascent heuristic.