Ent?te

Logo du LIFL

Depuis le 1er janvier 2015 le LIFL et le LAGIS forment le laboratoire CRIStAL

  1. Actualités

Séminaire de

Cédric Saule

10 juin 2010
Amphi Turing, Bât M3

énumération de structures d'ARN avec pseudonoeud

En 2004, Anne Condon et ses co-auteurs dressèrent une classification des algorithmes exactes de prédiction de structures ARN ab initio avec pseudonoeuds basée sur le degré de généralité des structures qu'ils peuvent prédire. Ils montrèrent que ces classes sont en relation d'inclusion. Nous proposons d'évaluer le compromis entre complexité en temps et le nombre de structures prédictibles par chaqu'un de ces algorithmes. En particulier nous montrerons qu'il existe une bijection entre les structures de la classe de Lyngso et Pedersen à n arcs et les  cartes planaires enracinées sans isthmes à un ou deux sommets et n arêtes.
Nous montrerons aussi que ces structures peuvent être codées par des langages algébriques non ambigüs. Nous en déduisons la série génératrice et le comportement asymptotique du nombre de structures.  Nous ajouterons également deux classes de structures à cette classification.

Nous présenterons également une classe d'équivalence pour les structures avec pseudonoeud  et nous montrerons que ces structures sont en bijection avec les arbres ternaires.

Ours

UMR 8022 - Laboratoire d'Informatique Fondamentale de Lille - Copyright © 2012 Sophie TISON - Crédits & Mentions légales

Page respectant XHTML et CSS.

Pour tout commentaire / Comments and remarks : webmaster