Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

A suffix tree is a fundamental data structure for string searching algorithms. Unfortunately, when it comes to the use of suffix trees in real-life applications, the current methods for constructing suffix trees do not scale for large inputs. All the existing practical algorithms perform random access to the input string, thus requiring that the input be small enough to be kept in main memory.

We are the first to present an algorithm which is able to construct suffix trees for input sequences significantly larger than the size of the available main memory. As a proof of concept, we show that our method allows to build the suffix tree for 12GB of real DNA sequences in 26 hours on a single machine with 2GB of RAM. This input is four times the size of the Human Genome, and the construction of suffix trees for inputs of such magnitude was never reported before.

REFERENCES

• 1: Marina Barsky , Ulrike Stege , Alex Thomo , Chris Upton, A new method for indexing genomes using on-disk suffix trees, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458170]
• 2: Martin Farach-Colton , Paolo Ferragina , S. Muthukrishnan, On the sorting-complexity of suffix tree construction, Journal of the ACM (JACM), v.47 n.6, p.987-1011, Nov. 2000 [doi>10.1145/355541.355547]
• 3: Hector Garcia-Molina , Jennifer Widom , Jeffrey D. Ullman, Database System Implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 4: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 5: Ela Hunt , Malcolm P. Atkinson , Robert W. Irving, A Database Index to Large Biological Sequences, Proceedings of the 27th International Conference on Very Large Data Bases, p.139-148, September 11-14, 2001
• 6: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 7: Benjarath Phoophakdee , Mohammed J. Zaki, Genome-scale disk-based suffix tree indexing, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247572]
• 8: B. Phoophakdee and M. J. Zaki. Trellis+: An Effective Approach for Indexing Massive Sequence. Pacific Symposium on Biocomputing, 2008.
• 9: Sandeep Tata , Richard A. Hankins , Jignesh M. Patel, Practical suffix tree construction, Proceedings of the Thirtieth international conference on Very large data bases, p.36-47, August 31-September 03, 2004, Toronto, Canada
• 10: Yuanyuan Tian , Sandeep Tata , Richard A. Hankins , Jignesh M. Patel, Practical methods for constructing suffix trees, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.3, p.281-299, September 2005 [doi>10.1007/s00778-005-0154-8]
• 11: USCS Genome Browser: hgdownload.cse.ucsc.edu/downloads.html
• 12: Source code for TDD: www.eecs.umich.edutdddownload.html
• 13: Source code for Trellis+SB: www.cs.rpi.edu/~zaki/software/trellis

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

General Terms:
Algorithms, Design, Performance

Keywords:
external memory algorithms, suffix tree