Alignments of RNA structures.

Guillaume Blin (1) , Alain Denise (2, 3, 4) , Serge Dulucq (5) , Claire Herrbach (3) , Helene Touzet (6, 7)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 LRI - Laboratoire de Recherche en Informatique
3 IGM - Institut de génétique et microbiologie [Orsay]
4 AMIB - Algorithms and Models for Integrative Biology
5 LaBRI - Laboratoire Bordelais de Recherche en Informatique
6 LIFL - Laboratoire d'Informatique Fondamentale de Lille
7 SEQUOIA - Sequential Learning

We describe a theoretical unifying framework to express the comparison of RNA structures, which we call alignment hierarchy. This framework relies on the definition of common supersequences for arc-annotated sequences and encompasses the main existing models for RNA structure comparison based on trees and arc-annotated sequences with a variety of edit operations. It also gives rise to edit models that have not been studied yet. We provide a thorough analysis of the alignment hierarchy, including a new polynomial-time algorithm and an NP-completeness proof. The polynomial-time algorithm involves biologically relevant edit operations such as pairing or unpairing nucleotides. It has been implemented in a software, called gardenia, which is available at the Web server http://bioinfo.lifl.fr/RNA/gardenia.

Domaines: Biochimie, Biologie Moléculaire; Bio-informatique [q-bio.QM]; Bio-Informatique, Biologie Systémique [q-bio.QM]

Guillaume Blin, Alain Denise, Serge Dulucq, Claire Herrbach, Helene Touzet. Alignments of RNA structures.. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2010, 7 (2), pp.309-322. ⟨10.1109/TCBB.2008.28⟩. ⟨hal-00506348⟩