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

DOI10.1016/j.tcs.2015.04.036zbMath1332.68286OpenAlexW599463929MaRDI QIDQ897944

Haitao Jiang, Binhai Zhu, Lusheng Wang, 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)

Related Items (1)

A 1.375-approximation algorithm for unsigned translocation sorting

Cites Work

• An \(O(n^{3/2}\sqrt {\log (n)})\) algorithm for sorting by reciprocal translocations
• On the complexity of unsigned translocation distance
• Improved approximation for breakpoint graph decomposition and sorting by reversals
• A further improved approximation algorithm for breakpoint graph decomposition
• A 1.75-approximation algorithm for unsigned translocation distance
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Combinatorial Pattern Matching
• Polynomial-time algorithm for computing translocation distance between genomes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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