Reconciling a gene tree to a species tree under the duplication cost model
Reconciling a gene tree to a species tree under the duplication cost model
复制标题
DOI：
10.1016/j.tcs.2005.05.016
复制
发表时间：
2005-11-30
影响因子：
1.1
通讯作者：
Dondi, R
中科院分区：
文献类型：
--
作者：
Bonizzoni, P;Della Vedova, G;Dondi, R
调和来自代表不同基因家族之间关系的进化树的信息的一般问题在生物信息学中非常重要，并且已经由Ma等人在计算机科学研究人员中普及。[从基因树到物种树，SIAM J. Comput. 30(3)(2000) 729-752]其中作者提出了一个有趣的问题，即调和基因树和物种树的最小树的某个定义是否正确。我们肯定地回答这个问题；此外，我们给出了一种计算这种最小叶调和树的有效算法，并证明了这种树的唯一性。然后，我们通过展示范例问题（由多基因基因组的范例分析产生）是np困难的，来解决生物学问题的一些不同版本，即使给定标签的副本数量最多为两个。最后，我们引入了重组进化树问题的两个新公式，扩展了基因重复问题[Ma等人，从基因树到物种树，SIAM J. computer . 30(3) (2000) 729-752；M. Fellows等人，关于多基因复制问题，见：Proc. 9th Internat。计算机协会。论算法和计算（ISAAC98）， 1998；R. Page，树之间的地图和基因之间的历史关联的枝系分析，系统生物学43 (1994)58-77；r.m.p epage， J. Cotton，脊椎动物系统基因组学：和解树和基因复制，第2期。生物计算2002 (PSB2002)，2002年，536-547页；R. Guigo et al.，古代分子系统发育的重建，物理学报。和进化。6(2)(1996)189-213]，我们给出了一个精确的算法（通过动态规划）这些公式之一。(c) 2005 Elsevier B.V.版权所有
The general problem of reconciling the information from evolutionary trees representing the relationships between distinct gene families is of great importance in bioinformatics and has been popularized among the computer science researchers by Ma et al. [From gene trees to species trees, SIAM J. Comput. 30(3) (2000) 729-752] where the authors pose the intriguing question if a certain definition of minimum tree that reconciles a gene tree and a species tree is correct. We answer affirmatively to this question; moreover, we show an efficient algorithm for computing such minimum-leaf reconciliation trees and prove the uniqueness of such trees. We then tackle some different versions of the biological problem by showing that the exemplar problem, arising from the exemplar analysis of multigene genomes, is NP-hard even when the number of copies of a given label is at most two. Finally, we introduce two novel formulations for the problem of recombining evolutionary trees, extending the gene duplication problem studied in [Ma et al., From gene trees to species trees, SIAM J. Comput. 30(3) (2000) 729-752; M. Fellows et al., On the multiple gene duplication problem, in: Proc. Ninth Internat. Symp. on Algorithms and Computation (ISAAC98), 1998; R. Page, Maps between trees and cladistic analysis of historical associations among genes, Systematic Biology 43 (1994) 58-77; R.M. Page, J. Cotton, Vertebrate phylogenomics: reconciled trees and gene duplications, in: Proc. Pacific Symp. on Biocomputing 2002 (PSB2002),2002, pp. 536-547; R. Guigo et al., Reconstruction of ancient molecular phylogeny, Mol. Phy. and Evol. 6(2) (1996) 189-213], and we give an exact algorithm (via dynamic programming) for one of these formulations. (c) 2005 Elsevier B.V. All rights reserved.