A fast algorithm for the multiple genome rearrangement problem with weighted reversals and transpositions

Abstract

Background: Due to recent progress in genome sequencing, more and more data for phylogenetic reconstruction based on rearrangement distances between genomes become available. However, this phylogenetic reconstruction is a very challenging task. For the most simple distance measures (the breakpoint distance and the reversal distance), the problem is NP-hard even if one considers only three genomes.

Results: In this paper, we present a new heuristic algorithm that directly constructs a phylogenetic tree w.r.t. the weighted reversal and transposition distance. Experimental results on previously published datasets show that constructing phylogenetic trees in this way results in better trees than constructing the trees w.r.t. the reversal distance, and recalculating the weight of the trees with the weighted reversal and transposition distance. An implementation of the algorithm can be obtained from the authors.

Conclusion: The possibility of creating phylogenetic trees directly w.r.t. the weighted reversal and transposition distance results in biologically more realistic scenarios. Our algorithm can solve today's most challenging biological datasets in a reasonable amount of time.

Figure 1

Adding a node. A new node π can either be added to (a) a node v in the tree or (b) to a point s in a cloud of an edge (v, v'). In the latter case, we have to split the edge (v, v') into two edges (v, s) and (s, v'). Clouds are removed/generated accordingly.

Figure 2

Improving the tree topology. The subtrees T₁ and T₂ are reconnected by an edge from s to v₂, where s ∈ Cloud(v₁, ${v^{\prime }}_1$) and v₂ ∈ V₂. The edge (v₁, ${v^{\prime }}_1$) must be split into two edges (v₁, s) and (s, ${v^{\prime }}_1$) before the new edge (s, v₂) is added. Clouds are removed/generated accordingly.

Figure 3

Variance of the Campanulaceae dataset. The results of our algorithm for the Campanulaceae dataset over all runs as box plots. For each improvement strategy, also the average running time per run is provided. (a) contains the results for the weight ratio 1:2, (b) for the weight ratio 1:1.5, and (c) for the weight ratio 1:1.

Figure 4

Variance of the metazoan dataset. The results of our algorithm for the metazoan dataset over all runs as box plots. For each improvement strategy, also the average running time per run is provided. (a) contains the results for the weight ratio 1:2, (b) for the weight ratio 1:1.5, and (c) for the weight ratio 1:1.

Figure 5

Variance of the protostomes dataset. The results of our algorithm for the protostomes dataset over all runs as box plots. For each improvement strategy, also the average running time per run is provided. (a) contains the results for the weight ratio 1:2, (b) for the weight ratio 1:1.5, and (c) for the weight ratio 1:1.