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

Recommendations

• Algorithms and Computation
• A 1.75-approximation algorithm for unsigned translocation distance
• A 1.375-approximation algorithm for unsigned translocation sorting
• Sorting by transpositions is difficult
• A new approximation algorithm for unsigned translocation sorting

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)

Cites Work

• Title not available (Why is that?)
• Transforming cabbage into turnip
• Title not available (Why is that?)
• Polynomial-time algorithm for computing translocation distance between genomes
• Genome Rearrangements and Sorting by Reversals
• Title not available (Why is that?)
• Combinatorial Pattern Matching

Cited In (15)

• Algorithms and Computation
• A retrospective on genomic preprocessing for comparative genomics
• Computing the tandem duplication distance is NP-hard
• Inapproximability of maximal strip recovery
• A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations
• The transposition median problem is NP-complete
• A note on complexity of genetic mutations
• Structural, Syntactic, and Statistical Pattern Recognition
• Exact and approximation algorithms for the contiguous translocation distance problem
• A 1.375-approximation algorithm for unsigned translocation sorting
• On the computational complexity of closest genome problems
• A 14/11-approximation algorithm for sorting by short block-moves
• Can a breakpoint graph be decomposed into none other than 2-cycles?
• Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling
• 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)