Conference Proceeding Article
In this paper, we propose a Distance-based Sequence Indexing Method (DSIM) for indexing and searching genome databases. Borrowing the idea of video compression, we compress the genomic sequence database around a set of automatically selected reference words, formed from high-frequency data substrings and substrings in past queries. The compression captures the distance of each non-reference word in the database to some reference word. At runtime, a query is processed by comparing its substrings with the compressed data strings, through their distances to the reference words. We also propose an efficient scheme to incrementally update the reference words and the compressed data sequences as more data sequences are added and new queries come along. Extensive experiments on a human genome database with 2.62 GB of DNA sequence letters show that the new algorithm achieves significantly faster response time than BLAST, while maintaining comparable accuracy.
Computation methods, data compression, data structures, database systems, indexing, Data sequences, Distance based Sequence Indexing Method (DSIM), Genomic sequences, Human genome
Databases and Information Systems | Numerical Analysis and Scientific Computing
Data Management and Analytics
BIBE 2005: Fifth IEEE International Symposium on Bioinformatic and Bioengineering, 19-21 October 2005, Minneapolis, MN
IEEE Computer Society
City or Country
Los Alamitos, CA
CAO, Xia; OOI, Beng-Chin; PANG, Hwee Hwa; TAN, Kian-Lee; and TUNG, Anthony K. H..
DSIM: A Distance-Based Indexing Method for Genomic Sequences. (2005). BIBE 2005: Fifth IEEE International Symposium on Bioinformatic and Bioengineering, 19-21 October 2005, Minneapolis, MN. 97-104. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/276
Copyright Owner and License
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.