Efficient pattern matching for RNA secondary structures
Efficient pattern matching for RNA secondary structures
复制标题
DOI：
10.1016/j.tcs.2015.05.016
复制
发表时间：
2015-08-09
影响因子：
1.1
通讯作者：
Adjeroh, Donald
中科院分区：
文献类型：
--
作者：
Beal, Richard;Adjeroh, Donald
我们提出了使用结构串的概念来解决RNA二级结构中的关键模式匹配问题的有效方法。结构串(S串)分别由字母Sigma和PI中的常量符号和参数符号组成。PI字母表中的单个符号可以被认为是PI中另一个唯一符号的补充。结构匹配问题被称为结构匹配问题(S-Match)，它有助于匹配RNA，以前是通过结构后缀树(SST)来解决的。其他不公开考虑S匹配的RNA匹配方法包括使用词缀数据结构。在本文中，我们提供了新的数据结构和算法来解决S匹配问题。具体地，我们介绍了结构后缀数组和结构最长公共前缀数组，并确定了如何与这些数据结构进行S匹配。然后，我们将新的S匹配解决方案作为框架来回答在匹配RNA二级结构时遇到的各种组合查询。(C)2015爱思唯尔B.V.保留所有权利。
We propose efficient methods to address key pattern matching problems in RNA secondary structures using the notion of structural strings. A structural string (s-string) is composed of constant symbols and parameter symbols from the alphabets Sigma and Pi, respectively. An individual symbol in the Pi alphabet may be considered a complement of another unique symbol in Pi. The notion of matching constants, parameters, and complements is referred to as the structural matching (s-match) problem, which is helpful in matching RNA and previously, was solved by the structural suffix tree (sST). Other approaches to RNA matching that do not openly consider the s-match include the use of affix data structures. In this paper, we provide new data structures and algorithms to address the s-match problem. Specifically, we introduce the structural suffix array and structural longest common prefix array and then identify how to s-match with these data structures. Our new s-matching solution is then used as the framework to answer various combinatorial queries encountered in matching RNA secondary structures. (C) 2015 Elsevier B.V. All rights reserved.