An edit distance between RNA stem-loops
© Springer-Verlag



Valentin Guignon, Cedric Chauve et Sylvie Hamel



Résumé :


      Cet article propose un algorithme polynomial, en temps et en espace, pour calculer une distance et un alignement optimal entre deux éléments de structures secondaires d'ARN ne contenant pas de boucles multiples, lorsque certaines contraintes sont imposées sur les alignements possibles. Ces contraintes nous permettent de considérer un ensemble très complet d'opérations d'édition sur les paires de bases et les nucléotides non appariés. Notre approche vise la détection d'éléments rapprochés entre structures secondaires d'ARN et est basée sur le calcul d'une table de programmation dynamique.