On the Approximability of Comparing Genomes with Duplicates
From MaRDI portal
Publication:5452150
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)
genome rearrangement; common intervals; conserved intervals; breakpoints; adjacencies; duplicates; APX-Hardness
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