S. Hannenhalli et Pa. Pevzner, Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals, J ACM, 46(1), 1999, pp. 1-27
Genomes frequently evolve by reversals rho(i,j) that transform a gene order
pi(1) ..., pi(i)pi(i+1) ... pi(j-1)pi(j) ... pi(n) into pi(1) ... pi(i)pi(
j-1) ... pi(i+1)pi(j) ... pi(n). Reversal distance between permutations pi
and sigma is the minimum number of reversals to transform pi into sigma Ana
lysis of genome rearrangements in molecular biology started in the late 193
0's, when Dobzhansky and Sturtevant published a milestone paper presenting
a rearrangement scenario with 17 inversions between the species of Drosophi
la. Analysis of genomes evolving by inversions leads to a combinatorial pro
blem of sorting by reversals studied in detail recently. We study sorting o
f signed permutations by reversals, a problem that adequately models rearra
ngements in small genomes like chloroplast or mitochondrial DNA. The previo
usly suggested approximation algorithms for sorting signed permutations by
reversals compute the reversal distance between permutations with an astoni
shing accuracy for both simulated and biological data. We prove a duality t
heorem explaining this intriguing performance and show that there exists a
"hidden" parameter that allows one to compute the reversal distance between
signed permutations in polynomial time.