Alignments of RNA Structures
- 3 March 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 7 (2) , 309-322
- https://doi.org/10.1109/tcbb.2008.28
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.Keywords
This publication has 26 references indexed in Scilit:
- GenRGenS: software for generating random genomic sequences and structuresBioinformatics, 2006
- The longest common subsequence problem for arc-annotated sequencesJournal of Discrete Algorithms, 2004
- On the computational complexity of 2-interval pattern matching problemsTheoretical Computer Science, 2004
- The longest common subsequence problem for sequences with nested arc annotationsJournal of Computer and System Sciences, 2002
- Computing similarity between RNA structuresTheoretical Computer Science, 2002
- A General Edit Distance between RNA StructuresJournal of Computational Biology, 2002
- Alignment of trees — an alternative to tree editTheoretical Computer Science, 1995
- Comparing multiple RNA secondary structures using tree comparisonsBioinformatics, 1990
- The book thickness of a graphJournal of Combinatorial Theory, Series B, 1979
- The Tree-to-Tree Correction ProblemJournal of the ACM, 1979