A new method for indexing genomes using on-disk suffix trees

ABSTRACT

We propose a new method to build persistent suffix trees for indexing the genomic data. Our algorithm DiGeST (Disk-Based Genomic Suffix Tree) improves significantly over previous work in reducing the random access to the input string and performing only two passes over disk data. DiGeST is based on the two-phase multi-way merge sort paradigm using a concise binary representation of the DNA alphabet. Furthermore, our method scales to larger genomic data than managed before.

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: Srikanta J. Bedathur , Jayant R. Haritsa, Engineering a Fast Online Persistent Suffix Tree Construction, Proceedings of the 20th International Conference on Data Engineering, p.720, March 30-April 02, 2004
• 3: 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]
• 4: R. Clifford, and M.J. Sergot Distributed and paged suffix trees forlarge genetic databases. Proc. of 14th Symposiumon Combinatorial Pattern Matching: 70--82, 2003.
• 5: A. Crauser and P. Ferragina A Theoretical and Experimental Study on the Construction of Suffix Arrays in External Memory. Algoritmica, 32(1): 1--35, 2002.
• 6: A.L. Delcher, S. Kasif, R.D. Fleischmann, J. Peterson, O. White and S.L. Salzberg Alignment of whole genomes. Nucl. Acids. Res., 27(11): 2369--2376, 1999.
• 7: A.L. Delcher, A. Phillippy, J. Carlton, and S.L. Salzberg Fast algorithms for large-scale genome alignment and comparison. Nucl. Acids. Res., 30(11): 2478--2483, 2002.
• 8: R. Dementiev, J. Kärkkäinen, J. Mehnert, and P. Sanders Better externalmemory suffix array construction. Proc. of the 7thWorkshop on Algorithm Engineering and Experiments, 2005.
• 9: Paolo Ferragina , Roberto Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM (JACM), v.46 n.2, p.236-280, March 1999 [doi>10.1145/301970.301973]
• 10: Hector Garcia-Molina , Jennifer Widom , Jeffrey D. Ullman, Database System Implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 11: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 12: Wing-Kai Hon , Kunihiko Sadakane , Wing-Kin Sung, Breaking a Time-and-Space Barrier in Constructing Full-Text Indices, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.251, October 11-14, 2003
• 13: E. Hunt, M.P. Atkinson, and R.W. Irving A database index to large biological sequences. The VLDB Jornal, 7(3): 139--148, 2001.
• 14: J. Kärkkäinen, and P. Sanders Simple linear work suffix array construction. Proc. 13th Int. Conf. on Automata, Languages and Programming, 2003
• 15: D.K. Kim, J.S. Sim, H. Park, and K. Park Linear-time construction of suffix arrays: (Extended abstract). Proc. of CPM Conf., LNCS 2676: 189--199, 2003
• 16: P. Ko and S. Aluru Space efficient linear time construction of suffix arrays. J. of Discrete Algorithms, 3 (2-4): 143--156, 2005
• 17: 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]
• 18: S. Kurtz, A. Phillippy, A.L. Delcher, M. Smoot, M. Shumway, C. Antonescu, and S.L. Salzberg Versatile and open software for comparing large genomes. Genome Biology, 5(R12): 2004.
• 19: N.J. Larsson and K. Sadakane Faster suffix sorting. Tech. Rep. LUCS-TR:99-214 of the Dept. of Comp. Sc., Lund University, Sweden, 1999.
• 20: 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]
• 21: 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]
• 22: 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]
• 23: B. Phoophakdee and M.J. Zaki Trellis+: An Effective Approach for Indexing Massive Sequence. Pacific Symposium on Biocomputing, 2008.
• 24: E. Pennisi DNA Study Forces Rethink of What It Means to Be a Gene. Science, 316 (5831): 1556--7, 2007
• 25: 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]
• 26: T. Ryan Gregory The evolution of the genome. Academic Press, 2005.
• 27: K. Schurmann, J. Stoye Suffix-tree construction and storagewith limited main memory. Tech. Rep. 2003-06 of the Universityof Bielefeld, Germany, 2003.
• 28: Ranjan Sinha , Simon Puglisi , Alistair Moffat , Andrew Turpin, Improving suffix array locality for fast pattern matching on disk, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376683]
• 29: A. Stark et al. Discovery of functional elements in 12 Drosophila genomes using evolutionary signatures. Nature, 450 : 219--232, 2007.
• 30: 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
• 31: 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]
• 32: E. Ukkonen On-line construction of suffix trees. Algorithmica, 14(3): 1995.
• 33: A. Woolfe et al. Highly conserved non-coding sequences are associated with vertebrate development. PLoS Biology, 3(1), e7 doi:10.1371/journal.pbio.0030007
• 34: Strings, Compression, and Orchestra: www.larsson.dogma.net/research.html
• 35: USCS Genome Browser: hgdownload.cse.ucsc.edu/downloads.html
• 36: Benjarath Pupacdi's Home Page: www.cs.rpi.edu/~zaki/software/trellis

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

Additional Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES

General Terms:
Algorithms, Design, Performance

Keywords:
DNA indexing, disk structures, suffix tree