Generalization of a Suffix Tree for RNA Structural Pattern Matching
Generalization of a Suffix Tree for RNA Structural Pattern Matching
复制标题
RNA 结构模式匹配后缀树的推广
DOI：
10.1007/s00453-003-1067-9
复制
发表时间：
2000
期刊：
影响因子：
1.1
通讯作者：
T. Shibuya
中科院分区：
文献类型：
--
作者：
T. Shibuya
**摘要**
在分子生物学中，据说如果两个生物序列具有相似的三维结构，它们往往具有相似的性质。因此，不仅从字符串意义上找到相似序列，而且从数据库中找到结构相似的序列是非常重要的。在本文中，我们提出一种新的数据结构，它是由贝克引入的参数化后缀树（简称p - 后缀树）的一种推广。我们将其简称为结构后缀树或s - 后缀树。s - 后缀树可用于寻找RNA或单链DNA的结构相关模式。此外，我们提出一种用于构建它的时间复杂度为O(n(log|Σ| + log|Π|))的在线算法，其中n是序列长度，|Σ|是常规字母表的大小，|Π|是与序列结构相关的被称为“参数”的字母表的大小。当我们的算法用于分析RNA和DNA序列时，它能达到线性时间复杂度。此外，作为一种构建p - 后缀树的算法，它是第一个在线算法，尽管我们算法的计算界限与科萨拉朱最著名的算法相同。我们还给出了使用实际RNA和DNA序列进行计算实验的结果，以证明我们算法的实用性。
Abstract
In molecular biology, it is said that
two biological sequences tend to have similar properties if they have similar
three-dimensional structures. Hence, it is very important to find not only similar
sequences in the string sense, but also structurally similar sequences from
databases. In this paper we propose a new data structure that
is a generalization of a parameterized suffix tree (p-suffix tree for short)
introduced by Baker.
We call it the structural suffix tree or s-suffix tree for short.
The s-suffix tree can be used for finding structurally related patterns of RNA
or single-stranded DNA.
Furthermore, we propose an
O(n(log|Σ| + log|Π|)) on-line algorithm for constructing it,
where n is the sequence length,
|Σ| is the size of the normal alphabet, and |Π| is that of the
alphabet called “parameter,” which is related to the structure of the sequence.
Our algorithm achieves linear time when it is used to analyze RNA and DNA sequences.
Furthermore, as an algorithm for constructing the p-suffix tree,
it is the first on-line algorithm, though
the computing bound of our algorithm
is the same as that of Kosaraju’s best-known algorithm.
The results of computational experiments using actual RNA and
DNA sequences are also given to demonstrate our algorithm’s practicality.