Lossless seeds for searching short patterns with high error rates

Vroland, Christophe; Salson, Mikael; Touzet, Helene

Type de document :

Communication dans un congrès avec actes

Titre :

Lossless seeds for searching short patterns with high error rates

Auteur(s) :

Vroland, Christophe [Auteur]
Génétique et évolution des populations végétales [GEPV]
Bioinformatics and Sequence Analysis [BONSAI]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Salson, Mikael [Auteur]

Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Bioinformatics and Sequence Analysis [BONSAI]
Touzet, Helene [Auteur]

Bioinformatics and Sequence Analysis [BONSAI]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]

Titre de la manifestation scientifique :

International Workshop On Combinatorial Algorithms

Ville :

Duluth

Pays :

Etats-Unis d'Amérique

Date de début de la manifestation scientifique :

2014-10

Discipline(s) HAL :

Informatique [cs]/Algorithme et structure de données [cs.DS]

Résumé en anglais : [en]

We address the problem of approximate pattern matching using the Levenshtein distance. Given a text T and a pattern P , find alllocations in T that differ by at most k errors from P . For that purpose, we propose a filtration ...
Lire la suite >We address the problem of approximate pattern matching using the Levenshtein distance. Given a text T and a pattern P , find alllocations in T that differ by at most k errors from P . For that purpose, we propose a filtration algorithm that is based on a novel type of seeds,combining exact parts and parts with a fixed number of errors. Experimental tests show that the method is specifically well-suited for short patterns with a large number of errorsLire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :