On the Approximability of Comparing Genomes with Duplicates
From MaRDI portal
Publication:3627965
DOI10.7155/jgaa.00175zbMath1170.68049MaRDI 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
approximation algorithms; APX-hardness; common intervals; conserved intervals; breakpoints; genome rearrangements; adjacencies; duplicate genes
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
Genomic Scaffold Filling: A Progress Report, Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling, A Retrospective on Genomic Preprocessing for Comparative Genomics, The Potential of Family-Free Genome Comparison, Computing the Rearrangement Distance of Natural Genomes, Tandem Duplications, Segmental Duplications and Deletions, and Their Applications, A 1.5-approximation algorithm for two-sided scaffold filling, Repetition-free longest common subsequence of random sequences, Exemplar or matching: modeling DCJ problems with unequal content genome data, On the approximability of the exemplar adjacency number problem for genomes with gene repetitions, New applications of interval generators to genome comparison, Common intervals and permutation reconstruction from \textit{MinMax}-betweenness constraints, On the solution bound of two-sided scaffold filling, Parameterized complexity of two-interval pattern problem, Computing a consensus trajectory in a vehicular network, \textit{MinMax}-profiles: a unifying view of common intervals, nested common intervals and conserved intervals of \(K\) permutations, A NOTE ON COMPLEXITY OF GENETIC MUTATIONS, Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem, The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated
