Chaînes de Markov et absorption. Application à l’algorithme de Fu en génomique

Résumé

Cet article est motivé par la recherche de mots ou de motifs exceptionnellement rares ou exceptionnellement présents dans une séquence d’ADN chromosomique. Cette approche permettra en effet de découvrir des motifs ayant un rôle biologique néfaste ou bénéfique pour l’organisme qui le porte. On modélise alors la séquence par une chaîne de Markov (CM) et l’approche classique cherche l’espérance et la variance du nombre N(W) d’occurences du mot W. Nous développons ici une approche duale, déterminant l’espérance et la variance du temps T(W) entre deux occurrences deW. Ceci s’appuie sur une CM auxilliaire dont les états sont les préfixes deW et T(W) est alors le temps que met cette CM pour atteindre le mot completW. L’étude de l’absoption d’une CM est, pour ce faire, présentée en détail.