title: An efficient similarity search based on indexing in large DNA databases.
abstract: Index-based search algorithms are an important part of a genomic search, and how to construct indices is the key to an index-based search algorithm to compute similarities between two DNA sequences. In this paper, we propose an efficient query processing method that uses special transformations to construct an index. It uses small storage and it rapidly finds the similarity between two sequences in a DNA sequence database. At first, a sequence is partitioned into equal length windows. We select the likely subsequences by computing Hamming distance to query sequence. The algorithm then transforms the subsequences in each window into a multidimensional vector space by indexing the frequencies of the characters, including the positional information of the characters in the subsequences. The result of our experiments shows that the algorithm has faster run time than other heuristic algorithms based on index structure. Also, the algorithm is as accurate as those heuristic algorithms.
authors.affiliation: School of Electronics & Computer Eng., Chonnam National University, 300 YongBong-Dong, Buk-Gu, Gwangju 500-757, Republic of Korea. isjung0@moiza.chonnam.ac.kr
authors.forename: In-Seon
authors.initials: IS
authors.lastname: Jeong
authors.forename: Kyoung-Wook
authors.initials: KW
authors.lastname: Park
authors.forename: Seung-Ho
authors.initials: SH
authors.lastname: Kang
authors.forename: Hyeong-Seok
authors.initials: HS
authors.lastname: Lim
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D030561:Databases, Nucleic Acid; D006801:Humans; D016247:Information Storage and Retrieval; D017385:Sequence Homology