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

• 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.

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap -- Bioinformatik (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Bioinformatics (hsv//eng)

Keyword

algorithm

article

controlled study

Cyanobacterium

evolution

gene deletion

gene duplication

gene insertion

gene rearrangement

genetic recombination

horizontal gene transfer

molecular phylogeny

nonhuman

plant

plastid

point mutation

priority journal

Proteobacteria

sequence alignment

simulation

Algorithms

Bacterial Proteins

Base Sequence

Chromosome Mapping

Computer Simulation

DNA Mutational Analysis

Evolution

Molecular

Gene Rearrangement

T-Lymphocyte

Gene Transfer

Horizontal

Models

Genetic

Molecular Sequence Data

Plant Proteins

Sequence Analysis

DNA

Variation (Genetics)

Publication and Content Type

ref (subject category)

art (subject category)