Alignments of RNA structures.
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.
Blin
Guillaume
G
Institut Gaspard Monge, UMR 8049 CNRS, Université Paris-Est, 5 Bd Descartes-Champs sur Marne, 77454 Marne La Vallée Cedex 2, France. gblin@univ-mlv.fr
Denise
Alain
A
Dulucq
Serge
S
Herrbach
Claire
C
Touzet
Hélène
H
D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D005798:Genes, Bacterial / Q000235:genetics; D008957:Models, Genetic; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*; D016415:Sequence Alignment; D012984:Software
D012313:RNA