Publication Type

Conference Proceeding Article

Version

Postprint

Publication Date

10-2005

Abstract

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.

Keywords

Computation methods, data compression, data structures, database systems, indexing, Data sequences, Distance based Sequence Indexing Method (DSIM), Genomic sequences, Human genome

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Management and Analytics

Publication

BIBE 2005: Fifth IEEE International Symposium on Bioinformatic and Bioengineering, 19-21 October 2005, Minneapolis, MN

First Page

97

Last Page

104

ISBN

9780769524764

Identifier

10.1109/BIBE.2005.24

Publisher

IEEE Computer Society

City or Country

Los Alamitos, CA

Copyright Owner and License

Authors

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL

http://doi.org/10.1109/BIBE.2005.24

Share

COinS