| Home | Organizers | Proceedings Editors | Proceedings Contributors | Search | | ||
|
|
|||
|
||||
|
|
||||
| Title: | RECONCILIATION WITH NON-BINARY SPECIES TREES | |
| DOI No: | 10.1142/9781860948732_0044 | |
| Source: | COMPUTATIONAL SYSTEMS BIOINFORMATICS (pp 441-452) | |
| Author(s): | B. Vernot
Departments of Biological Sciences and Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, USA M. Stolzer Departments of Biological Sciences and Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, USA A. Goldman Departments of Biological Sciences and Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, USA D. Durand Corresponding Author. Departments of Biological Sciences and Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, USA |
|
| 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(|VG| · (kS + hS)) time, where VG is the number of nodes in the gene tree, hS is the height of the species tree and kS 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. | |
| Keywords: | Reconciliation; non-binary species trees; polytomy; gene duplication; gene loss; lineage sorting; deep coalescence |
|
| Full Text: | View full text in PDF format (1005KB) | |
| TOC: | Back to Table of Contents | |
|
||