On the Approximability of Comparing Genomes with Duplicates

DOI10.7155/jgaa.00175zbMath1170.68049OpenAlexW2160388718MaRDI QIDQ3627965

Stéphane Vialette, Guillaume Fertin, Annelyse Thévenin, Irena Rusu, Sébastien Angibaud

Publication date: 19 May 2009

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/55913

zbMATH Keywords

approximation algorithmsAPX-hardnesscommon intervalsconserved intervalsbreakpointsgenome rearrangementsadjacenciesduplicate genes

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 (19)

A NOTE ON COMPLEXITY OF GENETIC MUTATIONS ⋮ Computing the Rearrangement Distance of Natural Genomes ⋮ Tandem Duplications, Segmental Duplications and Deletions, and Their Applications ⋮ Repetition-free longest common subsequence of random sequences ⋮ Exemplar or matching: modeling DCJ problems with unequal content genome data ⋮ Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem ⋮ On the approximability of the exemplar adjacency number problem for genomes with gene repetitions ⋮ New applications of interval generators to genome comparison ⋮ Genomic Scaffold Filling: A Progress Report ⋮ Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling ⋮ \textit{MinMax}-profiles: a unifying view of common intervals, nested common intervals and conserved intervals of \(K\) permutations ⋮ Common intervals and permutation reconstruction from \textit{MinMax}-betweenness constraints ⋮ The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated ⋮ On the solution bound of two-sided scaffold filling ⋮ Parameterized complexity of two-interval pattern problem ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics ⋮ The Potential of Family-Free Genome Comparison ⋮ Computing a consensus trajectory in a vehicular network ⋮ A 1.5-approximation algorithm for two-sided scaffold filling

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