Inferring horizontal transfers in the presence of rearrangements by the minimum evolution criterion

• Published in: Bioinformatics 2008-03, Vol.24 (6), p.826-832
• Main Authors: Birin, Hadas, Gal-Or, Zohar, Elias, Isaac, Tuller, Tamir
• Format: Article
• Language: English
• Subjects: algorithm; Algorithms; Bacterial Proteins; Bacterial Proteins - genetics; Base Sequence; Biological and medical sciences; Chromosome Mapping; Chromosome Mapping - methods; Computer Simulation; controlled study; Cyanobacterium; DNA; DNA Mutational Analysis; DNA Mutational Analysis - methods; evolution; Evolution, Molecular; Fundamental and applied biological sciences. Psychology; gene deletion; gene duplication; gene insertion; gene rearrangement; Gene Rearrangement, T-Lymphocyte - genetics; Gene Transfer; Gene Transfer, Horizontal - genetics; General aspects; Genetic; genetic recombination; Genetic Variation - genetics; Horizontal; horizontal gene transfer; Mathematics in biology. Statistical analysis. Models. Metrology. Data processing in biology (general aspects); Models, Genetic; Molecular; molecular phylogeny; Molecular Sequence Data; nonhuman; plant; Plant Proteins; Plant Proteins - genetics; plastid; point mutation; priority journal; Proteobacteria; sequence alignment; Sequence Alignment - methods; Sequence Analysis; Sequence Analysis, DNA - methods; simulation; T-Lymphocyte; Variation (Genetics)
• ISSN: 1367-4803; 1367-4811; 1460-2059; 1367-4811
• DOI: 10.1093/bioinformatics/btn024

Motivation: The evolution of viruses is very rapid and in addition to local point mutations (insertion, deletion, substitution) it also includes frequent recombinations, genome rearrangements and horizontal transfer of genetic materials (HGTS). Evolutionary analysis of viral sequences is therefore a complicated matter for two main reasons: First, due to HGTs and recombinations, the right model of evolution is a network and not a tree. Second, due to genome rearrangements, an alignment of the input sequences is not guaranteed. These facts encourage developing methods for inferring phylogenetic networks that do not require aligned sequences as input. Results: In this work, we present the first computational approach which deals with both genome rearrangements and horizontal gene transfers and does not require a multiple alignment as input. We formalize a new set of computational problems which involve analyzing such complex models of evolution. We investigate their computational complexity, and devise algorithms for solving them. Moreover, we demonstrate the viability of our methods on several synthetic datasets as well as four biological datasets. Availability: The code is available from the authors upon request. Contact: [e-mail] Supplementary information: Supplementary data are available at Bioinformatics online.