On the complexity of unsigned translocation distance

DOI10.1016/J.TCS.2005.09.078zbMATH Open1086.68047OpenAlexW2113659505MaRDI QIDQ818147FDOQ818147

Authors 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

inapproximabilityNP-hardnessunsigned translocation

Mathematics Subject Classification ID

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

Recommendations

• Algorithms and Computation
• A 1.75-approximation algorithm for unsigned translocation distance
• A 1.375-approximation algorithm for unsigned translocation sorting
• A new approximation algorithm for unsigned translocation sorting

Cites work

• scientific article; zbMATH DE number 871927 (Why is no real title available?)
• scientific article; zbMATH DE number 910919 (Why is no real title available?)
• scientific article; zbMATH DE number 6472609 (Why is no real title available?)
• Combinatorial Pattern Matching
• Genome Rearrangements and Sorting by Reversals
• Polynomial-time algorithm for computing translocation distance between genomes
• Transforming cabbage into turnip

Cited in

(15)

• The transposition median problem is NP-complete
• A note on complexity of genetic mutations
• Exact and approximation algorithms for the contiguous translocation distance problem
• A 1.375-approximation algorithm for unsigned translocation sorting
• Inapproximability of maximal strip recovery
• Computing the tandem duplication distance is NP-hard
• On the computational complexity of closest genome problems
• Can a breakpoint graph be decomposed into none other than 2-cycles?
• 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
• Algorithms and Computation
• Structural, Syntactic, and Statistical Pattern Recognition
• A retrospective on genomic preprocessing for comparative genomics
• A 14/11-approximation algorithm for sorting by short block-moves
• A 1.75-approximation algorithm for unsigned translocation distance

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

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