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

Nuraini Aguse, Yuanyuan Qi, Mohammed El-Kebir

Research output: Contribution to journalArticlepeer-review

Abstract

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 T 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 T 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 T.

Original languageEnglish (US)
Article numberbtz312
Pages (from-to)i408-i416
JournalBioinformatics
Volume35
Issue number14
DOIs
StatePublished - Jul 15 2019
Externally publishedYes

ASJC Scopus subject areas

  • Statistics and Probability
  • Biochemistry
  • Molecular Biology
  • Computer Science Applications
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Summarizing the solution space in tumor phylogeny inference by multiple consensus trees'. Together they form a unique fingerprint.

Cite this