A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
From MaRDI portal
Publication:4943850
DOI10.1137/S0097539798334207zbMath1112.68405WikidataQ56565188 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)
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
