Hardness of Optimal Spaced Seed Design

François Nicolas 1 Eric Rivals 1
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Speeding up approximate pattern matching is a line of research in stringology since the 80's. Practically fast approaches belong to the class of filtration algorithms, in which text regions dissimilar to the pattern are excluded (filtered out) in a first step, and remaining regions are compared to the pattern by dynamic programming in a second step. Among the necessary conditions used to test similarity between the regions and the pattern, many require a minimum number of common substrings between them. When only substitutions are taken into account for measuring dissimilarity, it was shown recently that counting spaced subwords instead of substrings improve the filtration efficiency. However, a preprocessing step is required to design one or more patterns, called gapped seeds, for the subwords, depending on the search parameters. The seed design problems proposed up to now differ by the way the similarities to detect are given: either a set of similarities is given in extenso (this is a “region specific” problem), or one wishes to detect all similar regions having at most k substitutions (general detection problem). Several articles exhibit exponential algorithms for these problems. In this work, we provide hardness and inapproximability results for both the region specific and general seed design problems, thereby justifying the exponential complexity of known algorithms. Moreover, we introduce a new formulation of the region specific seed design problem, in which the weight of the seed (i.e., number of characters in the subwords) has to be maximized, and show it is as difficult to approximate than Maximum Independent Set.
Type de document :
Communication dans un congrès
A. Apostolico; M. Crochemore; K. Park. CPM: Combinatorial Pattern Matching, Jun 2005, Jeju City, South Korea. Springer Verlag, 16th Annual Symposium on Combinatorial Pattern Matching, LNCS (3537), pp.144-155, 2005, 〈10.1007/11496656_13〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00106448
Contributeur : Christine Carvalho de Matos <>
Soumis le : lundi 16 octobre 2006 - 08:29:17
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mardi 6 avril 2010 - 19:40:35

Fichier

Identifiants

Collections

Citation

François Nicolas, Eric Rivals. Hardness of Optimal Spaced Seed Design. A. Apostolico; M. Crochemore; K. Park. CPM: Combinatorial Pattern Matching, Jun 2005, Jeju City, South Korea. Springer Verlag, 16th Annual Symposium on Combinatorial Pattern Matching, LNCS (3537), pp.144-155, 2005, 〈10.1007/11496656_13〉. 〈lirmm-00106448〉

Partager

Métriques

Consultations de la notice

222

Téléchargements de fichiers

158