Stéphane Vialette (LRI)

Nous considérons dans cet exposé des graphes munis d'une numérotation linéaire des sommets. En accord avec cet ordre linéaire, si deux arêtes sont disjointes (par les sommets) alors l'une "précède" l'autre, l'une est "dans" l'autre ou elles se "croisent". Dans le contexte de l'inférence de structures secondaires dans les ARN non codants, Davydov et Batzoglou ont récemment étudié (CPM 2004) le problème de la recherche dans un ensemble de graphes linéaires d'un couplage, i.e., un motif, commun sans croisements. L'idée, simple, est ici de représenter une séquence d'ARN par un graphe linéaire, l'ordre linéaire étant naturellement donné par l'enchaînement des lettres le long de la séquence, dont les arêtes décrivent tous les appariements possibles entre les lettres. Après un rappel des principaux résultats concernant ce problème, nous présenterons une généralisation qui permet d'aborder les pseudo-noeuds dans les structures d'ARN ; il conviendra ici d'étudier séparément les complexités de tous les motifs communs autorisés (avec croisements, avec précédences, ...). Nous insisterons en particulier sur l'approximation en temps polynomial et sur les liens avec la recherche de motifs dans les permutations. Nous terminerons en discutant quelques problèmes ouverts.