An efficient DNA sequence searching method using position specific weighting scheme

Abstract

Exact match queries, wildcard match queries, and k mismatch queries are widely used in various molecular biology applications including the searching of ESTs (Expressed Sequence Tags) and DNA transcription factors. In this paper, we suggest an efficient indexing and processing mechanism for such queries. Our indexing method places a sliding window at every possible location of a DNA sequence and extracts its signature by considering the occurrence frequency of each nucleotide. It then stores a set of signatures using a multi-dimensional index such as the R*-tree. Also, by assigning a weight to each position of a window, it prevents signatures from being concentrated around a few spots in indexing space. Our query processing method converts a query sequence into a multi-dimensional rectangle and searches the index for the signatures overlapping with the rectangle. Experiments with real biological data sets have revealed that the proposed approach is at least 4.4 times, 2.1 times, and several orders of magnitude faster than the previous one in performing exact match, wildcard match, and k-mismatch queries, respectively.

Keywords

DNA database indexing query processing exact match wildcard match k-mismatch

Get full access to this article

View all access options for this article.

References

C. Gibas and P. Jambeck , Developing Bioinformatics Computer Skills( O'Reilly, Sebastopol , 2001).

T. Smith and M. Waterman , Identification of common molecular subsequences , Journal of Molecular Biology 147(1) (1981) 195–197 .

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 Research 25(17) (1997) 3389–3402 .

S. Altschul , W. Gish , W. Miller , E. Myers and D. Lipman , Basic local alignment search tool , Journal of Molecular Biology 215(3) (1990) 403–500 .

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) 11–14 September 2001 (Morgan Kaufmann, San Francisco, 2001) 351–360 .

D. Gusfield , Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology( Cambridge University Press, New York , 1997).

R.S. Boyer and J.S. Moore , A fast string searching algorithm , Communications of the ACM 20(10) (1977) 762–772 .

D.E. Knuth , J.H. Morris , and V.B. Pratt , Fast pattern matching in strings , SIAM Journal of Computing 6(2) (1977) 323–350 .

A. Aho and M. Corasick , Efficient string matching: an aid to bibliographic search , Communications of the ACM 18(6) (1975) 333–340 .

10.

G.A. Stephen , String Searching Algorithm( World Scientific Publishing, Singapore , 1994).

11.

U. Manber and G. Myers , Suffix arrays: a new method for on-line string searches , SIAM Journal on Computing 22(5) (1993) 935–948 .

12.

V. Makinen , Compact suffix array: a space-efficient fulltext index , Fundamenta Informaticae 56(1/2) (2003) 191–210 .

13.

V. Makinen and G. Navarro , Compressed compact suffix DNA sequence searching arrays . In: S.C. Sahinalp et al. (eds), Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM04) 5–7 July 2004(Springer, Berlin, 2004) 420–433 .

14.

K. Sadakane , Compressed text databases with efficient query algorithms based on the compressed suffix array . In: D.T. Lee and S.H. Teng (eds), Proceedings of the 11th Algorithms and Computation (ISAAC00) 18–20 December 2000(Springer, Berlin, 2000) 410–421 .

15.

A. Guttman , R-Trees: a dynamic index structure for spatial searching . In: B. Yormark (ed.), Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data (ACM SIGMOD) 18–21 June 2004(ACM Press, New York, 1984) 47–57 .

16.

R. Agrawal , C. Faloutsos and A. Swam , Efficient similarity search in sequence databases . In: D.B. Lomet (ed.), Proceedings of the 4th International Conference of Foundations of Data Organization and Algorithms (FODO93) 13–15 October 1993(Springer, Berlin, 1993) 69–84 .

17.

R. Giegerich , S. Kurtz and J. Stoye , Efficient implementation of lazy suffix trees , Software-Practice & Experience 33(11) (2003) 1035–1039 .

18.

E. Hunt , M.P. Atkinson and R.W. Irving , Database indexing for large DNA and protein sequence collections , VLDB Journal 11(3) (2002) 256–271 .

19.

R. Cole , L. Gottlieb and M. Lewenstein , Dictionary matching and indexing with errors and don't cares . In: L. Babai (ed.), Proceedings of the 36th Annual ACM Symposium on Theory of computing (STOC04) 9–11 June 2003 (ACM Press, New York, 2004) 91–100 .

20.

A. Amir , M. Lewenstein and E. Porat , Faster algorithms for string matching with k-mismatches . In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete algorithms(SODA00) 9–11 January 2000 (ACM/SIAM, New York, 2000) 794–803 .

21.

S. Berchtold , D.A. Keim and H.-P. Kriegel , The X-tree: an index structure for high-dimensional data . In: T.M. Vijayaraman et al. (eds), Proceedings of the 22nd International Conference on Very Large Databases (VLDB96) 3–6 September 1996(Morgan Kaufman, San Francisco, 1996) 28–39 .

22.

The Entrez Nucleotides Database. Available at: www.ncbi.nlm.nih.gov (accessed 13 September 2005).

23.

The Ensembl Project. Available at: www.ensembl.org (accessed 13 September 2005).