An Integer Linear Programming Solution for the Domain-Gene-Species Reconciliation Problem
An Integer Linear Programming Solution for the Domain-Gene-Species Reconciliation Problem
复制标题
域-基因-物种协调问题的整数线性规划解决方案
DOI：
10.1145/3233547.3233603
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Mukul S. Bansal
中科院分区：
文献类型：
--
作者：
Lei Li;Mukul S. Bansal
众所周知，大多数真核基因含有一个或多个蛋白质结构域，并且基因的结构域内容可以随时间变化。域内容的这种变化，通过域复制，转移或丢失，具有重要的进化和功能后果。最近，一个强大的新的和解框架，称为域-基因-物种（DGS）和解，被引入到一个或多个基因家族内的域家族的进化和物种树内的这些基因家族的进化同时建模。DGS协调中的底层计算问题是NP难的，目前使用启发式算法来估计最佳DGS协调。然而，这种启发式有几个不希望的限制。首先，它不能保证最优或接近最优。其次，它可能导致生物学上不切实际的进化情景。第三，它只计算一个DGS协调，即使可能有多个最佳DGS协调。在这项工作中，我们介绍了第一个精确的算法来计算最佳的DGS和解，解决所有三个限制。我们的算法是基于一个整数线性规划制定的问题，我们通过求解一系列线性规划松弛迭代解决。我们的实验结果超过$3,400$域树和超过7,000个基因树从12个苍蝇物种表明，我们的新算法是高度可扩展的，它导致DGS和解推理显着改善。我们的精确算法的实现可以从http://compbio.engr.uconn.edu/software/seadog/免费获得。
It is well-understood that most eukaryotic genes contain one or more protein domains and that the domain content of a gene can change over time. This change in domain content, through domain duplications, transfers, or losses, has important evolutionary and functional consequences. Recently, a powerful new reconciliation framework, called Domain-Gene-Species (DGS) reconciliation, was introduced to simultaneously model the evolution of a domain family inside one or more gene families and the evolution of those gene families inside a species tree. The underlying computational problem in DGS reconciliation is NP-hard and a heuristic algorithm is currently used to estimate optimal DGS reconciliations. However, this heuristic has several undesirable limitations. First, it offers no guarantee of optimality or near-optimality. Second, it can result in biologically unrealistic evolutionary scenarios. And third, it only computes a single DGS reconciliation even though there can be multiple optimal DGS reconciliations. In this work, we introduce the first exact algorithm for computing optimal DGS reconciliations that addresses all three limitations. Our algorithm is based on an integer linear programming formulation of the problem, which we solve iteratively by solving a series of linear programming relaxations. Our experimental results on over $3,400$ domain trees and over 7,000 gene trees from 12 fly species shows that our new algorithm is highly scalable and that it leads to significant improvement in DGS reconciliation inference. An implementation of our exact algorithm is available freely from http://compbio.engr.uconn.edu/software/seadog/.