Résumé : L'alignement d'arbres est la généralisation naturelle de la notion classique d'alignement de séquences. Elle est utilisée dans de nombreux domaines, y compris pour la comparaison de structures secondaires d'ARN (ce qui nous intéressera aujourd'hui). Nous allons donc comprendre comment explorer l'espace des alignements d'arbres et comment déduire des algorithmes efficaces pour comparer les ARN. Cet exposé introduit ainsi les notions d'alignement de séquences et d'arbres et décrit le problème d'ambiguïté qui point quand nous voulons générer de manière correcte les alignements d'arbres. Pour résoudre ce problème d'ambiguïté dans le contexte des alignements d'arbres, nous donnons un schéma de décomposition sous la forme de grammaire sans contexte. Cela conduit à de nombreux résultats : propriétés statistiques sur les larges structures d'ARN, algorithmes efficaces d'échantillonnage... Ces travaux, en collaboration avec Cédric Chauve et Yann Ponty, illustrent le fait que la combinatoire peut être un puissant couteau suisse pour traiter des problèmes algorithmiques qui apparaissent dans de nombreux champs appliqués.

Dernière modification : Monday 27 May 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr