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

MOTIVATION: Cancer phylogenies are key to studying tumorigenesis and have clinical implications. Due to the heterogeneous nature of cancer and limitations in current sequencing technology, current cancer phylogeny inference methods identify a large solution space of plausible phylogenies. To facilitate further downstream analyses, methods that accurately summarize such a set [Formula: see text] of cancer phylogenies are imperative. However, current summary methods are limited to a single consensus tree or graph and may miss important topological features that are present in different subsets of candidate trees. RESULTS: We introduce the Multiple Consensus Tree (MCT) problem to simultaneously cluster [Formula: see text] and infer a consensus tree for each cluster. We show that MCT is NP-hard, and present an exact algorithm based on mixed integer linear programming (MILP). In addition, we introduce a heuristic algorithm that efficiently identifies high-quality consensus trees, recovering all optimal solutions identified by the MILP in simulated data at a fraction of the time. We demonstrate the applicability of our methods on both simulated and real data, showing that our approach selects the number of clusters depending on the complexity of the solution space [Formula: see text]. AVAILABILITY AND IMPLEMENTATION: https://github.com/elkebir-group/MCT. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.