00000cab a22000003a 4500 UP-99796217608727516 Buklod 20231007234724.0 m |o d | ta 090226s xx d | ||r ||||| || (iLib)UPD-00077096428 DENGII eng Hannenhalli, Sridhar Transforming cabbage into turnip polynomial algorithm for sorting signed permutations by reversals. pp. 1-27 Genomes frequently evolve by reversals &rgr;(i,j) that transform a gene order &pgr;1 ? &pgr;i&pgr;i+1 ? &pgr;j-1&pgr;j ? &pgr;n into &pgr;1 ? &pgr;i&pgr;j-1 ? &pgr;i+1&pgr;j ? &pgr;n. Reversal distance between permutations &pgr; and &sgr;is the minimum number of reversals to transform &pgr; 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 Drosophilia. Analysis of genomes evolving by inversions leads to a combinatorial problem of sorting by reversals studied in detail recently. We study sorting of 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. Computer applications. Life and medical sciences. Biology and genetics. Theory of computation. Computation by abstract devices. Mathematics of computing. Discrete mathematics. Algorithms. Journal of the ACM 46, 1 (1999). FO UPD DENG-II Article