### Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversalsTransforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals

Access Restriction
Subscribed

 Author Hannenhalli, Sridhar ♦ Pevzner, Pavel A. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1999 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Computational biology ♦ Genetics Abstract Genomes frequently evolve by reversals $&rgr;(\textit{i,j})$ that transform a gene order π1 … $π\textit{i}π\textit{i}+1$ … $π\textit{j}-1π\textit{j}$ … $π\textit{n}$ into π1 … $π\textit{i}π\textit{j}-1$ … $π\textit{i}+1π\textit{j}$ … $π\textit{n}.$ Reversal distance between permutations π and &sgr;is the minimum number of reversals to transform π into &Agr;. Analysis of genome rearrangements in molecular biology started in the late 1930's, when Dobzhansky and Sturtevant published a milestone paper presenting a rearrangement scenario with 17 inversions between the species of $\textit{Drosophilia}.$ Analysis of genomes evolving by inversions leads to a combinatorial problem of sorting by reversals studied in detail recently. We study sorting of $\textit{signed}$ permutations by reversals, a problem that adequately models rearrangements in a small genomes like chloroplast or mitochondrial DNA. The previously suggested approximation algorithms for sorting signed permutations by reversals compute the reversal distance between permutations with an astonishing accuracy for both simulated and biological data. We prove a duality theorem 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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1999-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 46 Issue Number 1 Page Count 27 Starting Page 1 Ending Page 27

#### Open content in new tab

Source: ACM Digital Library