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|| + log||)) on-line algorithm for constructing it,where n is the sequence length,|| is the size of the normal alphabet, and || is that of thealphabet 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, thoughthe computing bound of our algorithmis the same as that of Kosarajus best-known algorithm.The results of computational experiments using actual RNA andDNA sequences are also given to demonstrate our algorithms practicality. |