Exact match search in sequence data using suffix trees

ABSTRACT

We study suitable indexing techniques to support efficient exact match search in large biological sequence databases. We propose a suffix tree (ST) representation, called STA-DF, as an alternative to the array representation of ST (STA) proposed in [7] and utilized in [18]. To study the performance of STA and STA-DF, we develop a memory efficient ST-based Exact Match (STEM) search algorithm. We implemented STEM and both representations of ST and conducted extensive experiments. Our results indicate that the STA and STA-DF representations are very similar in construction time, storage utilization, and search time using STEM. In terms of the access patterns by STEM, our results show that compared to STA, the STA-DF representation exhibits better spatial and sequential locality of reference. This suggests that STA-DF would require less number of disk I/Os, and hence is more amenable to efficient and scalable disk-based computation.

REFERENCES

• 1: S.F. Altschul S.F., W. Gish, W. Miller, E.W. Myers, and D.J. Lipman. Basic local alignment search tool. In J. Mol. Biol., 215:403--10, 1990.
• 2: S. F. Altschul, T. L. Madden, A. A. Schaeer, J. Zhang, Z. Zhang, W. Miller, and D. J. Lipman. Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. In Nucleic Acids Research, 25:3389--3402, 1997.
• 3: Arne Andersson , Stefan Nilsson, Efficient implementation of suffix trees, Software—Practice & Experience, v.25 n.2, p.129-141, Feb. 1995 [doi>10.1002/spe.4380250203]
• 4: Alberto Apostolico , Raffaele Giancarlo, The Boyer Moore Galil string searching strategies revisited, SIAM Journal on Computing, v.15 n.1, p.98-105, Feb. 1986 [doi>10.1137/0215007]
• 5: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 6: Christian Charras and Thierry Lecroq. ESMAJ: Exact String Matching Algorithms, Animation in Java. http://www-igm.univ-lv.fr/~lecroq/string/index.html. Laboratoire d'Informatique de Rouen, Université de Rouen. Last accessed: April, 2005.
• 7: Robert Giegerich , Stefan Kurtz , Jens Stoye, Efficient Implementation of Lazy Suffix Trees, Proceedings of the 3rd International Workshop on Algorithm Engineering, p.30-42, July 19-21, 1999
• 8: R. Giegerich, S. Kurtz, and J. Stoye. Wotdeager Source code, http://bibiserv.techfak.uni-bielefeld.de/wotd/. Last accessed March, 2005.
• 9: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 10: R. Nigel Horspool. Practical Fast Searching in Strings. In Software - Practice and Experience, 10:501--506, 1980.
• 11: 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
• 12: Robert W. Irving , Lorna Love, The suffix binary search tree and suffix AVL tree, Journal of Discrete Algorithms, v.1 n.5-6, p.387-408, October 2003 [doi>10.1016/S1570-8667(03)00034-0]
• 13: D.E. Knuth, J.H. Morris (Jr), and V.R. Pratt. Fast pattern matching in strings. In SIAM Journal on Computing 6(1):323--350, 1977.
• 14: 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]
• 15: C. Meek, J. M. Patel, and S. Kassety. OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences. In Proc. of VLDB, 2003
• 16: 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]
• 17: Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM (JACM), v.15 n.4, p.514-534, Oct. 1968 [doi>10.1145/321479.321481]
• 18: S. Tata, R.A. Hankins, and J. Patel. Practical Suffix Tree Construction. In Proc. of the 30th VLDB, 2004
• 19: E. Ukkonen. On-line construction of suffix-trees. In Algorithmica 14 (1995), 249--260, 1995.
• 20: P. Weiner. Linear Pattern Matching Algorithms. In Proc. 14th Annual Symposium on Switching and Automata Theory, 1973.
• 21: http://www.ncbi.nlm.nih.gov - the NCBI web site. Last accessed: April 2005.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.3 Information Search and Retrieval
          Subjects: Search process

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Design, Performance

Keywords:
bioinformatics, indexing, sequence databases, suffix trees