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 rearrangementcommon intervalsconserved intervalsbreakpointsadjacenciesduplicatesAPX-Hardness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15) Genetics and epigenetics (92D10) Approximation algorithms (68W25) Computational methods for problems pertaining to biology (92-08)

Related Items (2)

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

This page was built for publication: On the Approximability of Comparing Genomes with Duplicates