To cut…or not to cut (applications of comparative physical maps in molecular evolution)

Studies of genomes evolving by rearrangements lead to cornbinatorial problem of sorting permutation by reversals. Kececioglu and Sankoff conjectured that for every permutation there exists an optimal sorting by reversals which does not cut long strips in the permutation. We prove this conjecture and further study the problem of sorting by reversals for permutations without strips of size one, called singletons. We give a polynomial algorithm for sorting such permutations, thus demonstrating that singletons present the major obstacle on the way towards an efficient algorithm for sorting by reversals. Using this result, we prove the strong Kecedoglu-Sankoff conjecture: for every permutation there exists an optimal sorting by reversals that never increases the number of breakpoints. Finally we present a new algorithm for sorting by reversals based on the notion of the spin of a permutation. For permutations with O(log n) singletons the algorithm runs in polynomial time and suggests a desired trade-off of resolution for cross-hybridization physical mapping in molecular evolution studies. We describe applications of this algorithm to analyze rearrangements in maize and green algae, in particular we find a most parsimonious rearrangement scenario for Chlamydomonas moewusii versus Chlamydomonas reinhardtii representing the most complicated known case of rearrangements inmore » organelles.« less