Affiliations: Department of Computer Science, Yonsei University, 134
Sinchon-dong, Seodaemun-gu, Seoul 120-749, Korea. E-mail: mkseo@cs.yonsei.ac.kr;
sanghyun@cs.yonsei.ac.kr | College of Information and Communications Hanyang
University, 17 HaengDangDong, SeongDongGu, Seoul, Korea.
E-mail: jiwon@hanyang.ac.kr
Abstract: Approximate searching on the primary structure (i.e., amino acid
arrangement) of protein sequences is an essential part in predicting the
functions and evolutionary histories of proteins. However, because proteins
distant in an evolutionary history do not conserve amino acid residue
arrangements, approximate searching on proteins' secondary
structure is quite important in finding out distant homology. In this paper, we
propose an indexing scheme for efficient approximate searching on the secondary
structure of protein sequences which can be easily implemented in RDBMS.
Exploiting the concept of clustering and lookahead, the proposed indexing
scheme processes three types of secondary structure queries (i.e., exact match,
range match, and wildcard match) very quickly. To evaluate the performance of
the proposed method, we conducted extensive experiments using a set of actual
protein sequences. According to the experimental results, the proposed method
was proved to be faster than the existing indexing methods up to 6.3 times in
exact match, 3.3 times in range match, and 1.5 times in wildcard match,
respectively.
Keywords: Indexing method, Secondary structure of proteins, and Approximate searching
