Reconcilation with non-binary species trees.

@article{citeulike:1833712, abstract = {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.}, address = {Departments of Biological Sciences and Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, USA. durand@cs.cmu.edu.}, author = {Vernot, B. and Stolzer, M. and Goldman, A. and Durand, D. }, citeulike-article-id = {1833712}, issn = {1752-7791}, journal = {Comput Syst Bioinformatics Conf}, keywords = {reconciliation, species\_tree}, pages = {441--452}, posted-at = {2007-10-29 01:18:00}, priority = {3}, title = {Reconcilation with non-binary species trees.}, url = {http://view.ncbi.nlm.nih.gov/pubmed/17951846}, volume = {6}, year = {2007} }

TY - JOUR ID - citeulike:1833712 L3 - citeulike-article-id:1833712 TI - Reconcilation with non-binary species trees. JF - Comput Syst Bioinformatics Conf VL - 6 SP - 441 EP - 452 AD - Departments of Biological Sciences and Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, USA. durand@cs.cmu.edu. SN - 1752-7791 N2 - 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. KW - reconciliation KW - species_tree AU - Vernot, B AU - Stolzer, M AU - Goldman, A AU - Durand, D PY - 2007/// UR - http://view.ncbi.nlm.nih.gov/pubmed/17951846 ER -