首页 | 本学科首页   官方微博 | 高级检索  
     


Generalization of a Suffix Tree for RNA Structural Pattern Matching
Authors:Tetsuo?Shibuya  author-information"  >  author-information__contact u-icon-before"  >  mailto:tshibuya@jp.ibm.com"   title="  tshibuya@jp.ibm.com"   itemprop="  email"   data-track="  click"   data-track-action="  Email author"   data-track-label="  "  >Email author
Affiliation:(1) IBM Tokyo Research Laboratory, 1623-14 Shimotsuruma, Yamato-shi, Kanagawa 242-8502, Japan
Abstract:In molecular biology, it is said thattwo biological sequences tend to have similar properties if they have similarthree-dimensional structures. Hence, it is very important to find not only similarsequences in the string sense, but also structurally similar sequences fromdatabases. In this paper we propose a new data structure thatis 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 RNAor single-stranded DNA.Furthermore, we propose anO(n(log|Sgr| + log|Pgr|)) on-line algorithm for constructing it,where n is the sequence length,|Sgr| is the size of the normal alphabet, and |Pgr| is that of thealphabet called ldquoparameter,rdquo 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, thoughthe computing bound of our algorithmis the same as that of Kosarajursquos best-known algorithm.The results of computational experiments using actual RNA andDNA sequences are also given to demonstrate our algorithmrsquos practicality.
Keywords:Pattern matching  Suffix tree generalization  Parameterized suffixtree  Computational biology  RNA structure matching
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号