H-trees: a Model of Evolutionary Scenarios with Horizontal Gene Transfer

• Autorzy: Górecki, P.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we present a model of evolution of genes in the context of evolution of species. The concept is based on reconciliation models. We assume that the gene evolution is modeled by macro-evolutionary events like gene duplications, losses and horizontal gene transfers (HGTs) while the evolution of species is shaped by speciation events. We define an evolutionary scenario (called an H-tree) which will represent the common evolution of genes and species. We propose a rewrite system for transforming the scenarios. We prove that the system is confluent, sound and strongly normalizing. We show that a scenario in a normal form (that is, non-reducible) is unique and minimal in the sense of the cost computed as the total number of gene duplications, losses and HGTs (mutation cost). We present a classification of the scenarios and analyze their hierarchies.

Słowa kluczowe

EN

rewrite system; molecular evolution; phylogenetic tree; Duplication-loss model; DL-model; horizontal gene transfer; reconciled tree

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 103, nr 1-4
• Strony: 105-128
• Opis fizyczny: Bibliogr. 34 poz., wykr.

Twórcy

autor

Górecki, P.

• Warsaw University, Institute of Informatics, Banacha 2, 02-097 Warsaw, Poland,

Bibliografia

• [1] Akerborg, O., Sennblad, B., Arvestad, L., Lagergren, J.: Simultaneous Bayesian gene tree reconstruction and reconciliation analysis., Proc Natl Acad Sci U S A, 106(14), Apr 2009, 5714-5719.
• [2] Arvestad, L., Berglund, A.-C., Lagergren, J., Sennblad, B.: Bayesian gene/species tree reconciliation and orthology analysis using MCMC., Bioinformatics, 19 Suppl 1, 2003, i7-15.
• [3] Arvestad, L., Berglund, A.-C., Lagergren, J., Sennblad, B.: Gene tree reconstruction and orthology analysis based on an integrated model for duplications and sequence evolution, RECOMB, 2004.
• [4] Arvestad, L., Lagergren, J., Sennblad, B.: The gene evolution model and computing its associated probabilities, J. ACM, 56(2), 2009.
• [5] Bansal, M. S., Burleigh, J. G., Eulenstein, O., Wehe, A.: Heuristics for the Gene-Duplication Problem: A _(n) Speed-Up for the Local Search, RECOMB, 2007.
• [6] Bansal, M. S., Eulenstein, O.: An (n2/ log n) Speed-Up of TBR Heuristics for the Gene-Duplication Problem, WABI, 2007.
• [7] Bansal, M. S., Eulenstein, O.: The Gene-Duplication Problem: Near-Linear Time Algorithms for NNI Based Local Searches, ISBRA, 2008.
• [8] Bansal, M. S., Eulenstein, O.: The multiple gene duplication problem revisited, Bioinformatics, 24(13), Jul 2008, i132-8.
• [9] Bansal, M. S., Eulenstein, O., Wehe, A.: The gene-duplication problem: near-linear time algorithms for NNI-based local searches, IEEE/ACM Trans Comput Biol Bioinform, 6(2), 2009, 221-31.
• [10] Berglund-Sonnhammer, A.-C., Steffansson, P., Betts, M. J., Liberles, D. A.: Optimal gene trees from sequences and species trees using a soft interpretation of parsimony., J Mol Evol, 63(2), Aug 2006, 240-250.
• [11] Bonizzoni, P., Della Vedova, G., Dondi, R.: Reconciling a gene tree to a species tree under the duplication cost model, Theoretical Computer Science, 347(1-2), Nov 2005, 36-53.
• [12] Burleigh, J. G., Bansal,M. S.,Wehe, A., Eulenstein, O.: Locating large-scale gene duplication events through reconciled trees: implications for identifying ancient polyploidy events in plants, J Comput Biol, 16(8), Aug 2009, 1071-83.
• [13] Chang, W.-C., Eulenstein, O.: Reconciling Gene Trees with Apparent Polytomies, COCOON, 2006.
• [14] Charleston,M.: Jungles: a new solution to the host/parasite phylogeny reconciliation problem, Mathematical Biosciences, 149(2),May 1998, 191-223.
• [15] Chauve, C., El-Mabrouk, N.: New Perspectives on Gene Family Evolution: Losses in Reconciliation and a Link with Supertrees, RECOMB, 2009.
• [16] Eulenstein, O., Mirkin, B., Vingron, M.: Duplication-Based Measures of Difference Between Gene and Species Trees, Journal of Computational Biology, 5(1), 1998, 135-148.
• [17] Fellows, M. R., Hallett, M. T., Stege, U.: On the Multiple Gene Duplication Problem, ISAAC, 1998.
• [18] Felsenstein, J.: Inferring phylogenies, Sinauer Associates, Sunderland,Mass., 2004.
• [19] Gogarten, M. B., Gogarten, J. P., Olendzenski, L., Eds.: Horizontal Gene Transfer - Genomes in Flux, vol. 532 of Methods in Molecular Biology, Springer, 2009.
• [20] Goodman, M., Czelusniak, J., Moore, G. W., Romero-Herrera, A. E., Matsuda, G.: Fitting the Gene Lineage into its Species Lineage, a Parsimony Strategy Illustrated by Cladograms Constructed from Globin Sequences, Systematic Zoology, 28(2), 1979, 132-163.
• [21] Górecki, P.: Reconciliation problems for duplication, loss and horizontal gene transfer, RECOMB, 2004.
• [22] Górecki, P., Tiuryn, J.: DLS-trees: A model of evolutionary scenarios, Theor. Comput. Sci., 359(1-3), 2006, 378-399.
• [23] Górecki, P., Tiuryn, J.: Inferring phylogeny from whole genomes, Bioinformatics, 23(2), Jan 2007, e116-22.
• [24] Górecki, P., Tiuryn, J.: URec: a system for unrooted reconciliation, Bioinformatics, 23(4), Feb 2007, 511-512.
• [25] Guig´o, R., Muchnik, I. B., Smith, T. F.: Reconstruction of ancient molecular phylogeny, Molecular Phylogenetics and Evolution, 6(2), Oct 1996, 189-213.
• [26] Hallett, M. T., Lagergren, J.: New algorithms for the duplication-loss model, RECOMB, 2000.
• [27] Hallett, M. T., Lagergren, J.: Efficient algorithms for lateral gene transfer problems, RECOMB, 2001.
• [28] Hallett, M. T., Lagergren, J., Tofigh, A.: Simultaneous identification of duplications and lateral transfers, RECOMB, 2004.
• [29] Libeskind-Hadas, R., Charleston, M. A.: On the computational complexity of the reticulate cophylogeny reconstruction problem., J Comput Biol, 16(1), Jan 2009, 105-117.
• [30] Ma, B., Li, M., Zhang, L.: From Gene Trees to Species Trees, SIAM Journal on Computing, 30(3), 2000, 729-752.
• [31] Mirkin, B., Muchnik, I. B., Smith, T. F.: A Biologically Consistent Model for Comparing Molecular Phylogenies, Journal of Computational Biology, 2(4), 1995, 493-507.
• [32] Page, R. D.M.: Maps between trees and cladistic analysis of historical associations among genes, organisms, and areas, Systematic Biology, 43(1), Mar 1994, 58-77.
• [33] Page, R. D. M.: GeneTree: comparing gene and species phylogenies using reconciled trees, Bioinformatics, 14(9), 1998, 819-820.
• [34] Page, R. D. M., Holmes, E. C.: Molecular Evolution: A Phylogenetic Approach, 1 edition,Wiley-Blackwell, Jan 1998.