On the complexity of unsigned translocation distance

DOI10.1016/J.TCS.2005.09.078zbMath1086.68047OpenAlexW2113659505MaRDI QIDQ818147

Daming Zhu, Lusheng Wang

Publication date: 24 March 2006

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

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

zbMATH Keywords

NP-hardnessinapproximabilityunsigned translocation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10)

Related Items (9)

A NOTE ON COMPLEXITY OF GENETIC MUTATIONS ⋮ Can a breakpoint graph be decomposed into none other than 2-cycles? ⋮ A 1.75-approximation algorithm for unsigned translocation distance ⋮ A 1.375-approximation algorithm for unsigned translocation sorting ⋮ A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations ⋮ Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling ⋮ A 14/11-approximation algorithm for sorting by short block-moves ⋮ Inapproximability of maximal strip recovery ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics

Cites Work

• Transforming cabbage into turnip
• Genome Rearrangements and Sorting by Reversals
• Combinatorial Pattern Matching
• Polynomial-time algorithm for computing translocation distance between genomes
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of unsigned translocation distance