Improving suffix array locality for fast pattern matching on disk

ABSTRACT

The suffix tree (or equivalently, the enhanced suffix array) provides efficient solutions to many problems involving pattern matching and pattern discovery in large strings, such as those arising in computational biology. Here we address the problem of arranging a suffix array on disk so that querying is fast in practice. We show that the combination of a small trie and a suffix array-like blocked data structure allows queries to be answered as much as three times faster than the best alternative disk-based suffix array arrangement. Construction of our data structure requires only modest processing time on top of that required to build the suffix tree, and requires negligible extra memory.

REFERENCES

• 1: Mohamed Ibrahim Abouelhoda , Stefan Kurtz , Enno Ohlebusch, Replacing suffix trees with enhanced suffix arrays, Journal of Discrete Algorithms, v.2 n.1, p.53-86, March 2004 [doi>10.1016/S1570-8667(03)00065-0]
• 2: Mohamed Ibrahim Abouelhoda , Enno Ohlebusch , Stefan Kurtz, Optimal Exact Strring Matching Based on Suffix Arrays, Proceedings of the 9th International Symposium on String Processing and Information Retrieval, p.31-43, September 11-13, 2002
• 3: S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman. Basic local alignment search tool. Jour. of Molecular Biology, 215(3):403--410, Oct. 1990.
• 4: A. Apostolico. The myriad virtues of subword trees. In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, NATO ASI Series F12, pages 85--96. Springer Verlag, Berlin, Germany, 1985.
• 5: Ricardo Baeza-Yates , Eduardo F. Barbosa , Nivio Ziviani, Hierarchies of indices for text searching, Information Systems, v.21 n.6, p.497-514, Sept. 1996 [doi>10.1016/0306-4379(96)00025-7]
• 6: D. Benson, D. J. Lipman, and J. Ostell. Genbank. Nucleic Acids Research, 21(13):2963--2965, 1993.
• 7: D. A. Benson, I. Karsch-Mizrachi, D. J. Lipman, J. Ostell, and D. L. Wheeler. Genbank. Nucleic Acids Research, 35:D21--D25, Jan. 2007.
• 8: Michael Cameron , Hugh E. Williams , Adam Cannane, Improved Gapped Alignment in BLAST, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.1 n.3, p.116-129, July 2004 [doi>10.1109/TCBB.2004.32]
• 9: Ching-Fung Cheung , Jeffrey Xu Yu , Hongjun Lu, Constructing Suffix Tree for Gigabyte Sequences with Megabyte Memory, IEEE Transactions on Knowledge and Data Engineering, v.17 n.1, p.90-105, January 2005 [doi>10.1109/TKDE.2005.3]
• 10: A. Crauser and P. Ferragina. A theoretical and experimental study on the construction of suffix arrays in external memory. Algorithmica, 32(1):1--35, Jan. 2002.
• 11: R. Dementiev, J. Kärkkäinen, J. Mehnert, and P. Sanders. Better external memory suffix array construction. ACM Jour. of Experimental Algorithmics, 2007. To appear.
• 12: Ensembl. Ensembl Genome Browser, 2006. http://www.ensembl.org.
• 13: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 14: Donna Harman, Overview of the second text retrieval conference (TREC-2), Information Processing and Management: an International Journal, v.31 n.3, p.271-289, May-June 1995
• 15: Toru Kasai , Gunho Lee , Hiroki Arimura , Setsuo Arikawa , Kunsoo Park, Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications, Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, p.181-192, July 01-04, 2001
• 16: Stefan Kurtz, Reducing the space requirement of suffix trees, Software—Practice & Experience, v.29 n.13, p.1149-1171, Nov. 1999 [doi>10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O]
• 17: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing, v.22 n.5, p.935-948, Oct. 1993 [doi>10.1137/0222058]
• 18: M. A. Maniscalco and S. J. Puglisi. Faster lightweight suffix array construction. In J. Ryan and Dafik, editors, Proc. Australasian Workshop on Combinatorial Algorithms, pages 16--29, 2006.
• 19: G. Manzini. Two space saving tricks for linear time LCP computation. In T. Hagerup and J. Katajainen, editors, Proceedings of 9th Scandinavian Workshop on Algorithm Theory (SWAT '04), volume 3111 of Lecture Notes in Computer Science, pages 372--383. Springer Verlag, Berlin, Germany, 2004.
• 20: Giovanni Manzini , Paolo Ferragina, Engineering a Lightweight Suffix Array Construction Algorithm, Algorithmica, v.40 n.1, p.33-50, June 2004 [doi>10.1007/s00453-004-1094-1]
• 21: 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]
• 22: Gonzalo Navarro , Veli Mäkinen, Compressed full-text indexes, ACM Computing Surveys (CSUR), v.39 n.1, p.2-es, 2007 [doi>10.1145/1216370.1216372]
• 23: 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]
• 24: Simon J. Puglisi , W. F. Smyth , Andrew H. Turpin, A taxonomy of suffix array construction algorithms, ACM Computing Surveys (CSUR), v.39 n.2, p.4-es, 2007 [doi>10.1145/1242471.1242472]
• 25: J. S. Sim, D. K. Kim, H. Park, and K. Park. Linear-time search in suffix arrays. In M. Miller and K. Park, editors, Proc. Australasian Workshop on Combinatorial Algorithms, pages 139--146, Seoul, Korea, 2003.
• 26: B. Smyth. Computing Patterns in Strings. Addison-Wesley, Reading, Massachusetts, USA, 2003.
• 27: 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]
• 28: E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249--260, 1995.
• 29: P. van Emde-Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6(3):80--82, 1977.
• 30: P. Weiner. Linear pattern matching algorithms. In Proc. Annual Symposium on Foundations of Computer Science, pages 1--11, Silver Spring, MD, USA, 1973. IEEE Computer Society Press.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Contiguous representations**

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing

General Terms:
Algorithms, Experimentation, Performance

Keywords:
disk-based algorithm, pattern matching, secondary storage, suffix array, suffix tree