Alignments of RNA Structures
Alignments of RNA Structures
复制标题
DOI：
10.1109/tcbb.2008.28
复制
发表时间：
2010-04-01
影响因子：
4.5
通讯作者：
Touzet, Helene
中科院分区：
文献类型：
--
作者：
Blin, Guillaume;Denise, Alain;Touzet, Helene
我们描述了一个理论统一的框架来表达RNA结构的比较，我们称之为对齐层次。这个框架依赖于定义的共同超序列的弧注释序列，并包括现有的主要模型的基础上的树和弧注释序列与各种编辑操作的RNA结构比较。它还产生了尚未研究的编辑模型。我们提供了一个彻底的分析的对齐层次结构，包括一个新的多项式时间算法和NP完全性证明。多项式时间算法涉及生物学相关的编辑操作，例如配对或解配对核苷酸。它已在一个名为gardenia的软件中实现，该软件可在Web服务器http://bioinfo.lifl.fr/RNA/gardenia上获得。
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.