Sujets de stage de recherche 2011

Ce sujet concerne les chevauchements entre mots. Deux mots se chevauchent si l'un a un suffixe egal à un préfixe de l'autre. Ainsi, deux occurrences de ces mots dans un texte peuvent se chevaucher. Si l'on note les décalages d'un mot qui permettent ces chevauchements, où un décalage est un entier compris entre 0 et la longueur n du mot, on obtient un sous-ensemble de {0, …, n-1}. Cependant, tout sous-ensemble n'est pas nécessairement l'ensemble des chevauchements d'un mot. On se pose donc les questions de la caractérisation de ces sous-ensembles, de leur énumération, de leur combinatoire. L'ensemble des chevauchements peut être noté sous la forme du vecteur binaire de longueur $n$, nommé corrélation, où l'élément $i$ indique si l'entier $i$ appartient à l'ensemble. Dans le domaine de la combinatoire des mots, on appelle ses décalages des périodes du mot. De même, si l'on étudie les possibles chevauchements entre un mot avec lui même on parle d'autocorrélations. Un résultat surprenant est que l'ensemble des autocorrélations pour les mots de longueur $n$ ne dépend pas de l'alphabet (si bien sûr l'alphabet est de cardinal $>1$ !), cf [Guibas & Odlyzko 81].

Exemple: Soit le mot $U := abracadabra$ de longueur $10$. Son autocorrélation est "10000001001" et correspond à l'ensemble {0, 7, 10}.
Exemple: Soit le mot $V := ababababab$ de longueur $9$. Son autocorrélation est "1010101010" et correspond à l'ensemble {0, 2, 4, 6, 8}. Evidemment le mot "bababababa" aura la même autocorrélation.

Ainsi, se pose la question de la population d'une autocorrélation $v$ : de l'ensemble des mots de même longueur que $v$, sur un alphabet donné, et tels que leur autocorrélation égale $v$.

La combinatoire des autocorrélations a été étudiée dans [Rivals & Rahmann, 2003], où diverses propriétés combinatoires, un algorithme d'énumération, ainsi qu'un algorithme d'échatillonage aléatoire sont présentés. Une étude similaire sur les corrélations semble possible et peut être entammée dans un stage de recherche à différents niveaux du cursus.

Applications : les autocorrélations et corrélations servent à étudier les propriétés statistiques des occurrences de mots dans les textes : probabilité d'occurrence, de non occurrence, temps d'attente avant la première occurrence. Ils servent aussi à explorer la statistique du vocabulaire d'un texte, c'est à dire de tous ses mots de longueur $n$ pour un entier $n$ donné : par exemple le nombre de mots manquants dans un texte, ou encore le nombre de mots communs à deux textes [Rahmann & Rivals, 2003]. Ces questions sont elles-mêmes liées à la complexité des textes, à des problèmes de classification, de distance entre textes, etc. En outre les corrélations importent pour l'étude des patterns binaires dans les séries des jeux à pile ou face, questions sur lesquelles subsistent des interrogations fondamentales [Delahaye JP, Pour la science, 2011].

L'arbre des suffixes est un structure de données pour indexer les facteurs, aussi appelés sous-mots, d'un texte. S'il existe des algorithmes pour construire l'arbre des suffixe d'un texte T, peu de résultats nous informent sur la caractérisation des arbres des suffixes. Par caractérisation, nous entendons la possibilité de reconnaître si une structure arborescente donnée est un arbre des suffixes d'au moins un mot. Généralement la question de la caractérisation s'accompagne de celle de l'énumération de toutes les structures d'une taille donnée. Une autre question liée concerne les mots qui correspondent à une structure donnée.

Nicolas Philippe a étudié entre autres cette question de la caractérisation durant son mémoire de M2 en (2007) sous la direction de Thierry Lecroq (Univ. de Rouen). Cependant la question reste en suspens. Depuis, nous n'avons eu connaissance d'aucun autre travail sur cette question. Nous proposons comme sujet de poursuivre cette étude pour poursuivre l'exploration des propriétés combinatoires des arbres des suffixes.

On se propose d'étudier comment compresser la structure de données d'indexation nommée Gk arrays et décrite recemment dans [Philippe et al. 2011].

Cf. fichier descriptif http://www2.lirmm.fr/~rivals/M2R/SUJETS/Indexing-internship-Rivals.pdf

Bioinformatique, génomique comparative, comparaison multiples de génomes complets, alignements, transfert d'annotation
Encadrants: E. Rivals (rivals-AT-lirmm.fr), A. Mancheron (mancheron-AT-lirmm.fr) (remplacer -AT- par arobase )
Pré-requis: goût pour l'algorithmique, programmation, aucun pré-requis en biologie
Parcours: tous.
Savoir faire: algorithmique, structure de données évoluées, développement, évaluation.