Summarizing the solution space in tumor phylogeny inference by multiple consensus trees
Summarizing the solution space in tumor phylogeny inference by multiple consensus trees
复制标题
DOI：
10.1093/bioinformatics/btz312
复制
发表时间：
2019-07-15
期刊：
影响因子：
5.8
通讯作者：
El-Kebir, Mohammed
中科院分区：
文献类型：
--
作者：
Aguse, Nuraini;Qi, Yuanyuan;El-Kebir, Mohammed
动机癌症系统发育是研究肿瘤发生的关键并具有临床意义。由于癌症的异质性和当前测序技术的局限性，当前的癌症系统发育推断方法确定了合理系统发育的巨大解决方案空间。为了促进进一步的下游分析，准确总结这样一组癌症系统发育的方法势在必行。然而，当前的汇总方法仅限于单个共识树或图，并且可能会错过候选树不同子集中存在的重要拓扑特征。结果我们引入了多重共识树（MCT）问题来同时对 T 进行聚类并推断每个聚类的共识树。我们证明了 MCT 是 NP 难的，并提出了一种基于混合整数线性规划（MILP）的精确算法。此外，我们引入了一种启发式算法，可以有效地识别高质量共识树，在很短的时间内恢复 MILP 在模拟数据中识别的所有最佳解决方案。我们证明了我们的方法在模拟和真实数据上的适用性，表明我们的方法根据解决方案空间 T 的复杂性来选择簇的数量。可用性和实现https://github.com/elkebir-group/MCT。补充信息补充数据可在生物信息学在线获得。
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.Availability and implementationhttps://github.com/elkebir-group/MCT.Supplementary informationSupplementary data are available at Bioinformatics online.