An Integer Linear Programming Solution for the Most Parsimonious Reconciliation Problem under the Duplication-Loss-Coalescence Model
An Integer Linear Programming Solution for the Most Parsimonious Reconciliation Problem under the Duplication-Loss-Coalescence Model
复制标题
重复-丢失-合并模型下最简洁协调问题的整数线性规划解
DOI：
10.1145/3388440.3412474
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Wu, Yi-Chieh
中科院分区：
文献类型：
--
作者：
Carothers, Morgan;Gardi, Joseph;Gross, Gianluca;Kuze, Tatsuki;Liu, Nuo;Plunkett, Fiona;Qian, Julia;Wu, Yi-Chieh
给定一个基因树、一个物种树和它们的叶子之间的关联，最大简约调和（MPR）问题试图找到一个基因树到物种树的映射，使用进化事件的生物模型来解释它们的不一致性。不幸的是，当同时考虑基因复制、基因丢失和合并时，MPR问题是NP难的。虽然存在精确的算法，但由于时间和存储器要求，在实践中使用它可能是有问题的。在这项工作中，我们提出了一个整数线性规划（ILP）制定解决MPR问题时，考虑重复，损失和合并。在12种果蝇的模拟数据集上的实验结果表明，我们的新算法是准确的和可扩展的。此外，与现有的精确算法相比，我们的公式允许用户限制最大运行时间，从而权衡准确性和可扩展性，使其成为系统发育管道的有吸引力的选择。
Given a gene tree, a species tree, and an association between their leaves, the maximum parsimony reconciliation (MPR) problem seeks to find a mapping of the gene tree to the species tree that explains their incongruity using a biological model of evolutionary events. Unfortunately, when simultaneously accounting for gene duplication, gene loss, and coalescence, the MPR problem is NP-hard. While an exact algorithm exists, it can be problematic to use in practice due to time and memory requirements. In this work, we present an integer linear programming (ILP) formulation for solving the MPR problem when considering duplications, losses, and coalescence. Our experimental results on a simulated data set of 12 Drosophila species shows that our new algorithm is both accurate and scalable. Furthermore, in contrast to the existing exact algorithm, our formulation allows users to limit the maximum runtime and thus trade-off accuracy and scalability, making it an attractive choice for phylogenetic pipelines.
登录
查看更多内容
域-基因-物种协调问题的整数线性规划解决方案
DOI：
10.1145/3233547.3233603
发表时间：
2018
期刊：
Proceedings of the 2018 ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics
影响因子：
--
作者：
Lei Li;Mukul S. Bansal
通讯作者：
Mukul S. Bansal
影响因子：
--
作者：
R. Page
通讯作者：
R. Page
影响因子：
2
作者：
Chan, Yao-ban;Ranwez, Vincent;Scornavaccac, Celine
通讯作者：
Scornavaccac, Celine
影响因子：
7
作者：
Rasmussen, Matthew D.;Kellis, Manolis
通讯作者：
Kellis, Manolis
影响因子：
1.3
作者：
Lougee-Heimer, R
通讯作者：
Lougee-Heimer, R