Reconstruction of time-consistent species trees
- PDF / 3,594,401 Bytes
- 27 Pages / 595.276 x 790.866 pts Page_size
- 74 Downloads / 191 Views
lgorithms for Molecular Biology Open Access
RESEARCH
Reconstruction of time‑consistent species trees Manuel Lafond1† and Marc Hellmuth2*†
Abstract Background: The history of gene families—which are equivalent to event-labeled gene trees—can to some extent be reconstructed from empirically estimated evolutionary event-relations containing pairs of orthologous, paralogous or xenologous genes. The question then arises as whether inferred event-labeled gene trees are “biologically feasible” which is the case if one can find a species tree with which the gene tree can be reconciled in a time-consistent way. Results: In this contribution, we consider event-labeled gene trees that contain speciations, duplications as well as horizontal gene transfer (HGT) and we assume that the species tree is unknown. Although many problems become NP-hard as soon as HGT and time-consistency are involved, we show, in contrast, that the problem of finding a timeconsistent species tree for a given event-labeled gene can be solved in polynomial-time. We provide a cubic-time algorithm to decide whether a “time-consistent” species tree for a given event-labeled gene tree exists and, in the affirmative case, to construct the species tree within the same time-complexity. Keywords: Tree reconciliation, Gene evolution, Species evolution, Horizontal gene transfer, Time-consistency, Polynomial-time algorithm Background Genes collectively form the organism’s genomes and can be viewed as “atomic” units whose evolutionary history forms a tree. The history of species, which is also a tree, and the history of their genes is intimately linked, since the gene trees evolve along the species tree. A detailed evolutionary scenario, therefore, consists of a gene tree, a species tree and a reconciliation map µ that describes how the gene tree is embedded into the species tree. A reconciliation map assigns vertices of the gene tree to the vertices or edges in the species in such a way that (partial) ancestor relations given by the genes are preserved by the map µ . This gives rise to three important events that may act on the genes through evolution: speciation, duplication, and horizontal gene transfer (HGT) *Correspondence: [email protected] † Manuel Lafond and Marc Hellmuth contributed equally to this work 2 School of Computing, University of Leeds, E C Stoner Building, Leeds LS2 9JT, UK Full list of author information is available at the end of the article
[1, 2]. Inner vertices of the species tree represent speciation events. Hence, vertices of the gene tree that are mapped to inner vertices in the species tree underlay a speciation event and are transmitted from the parent species into the daughter species. If two copies from a single ancestral gene are formed and reside in the same species, then a duplication event happened. Contrary, if one of the copies of a gene “jumps” into a different branch of the species tree, then a HGT event happened. The latter can be annotated in the gene tree by associating a label to the edge that points from the h
Data Loading...
