Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement

DOI10.1007/BF01188586zbMath0831.92014OpenAlexW2054600183MaRDI QIDQ1902472

Publication date: 11 January 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01188586

zbMATH Keywords

linear programming shortest paths edit distance random permutations genome rearrangements sorting by reversals greedy approximation algorithm experimental analysis of algorithms branch-and-bound exact algorithm chromosome inversions maximum-weight matchings mitochondrial genomes random reversals shortest series of reversals

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Computational methods for problems pertaining to biology (92-08)

Related Items (48)

Efficient algorithms for multichromosomal genome rearrangements. ⋮ A topological framework for signed permutations ⋮ The spectral gap of graphs arising from substring reversals ⋮ A 3.5-Approximation Algorithm for Sorting by Intergenic Transpositions ⋮ Heuristics for Reversal Distance Between Genomes with Duplicated Genes ⋮ APPROXIMATE BLOCK SORTING ⋮ On sorting unsigned permutations by double-cut-and-joins ⋮ Entropic fluctuations in DNA sequences ⋮ Estimate the distance of genome rearrangements by reversals ⋮ Optimal algorithms for uncovering synteny problem ⋮ Two-sided Group Digraphs and Graphs ⋮ Structural properties and tractability results for linear synteny ⋮ Topological morphing of planar graphs ⋮ Quantum routing in planar graph using perfect state transfer ⋮ A new approximation algorithm for sorting of signed permutations ⋮ Quotient geometric crossovers and redundant encodings ⋮ Flipping edge-labelled triangulations ⋮ Girth of pancake graphs ⋮ Edit Distances and Factorisations of Even Permutations ⋮ Sorting permutations with transpositions in \(O(n^3)\) amortized time ⋮ Approximating Shortest Connected Graph Transformation for Trees ⋮ Maximum likelihood estimates of rearrangement distance: implementing a representation-theoretic approach ⋮ Pancake flipping and sorting permutations ⋮ Reconstruction of permutations distorted by reversal errors ⋮ Sorting permutations by block-interchanges ⋮ Some problems on Cayley graphs ⋮ The `Butterfly effect' in Cayley graphs with applications to genomics. ⋮ Maximum cycle packing in Eulerian graphs using local traces ⋮ Packing Euler graphs with traces ⋮ Signed genome rearrangement by reversals and transpositions: Models and approximations ⋮ On sorting by 3-bounded transpositions ⋮ A sparse dynamic programming algorithm for alignment with non-overlapping inversions ⋮ A DISCRIMINATION MEASURE FOR PHYLOGENETIC TREE CONSTRUCTION ⋮ Polynomial-time algorithm for computing translocation distance between genomes ⋮ Sorting a permutation by best short swaps ⋮ An approximation algorithm for sorting by reversals and transpositions ⋮ A 2-approximation algorithm for genome rearrangements by reversals and transpositions ⋮ An Audit Tool for Genome Rearrangement Algorithms ⋮ Bounding prefix transposition distance for strings and permutations ⋮ On the complexity and approximation of syntenic distance ⋮ Sorting by bounded block-moves ⋮ Reconstructing a history of recombinations from a set of sequences ⋮ An improved genetic algorithm for problem of genome rearrangement ⋮ Unnamed Item ⋮ Bacterial phylogeny in the Cayley graph ⋮ Kernelization of Whitney Switches ⋮ Kernelization of Whitney Switches ⋮ On Sorting by 3-Bounded Transpositions

Cites Work

This page was built for publication: Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement