This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Citation Map Services Email this article to a friend Similar articles in this journal Similar articles in Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Won, J.-I. Articles by Kim, S.-W. Search for Related Content Social Bookmarking                         What's this?

An efficient approach for sequence matching in large DNA databases

Sanghyun Park

Department of Computer Science, Yonsei University, Korea

Jee-Hee Yoon

Division of Information Engineering and Telecommunications, Hallym University, Korea

Sang-Wook Kim

College of Information and Communications, Hanyang University, Korea

In molecular biology, DNA sequence matching is one of the most crucial operations. Since DNA databases contain a huge volume of sequences, fast indexes are essential for efficient processing of DNA sequence matching. In this paper, we first point out the problems of the suffix tree, an index structure widely-used for DNA sequence matching, in respect of storage overhead, search performance, and difficulty in seamless integration with DBMS. Then, we propose a new index structure that resolves such problems. The proposed index structure consists of two parts: the primary part realizes the trie as binary bit-string representation without any pointers, and the secondary part helps fast access to the trie's leaf nodes that need to be accessed for post-processing. We also suggest efficient algorithms based on that index for DNA sequence matching. To verify the superiority of the proposed approach, we conduct performance evaluation via a series of experiments. The results reveal that the proposed approach, which requires smaller storage space, can be a few orders of magnitude faster than the suffix tree.

Key Words: DNA databases • DNA sequence matching • indexing

Journal of Information Science, Vol. 32, No. 1, 88-104 (2006)
DOI: 10.1177/0165551506059229


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?