Gabriel Bathie (département M2F, équipe DART) a reçu le prix du meilleur article à la 35ème Annual Symposium on Combinatorial Pattern Matching, qui s’est tenue en juin dernier, à Fukuoka (Japon).
Dans cet article, on s'intéresse à la tâche de recherche interne de motif (en anglais, Internal Pattern Matching, IPM) dans les chaînes de caractères.
Dans ce contexte, on nous donne une suite de lettres, par exemple une suite de A, C, G ou T qui représentent un brin d'ADN, et on doit répondre le plus efficacement possible à des questions de la forme "est-ce que cette sous-partie du brin d'ADN apparaît autre part dans le brin, et si oui, où ?".
L'IPM est une brique de base pour résoudre de nombreux problèmes sur les chaînes de caractères, comme celui de la plus longue sous-chaîne commune ou celui de la recherche circulaire de motifs.
Les algorithmes efficaces pour résoudre IPM nécessitent beaucoup de mémoire sur les grandes chaînes de caractère comme des génomes entier.
Dans cet article, notre contribution principale est un algorithme qui permet de résoudre IPM et dont on peut adapter la consommation mémoire en fonction des ressources disponible tout gardant la meilleure efficacité possible.