In molecular biology, DNA sequence matching is one of the most crucial operations. Since DNA databases contain a huge volume of sequences, fast indexes are essential for efficient processing of DNA sequence matching. In this paper, we first point out the problems of the suffix tree, an index structure widely-used for DNA sequence matching, in respect of storage overhead, search performance, and difficulty in seamless integration with DBMS. Then, we propose a new index structure that resolves such problems. The proposed index structure consists of two parts: the primary part realizes the trie as binary bit-string representation without any pointers, and the secondary part helps fast access to the trie's leaf nodes that need to be accessed for post-processing. We also suggest efficient algorithms based on that index for DNA sequence matching. To verify the superiority of the proposed approach, we conduct performance evaluation via a series of experiments. The results reveal that the proposed approach, which requires smaller storage space, can be a few orders of magnitude faster than the suffix tree.
C. Gibas and P. Jambeck , Developing Bioinformatics Computer Skills( O'Reilly and Associates, Tokyo , 2001).
2.
D.W. Mount , Bioinformatics: Sequence and Genome Analysis( Cold Spring Harbor Laboratory Press, Cold Spring Harbor , 2001).
3.
R.S.C. Goble , P. Baker and A. Brass , A Classification of tasks in bioinformatics , Bioinformatics17(2) (2001) 180–188 .
4.
D.A. Benson , M.S. Boguski , D.J. Lipman , J. Ostell and B.F. Quellette, Genbank , Nucleic Acids Research26(1) (1998) 1–7 .
5.
S. Altschul , W. Gish , W. Miller , E. Myers and D. Lipman , Basic local alignment search tool , Journal of Molecular Biology215 (1990) 403–410 .
6.
S.F. Altschul , T.L. Madden , A.A. Schaffer , J. Zhang , Z. Zhang , W. Miller and D.J. Lipman , Gapped BLAST and PSI-BLAST: a new generation of protein database search programs , Nucleic Acids Research25(17) (1997) 3389–3402 .
7.
T. Smith and M. Waterman , Identification of common molecular subsequences , Journal of Molecular Biology147 (1981) 195–197 .
8.
G.A. Stephen , String Searching Algorithms( World Scientific Publishing, River Edge , 1994).
9.
E. Ukkonen , Approximate string matching over suffix trees. In: A. Apostolico et al. (eds), Proceedings of the 4th Annual Symposium on Combinatorial Pattern Matching (CPM93) 1993(Springer, 1993) 228–242.
10.
A.L. Delcher , S. Kasif , R.D. Fleischmann , J. Peterson , O. White and S.L. Salzberg , Alignment of whole genomes , Nucleic Acids Research27 (1999) 2369–2376 .
11.
S. Kurtz , J. Choudhuri , E. Ohlebusch , C. Schleiermacher , J. Stoye and R. Giegerich , REPuter: the manifold applications of repeat analysis on a genome scale , Nucleic Acids Research29(22) (2001) 4633–4642 .
12.
E. Hunt , M.P. Atkinson and R.W. Irving , Database indexing for large DNA and protein sequence collections , VLDB Journal11(3) (2002) 256–271 .
13.
G. Navarro and R. Baeza-Yates , A hybrid indexing method for approximate string matching , Journal of Discrete Algorithms1(1) (2000) 205–239 .
14.
G. Navarro and R. Baeza-Yates , A new indexing method for approximate string matching. In: M. Crochemore and M. Paterson (eds), Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching (CPM99) 1999(Springer, 1999)163–185.
15.
C. Meek , J.M. Patel and S. Kasetty , OASIS: an online and accurate technique for local-alignment searches on biological sequences. In: J.C. Freytag et al. (eds), Proceedings of the 29th International Conference on Very Large Databases(VLDB03) 2003( Morgan Kaufmann , 2003) 920–921.
16.
K. Kelly and P. Labute , The A* Search and Applications to Sequence Alignment(1996). Available at: www.chemcomp.com/Journal_of_CCG/Articles/astar.htm (accessed 28 July 2005).
17.
S. Kurtz and C. Schleiermacher , REPuter: fast computation of maximal repeats in complete genomes , Bioinformatics15(5) (1999) 426–427 .
18.
R. Giegerich , S. Kurtz and J. Stoye , Efficient implementation of lazy suffix trees , Software-Practice and Experience33 (2003) 1035–1049 .
19.
K. Sadakane and T. Shibuya , Indexing huge genome sequences for solving various problems. In: H. Matsuda et al. (eds), Proceedings of the 12th Genome Informatics (GIW01) 2001( Universal Academy Press , 2001) 175–183.
20.
H. Wang et al., BLAST++: a tool for BLASTing queries in batches. In: Y.P.P. Chen (ed.), Proceedings of the 1st Asia-Pacific Bioinformatics Conference (APBC03) 2003 ( Australian Computer Society , 2003) 71–79.
21.
E. Horowitz , S. Sahni and S. Anderson-Freed , Fundamentals of Data Structures in C( Computer Science Press, New York , 1993).
22.
J. Buhler , Efficient large-scale sequence comparison by local-sensitive hashing , Bioinformatics17 (2001) 419–428 .
23.
B. Ma , J. Tromp , and M. Li , Patternhunter: faster and more sensitive homology search , Bioinformatics18 (2002) 440–445 .
24.
A. Califano and I. Rigoutsos , FLASH: a fast look-up algorithm for string homology. In: L. Hunter et al. (eds), Proceedings of the 1st International Conference on Intelligent Systems for Molecular Biology, 1993( AAAI Press , 1993) 56–64.
25.
C. Fondrat and P. Dessen , A rapid access motif database (RAMdb) with a searching algorithms for the retrieval patterns in nucleic acids or protein databanks , Computer Applications in the Biosciences11(3) (1995) 273–279 .
26.
H.E. Williams and J. Zobel , Indexing and retrieval for genomic databases , IEEE TKDE14(1) (2002) 63–78 .
27.
T. Kaheci and A.K. Singh , An efficient index structure for string databases. In: P.M.G. Apers et al. (eds), Proceedings of the 27th International Conference on Very Large Databases (VLDB01) 2001( Morgan Kaufmann , 2001) 351–360.
28.
U. Manber and G. Myers , Suffix arrays: a new method for on-line string searches , SIAM Journal on Computing22(5) (1993) 935–948 .
29.
R. de la Briandais , File searching using variable length keys. In: Proceedings of Western Joint Computer Conference, 1959( AFIPS Press , 1959) 295–298.
30.
D.E. Knuth , The Art of Computer Programming 3: Sorting and searching( Addison-Wesley, Boston , 1973).
31.
H. Shang and T.H. Merrett , Tries for approximate string matching , IEEE Transactions on Knowledge and Data Engineering8(4) (1996) 540–547 .
32.
P. Bieganski , J. Riedl and J.V. Carlis , Generalized suffix trees for biological sequence data: applications and implementation. In: Proceedings of the 27th International Conference on System Sciences 1994( IEEE , 1994) Vol. 5, 35–44.
33.
Genbank. Available at: www.ncbi.nlm.nih.gov (accessed 28 July 2005).
34.
N. Beckmann , H. Kriegel , R. Schneider and B. Seeger , The R*-tree: an efficient and robust access method for points and rectangles. In: H. Garcia-Molina and H.V. Jagadish (eds), Proceedings of ACM SIGMOD International Conference on Management of Data 1990 ( ACM Press , 1990) 322–331.
