14h00: Séquences d'ADN et arbres digitaux. Brigitte.Chauvin, Laboratoire LAMA, UVSQ.

Il est possible de représenter une séquence d'ADN par une suite (T_n)_n d'arbres digitaux, vue comme un processus de Markov à valeurs arbres. Ceux-ci peuvent être des tries (trie des suffixes) ou bien des arbres digitaux de recherche (DST). Du coup, les habituelles variables de coût (hauteur, niveau de saturation, profondeur d'insertion, ...) gagnent une nouvelle interprétation. Du strict point de vue de l'étude algorithmique, celle-ci est délicate (donc intéressante) car les mots que l'on insère dans les arbres successifs sont fortement dépendants entre eux. Les méthodes utilisées reposent alors sur l'autocorrelation des motifs et sur des hypothèses de mélange. Un cadre agréable et général pourrait être celui des sources dynamiques.