Reconciliation with non-binary species trees.
Reconciliation with non-binary species trees.
复制标题
DOI：
10.1142/9781860948732_0044
复制
发表时间：
2007-09
期刊：
影响因子：
--
通讯作者：
Benjamin Vernot;Maureen Stolzer;A. Goldman;D. Durand
中科院分区：
文献类型：
--
作者：
Benjamin Vernot;Maureen Stolzer;A. Goldman;D. Durand
Reconciliation is the process of resolving disagreement between gene and species trees, by invoking gene duplications and losses to explain topological incongruence. The resulting inferred duplication histories are a valuable source of information for a broad range of biological applications, including ortholog identification, estimating gene duplication times, and rooting and correcting gene trees. Reconciliation for binary trees is a tractable and well studied problem. However, a striking proportion of species trees are non-binary. For example, 64% of branch points in the NCBI taxonomy have three or more children. When applied to non-binary species trees, current algorithms overestimate the number of duplications because they cannot distinguish between duplication and deep coalescence. We present the first formal algorithm for reconciling binary gene trees with non-binary species trees under a duplication-loss parsimony model. Using a space efficient mapping from gene to species tree, our algorithm infers the minimum number of duplications and losses in O(|V(G)| . (k(S) + h(S))) time, where V(G) is the number of nodes in the gene tree, h(S) is the height of the species tree and k(S) is the width of its largest multifurcation. We also present a dynamic programming algorithm for a combined loss model, in which losses in sibling species may be represented as a single loss in the common ancestor. Our algorithms have been implemented in NOTUNG, a robust, production quality tree-fitting program, which provides a graphical user interface for exploratory analysis and also supports automated, high-throughput analysis of large data sets.
