title: Alignments of RNA structures.
abstract: 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.
authors.affiliation: 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
authors.forename: Guillaume
authors.initials: G
authors.lastname: Blin
authors.forename: Alain
authors.initials: A
authors.lastname: Denise
authors.forename: Serge
authors.initials: S
authors.lastname: Dulucq
authors.forename: Claire
authors.initials: C
authors.lastname: Herrbach
authors.forename: Hélène
authors.initials: H
authors.lastname: Touzet
mesh_terms: 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
chemical_list: D012313:RNA