A 2-approximation algorithm for genome rearrangements by reversals and transpositions
From MaRDI portal
Publication:1274604
DOI10.1016/S0304-3975(98)00092-9zbMath0915.68033MaRDI QIDQ1274604
Hal Sudborough, Qian-Ping Gu, Shietung Peng
Publication date: 12 January 1999
Published in: Theoretical Computer Science (Search for Journal in Brave)
lower boundapproximation algorithmssorting of permutationssequence comparisoncomputational molecular biologygenome rearrangements
Searching and sorting (68P10) Computing methodologies and applications (68U99) Parallel algorithms in computer science (68W10)
Related Items (21)
A NOTE ON COMPLEXITY OF GENETIC MUTATIONS ⋮ APPROXIMATE BLOCK SORTING ⋮ Optimal algorithms for uncovering synteny problem ⋮ Structural properties and tractability results for linear synteny ⋮ A new approximation algorithm for sorting of signed permutations ⋮ An approximation algorithm for genome sorting by reversals to recover all adjacencies ⋮ A 2.25-Approximation Algorithm for Cut-and-Paste Sorting of Unsigned Circular Permutations ⋮ Conditional fractional matching preclusion for burnt pancake graphs and pancake-like graphs (extended abstract) ⋮ A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations ⋮ The (conditional) matching preclusion for burnt pancake graphs ⋮ Multi-break rearrangements and chromosomal evolution ⋮ Pancake flipping and sorting permutations ⋮ Approximation algorithms for sorting by length-weighted prefix and suffix operations ⋮ Expected number of breakpoints after \(t\) random reversals in genomes with duplicate genes ⋮ Uniquely pressable graphs: characterization, enumeration, and recognition ⋮ A simpler and faster 1.5-approximation algorithm for sorting by transpositions ⋮ An algorithm for reversal median problem ⋮ Signed genome rearrangement by reversals and transpositions: Models and approximations ⋮ An approximation algorithm for sorting by reversals and transpositions ⋮ An Audit Tool for Genome Rearrangement Algorithms ⋮ \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.
Cites Work
This page was built for publication: A 2-approximation algorithm for genome rearrangements by reversals and transpositions
