A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals

DOI10.1137/S0097539798334207zbMath1112.68405DBLPjournals/siamcomp/KaplanST99WikidataQ56565188 ScholiaQ56565188MaRDI QIDQ4943850

Ron Shamir, Haim Kaplan, Robert Endre Tarjan

Publication date: 19 March 2000

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

computational molecular biologysorting permutationsreversal distance

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Biochemistry, molecular biology (92C40)

Related Items (28)

Efficient algorithms for multichromosomal genome rearrangements. ⋮ The complexity of genome rearrangement combinatorics under the infinite sites model ⋮ A 1.75-approximation algorithm for unsigned translocation distance ⋮ Advances on sorting by reversals ⋮ How to sort by walking and swapping on paths and trees ⋮ Sorting by reversals and the theory of 4-regular graphs ⋮ A 1.375-approximation algorithm for unsigned translocation sorting ⋮ An efficient algorithm for one-sided block ordering problem under block-interchange distance ⋮ Sorting signed permutations by reversals using link-cut trees ⋮ A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations ⋮ A linear time algorithm for the inversion median problem in circular bacterial genomes ⋮ An \(O(n^{3/2}\sqrt {\log (n)})\) algorithm for sorting by reciprocal translocations ⋮ Patterns of simple gene assembly in ciliates ⋮ Decision problem for shuffled genes ⋮ A very elementary presentation of the Hannenhalli-Pevzner theory ⋮ A simpler and faster 1.5-approximation algorithm for sorting by transpositions ⋮ Sorting signed permutations by reversals, revisited ⋮ A sparse dynamic programming algorithm for alignment with non-overlapping inversions ⋮ An improved algorithm for sorting by block-interchanges based on permutation groups ⋮ Sorting a permutation by best short swaps ⋮ Simple Operations for Gene Assembly ⋮ SUCCESSFUL ELEMENTARY GENE ASSEMBLY STRATEGIES ⋮ SORTING SIGNED PERMUTATIONS BY FIXED-LENGTH REVERSALS ⋮ An improved genetic algorithm for problem of genome rearrangement ⋮ A new linear time algorithm to compute the genomic distance via the double cut and join distance ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics ⋮ General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic ⋮ Generating a random signed permutation with random reversals

This page was built for publication: A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals