Transforming cabbage into turnip

TLDR

Genomes evolve through reversals, and the reversal distance between permutations is the minimal number of such reversals needed to transform one genome into another, making sorting by reversals a key combinatorial problem studied extensively. The study investigates sorting of signed permutations by reversals to model rearrangements in small genomes such as chloroplast or mitochondrial DNA. The authors analyze sorting of signed permutations by reversals, a problem that adequately models rearrangements in small genomes like chloroplast or mitochondrial DNA. We prove a duality theorem explaining the high accuracy of existing approximation algorithms and show that a hidden parameter enables polynomial‑time computation of reversal distance between signed permutations.

Abstract

Genomes frequently evolve by reversals ρ( i,j ) that transform a gene order π 1 … π i π i +1 … π j -1 π j … π n into π 1 … π i π j -1 … π i +1 π j … π n . Reversal distance between permutations π and σis the minimum number of reversals to transform π into Α. 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.