Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss.
Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss.
复制标题
DOI：
10.1093/bioinformatics/bts225
复制
发表时间：
2012-06-15
期刊：
影响因子：
--
通讯作者：
Kellis M
中科院分区：
文献类型：
--
作者：
Bansal MS;Alm EJ;Kellis M
动机：基因家族的进化是由物种形成、基因复制、水平基因转移和基因丢失等进化事件驱动的，推断这些事件在给定基因家族的进化历史中是比较和进化基因组学中的一个基本问题，具有许多重要的应用。解决这个问题需要使用一个调和框架，其中输入包括一个基因家族遗传和相应的物种遗传，目标是通过假设物种形成，基因复制，水平基因转移和基因丢失事件来调和两者。这种协调问题被称为重复传输损失（DTL）协调，并已在文献中得到广泛研究。然而，即使是最快的DTL和解的现有算法是太慢的和解大型基因家族，并用于更复杂的应用程序，如基因树或物种树重建。结果如下：我们提出了两个新的算法的DTL和解问题，显着快于现有的算法，无论是渐近和在实践中。我们还扩展了标准的DTL和解模型，考虑距离相关的传输成本，允许更准确的和解，并给出了一个有效的算法DTL和解在此扩展模型。我们实现了我们的新算法，并使用模拟和生物数据集，证明了比现有方法快10万倍的速度。这一巨大的改进使得可以使用DTL和解进行严格的大基因家族的进化分析，并使其在先进的和解为基础的基因和物种树重建方法的使用。可用性：我们的程序可以从http://compbio.mit.edu/ranger-dtl/免费下载。联系方式：mukul@csail.mit.edu; manoli@mit.edu补充信息：补充数据可在生物信息学在线获得。
Motivation: Gene family evolution is driven by evolutionary events such as speciation, gene duplication, horizontal gene transfer and gene loss, and inferring these events in the evolutionary history of a given gene family is a fundamental problem in comparative and evolutionary genomics with numerous important applications. Solving this problem requires the use of a reconciliation framework, where the input consists of a gene family phylogeny and the corresponding species phylogeny, and the goal is to reconcile the two by postulating speciation, gene duplication, horizontal gene transfer and gene loss events. This reconciliation problem is referred to as duplication-transfer-loss (DTL) reconciliation and has been extensively studied in the literature. Yet, even the fastest existing algorithms for DTL reconciliation are too slow for reconciling large gene families and for use in more sophisticated applications such as gene tree or species tree reconstruction. Results: We present two new algorithms for the DTL reconciliation problem that are dramatically faster than existing algorithms, both asymptotically and in practice. We also extend the standard DTL reconciliation model by considering distance-dependent transfer costs, which allow for more accurate reconciliation and give an efficient algorithm for DTL reconciliation under this extended model. We implemented our new algorithms and demonstrated up to 100 000-fold speed-up over existing methods, using both simulated and biological datasets. This dramatic improvement makes it possible to use DTL reconciliation for performing rigorous evolutionary analyses of large gene families and enables its use in advanced reconciliation-based gene and species tree reconstruction methods. Availability: Our programs can be freely downloaded from http://compbio.mit.edu/ranger-dtl/. Contact: mukul@csail.mit.edu; manoli@mit.edu Supplementary information: Supplementary data are available at Bioinformatics online.
登录
查看更多内容
DOI：
10.1109/tcbb.2008.119
发表时间：
2009-07-01
影响因子：
4.5
作者：
Jin, Guohua;Nakhleh, Luay;Tuller, Tamir
通讯作者：
Tuller, Tamir
影响因子：
1.1
作者：
Bonizzoni, P;Della Vedova, G;Dondi, R
通讯作者：
Dondi, R
DOI：
10.1186/1748-7188-5-16
发表时间：
2010-02-03
期刊：
Algorithms for molecular biology : AMB
影响因子：
--
作者：
Conow C;Fielder D;Ovadia Y;Libeskind-Hadas R
通讯作者：
Libeskind-Hadas R
影响因子：
1.7
作者：
Chauve, Cedric;Doyon, Jean-Philippe;El-Mabrouk, Nadia
通讯作者：
El-Mabrouk, Nadia
影响因子：
6.5
作者：
Burleigh, J. Gordon;Bansal, Mukul S.;Vision, Todd J.
通讯作者：
Vision, Todd J.