Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:Database indexing for large DNA and protein sequence collections
Authors: E. Hunt ; Malcolm Atkinson ; R.W Irving
Date:Nov 2002
Publication Title:The VLDB Journal
Publication Type:Journal Article Publication Status:Published
Volume No:11(3) Page Nos:256-271
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.
Links To Paper
1st Link
Bibtex format
author = { E. Hunt and Malcolm Atkinson and R.W Irving },
title = {Database indexing for large DNA and protein sequence collections},
journal = {The VLDB Journal},
publisher = {Springer},
year = 2002,
month = {Nov},
volume = {11(3)},
pages = {256-271},
doi = {10.1007/s007780200064},
url = {},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh