On the Approximability of Comparing Genomes with Duplicates

DOI10.1007/978-3-540-77891-2_4zbMath1132.68817MaRDI QIDQ5452150

Guillaume Fertin, Irena Rusu, Sébastien Angibaud

Publication date: 25 March 2008

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

zbMATH Keywords

genome rearrangement; common intervals; conserved intervals; breakpoints; adjacencies; duplicates; APX-Hardness

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

92D15: Problems related to evolution

92D10: Genetics and epigenetics

68W25: Approximation algorithms

92-08: Computational methods for problems pertaining to biology

Related Items

Extending common intervals searching from permutations to sequences, The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated

Cites Work

• Unnamed Item
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• Genomic distances under deletions and insertions
• Non-breaking Similarity of Genomes with Gene Repetitions
• Genomes Containing Duplicates Are Hard to Compare
• The Approximability of the Exemplar Breakpoint Distance Problem
• Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
• Algorithms – ESA 2005
• Computing and Combinatorics
• Algorithms and Data Structures