Hard problems in similarity searching

DOI10.1016/j.dam.2004.06.003zbMath1077.68034OpenAlexW2122887143MaRDI QIDQ1885825

Christophe Moan, Irena Rusu

Publication date: 12 November 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.06.003

zbMATH Keywords

Parameterized complexityNP-complexity

Mathematics Subject Classification ID

Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational methods for problems pertaining to biology (92-08)

Cites Work

• On the complexity of finding common approximate substrings.
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• Finding similar regions in many strings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Hard problems in similarity searching