Database indexing for large DNA and protein sequence collections

Ela Hunt, Malcolm P. Atkinson, Robert W. Irving

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Our aim is to develop new database technologies for the approximate matching of unstructured string data using indexes. We explore the potential of the suffix tree data structure in this context. We present a new method of building suffix trees, allowing us to build trees in excess of RAM size, which has hitherto not been possible. We show that this method performs in practice as well as the O(n) method of Ukkonen [70]. Using this method we build indexes for 200 Mb of protein and 300 Mbp of DNA, whose disk-image exceeds the available RAM. We show experimentally that suffix trees can be effectively used in approximate string matching with biological data. For a range of query lengths and error bounds the suffix tree reduces the size of the unoptimised O(mn) dynamic programming calculation required in the evaluation of string similarity, and the gain from indexing increases with index size. In the indexes we built this reduction is significant, and less than 0.3% of the expected matrix is evaluated. We detail the requirements for further database and algorithmic research to support efficient use of large suffix indexes in biological applications.
Original languageEnglish
Pages (from-to)256-271
Number of pages16
JournalVLDB Journal
Issue number3
Publication statusPublished - Nov 2002


Dive into the research topics of 'Database indexing for large DNA and protein sequence collections'. Together they form a unique fingerprint.

Cite this