A factor-(1.408+) approximation for sorting unsigned genomes by reciprocal translocations

DOI10.1016/J.TCS.2015.04.036MaRDI QIDQ897944zbMATH OpenOpenAlexFDO

Authors Haitao Jiang, Lusheng Wang, Binhai Zhu, Daming Zhu

Publication date 8 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.04.036

zbMATH Keywords

approximation algorithmsNP-hardnessgenome rearrangementcomputational genomics

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Approximation algorithms (68W25)

Recommendations

• A \((1.408+\varepsilon )\)-approximation algorithm for sorting unsigned genomes by reciprocal translocations
• A new approximation algorithm for unsigned translocation sorting
• A 1.375-approximation algorithm for unsigned translocation sorting
• An approximation algorithm for sorting by reversals and transpositions
• A 1.75-approximation algorithm for unsigned translocation distance

Cites work

• scientific article; zbMATH DE number 1003268 (Why is no real title available?)
• scientific article; zbMATH DE number 1947393 (Why is no real title available?)
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• scientific article; zbMATH DE number 910919 (Why is no real title available?)
• A 1.75-approximation algorithm for unsigned translocation distance
• A further improved approximation algorithm for breakpoint graph decomposition
• An \(O(n^{3/2}\sqrt {\log (n)})\) algorithm for sorting by reciprocal translocations
• Combinatorial Pattern Matching
• Improved approximation for breakpoint graph decomposition and sorting by reversals
• On the complexity of unsigned translocation distance
• Polynomial-time algorithm for computing translocation distance between genomes
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions

Cited in

(5)

• A \((1.408+\varepsilon )\)-approximation algorithm for sorting unsigned genomes by reciprocal translocations
• Signed genome rearrangement by reversals and transpositions: Models and approximations
• A randomized FPT approximation algorithm for maximum alternating-cycle decomposition with applications
• A 1.375-approximation algorithm for unsigned translocation sorting
• Exact and approximation algorithms for the contiguous translocation distance problem

This page was built for publication: A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897944)