Computing at Glasgow University
Paper ID: 6471

Database indexing for large DNA and protein sequence collections
Hunt,E. Atkinson,M.P. Irving,R.W.

Publication Type: Journal
Appeared in: The VLDB Journal 11:3
Page Numbers : 256-271
Publisher: Springer
Year: 2002

Note: DOI 10.1007/s007780200064


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 \cite{Ukkonen95}. 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 data\-base and algorithmic research to support efficient use of large suffix indexes in biological applications.

Keywords: Database index, Suffix tree, Approximatematching, Biological sequence

PDF Bibtex entry Endnote XML