Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 15 décembre 2009 à 14h en B311, Yann Ponty nous parlera de : Repliement de l'ARN : Une approche combinatoire

Résumé : Historiquement, l’ADN et les protéines, aux deux extremités du dogme central de la biologie moléculaire, ont monopolisé l’attention des chercheurs en biologie, délaissant dans un premier temps l’ARN, confinée dans un rôle d’intermédiaire. Cependant, des études menées au cours de la dernière décennie sur les mécanismes de fonctionnement de ce polymère ont révélé une diversité de modes d’actions et un potentiel thérapeutique tels que deux prix Nobels ont été décernés à C. Mello/A. Z. Fire (Médecine 2006) et V. Ramakrishnan/T. A. Steitz/A. E. Yonath (Chimie 2009). À l’échelle nanométrique des interactions moléculaires, il est possible d’analyser la fonction des molécules à travers leur géométrie, ou conformation. Dans le cas de l’ARN, la conformation fonctionnelle d’un ARN résulte de phénomènes d’appariement entre des bases complémentaires, qui provoquent un repliement global de l’ARN. Par ailleurs, des contraintes stériques permettent bien souvent de limiter l’ensemble des conformations possible à des structures simples, les structures secondaires, dans lesquels les appariements considérés sont sans croisement. On assimile alors cet ensemble à un ensemble canonique "de Boltzmann", un des objets de base de la physique statistique, ce qui permet de définir une distribution de probabilité, dite de Boltzmann, sur l’ensemble des structures secondaires réalisables. L’ensemble des conformations d’un ARN est aussi assimilable à un objet combinatoire simple, analogue d’un arbre ou encore d’une séquence bien parenthésée, et pouvant être étudié grâce à l’arsenal de la combinatoire analytique. Après une introduction présentant les problématiques et challenge actuels de la bioinformatique de l’ARN, nous présenterons deux contributions à l’algorithmique des structures d’ARN, reposant sur une vision combinatoire de l’ensemble des conformations. La première consiste en une analyse et une amélioration d’un algorithme d’échantillonnage statistique pour la structure d’ARN. En se basant sur une analogie avec la génération aléatoire par la méthode dite récursive, nous pratiquons une analyse de la complexité moyenne de l’algorithme, et proposons une amélioration algorithmique basée sur un parcours "Boustrophedon" proposé par Flajolet/Zimmermann/Van Cutsem 1994. La deuxième application consiste en l’analyse d’une représentation hierarchique pour l’ensemble de Boltzmann, les RNA Shapes introduites par Giegerich/Voß/Rehmsmeier 2004.. Cette hierarchie de représentations compactes pour la structure d’ARN permet la mise en oeuvre d’approches modulaires pour l’analyse des repliements. Cependant, ces approches exigent parfois une énumération exhaustives des Shapes compatibles avec un ARN, provoquant ainsi une explosion combinatoire qu’il convient de quantifier. Pour cette raison, nous avons modélisé et énuméré celles-ci, obtenant des croissances asymptotiques en $\Theta(A^n/n^{3/2})$ pour ces représentations, avec A=1.8... (resp. A=1.3) pour la représentation la moins (resp. la plus) compacte, à comparer avec A=2.3 pour le nombre de structures secondaires de taille similaire.. Au passage, nous montrons (encore une...) bijection entre le niveau de représentation le plus compact et les mots de Motzkin. Les travaux sur les RNA-Shapes ont été menés en collaboration avec A. Lorenz et P. Clote (Boston College).


Dernière modification : mercredi 06 juillet 2011 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr