Multiseed Lossless Filtration

ABSTRACT

We study a method of seed-based lossless filtration for approximate string matching and related bioinformatics applications. The method is based on a simultaneous use of several spaced seeds rather than a single seed as studied by Burkhardt and Kärkkäinen [1]. We present algorithms to compute several important parameters of seed families, study their combinatorial properties, and describe several techniques to construct efficient families. We also report a large-scale application of the proposed technique to the problem of oligonucleotide selection for an EST sequence database.

REFERENCES

• 1: Stefan Burkhardt , Juha Kärkkäinen, Better filtering with gapped q-grams, Fundamenta Informaticae, v.56 n.1,2, p.51-70, July 2003
• 2: Gonzalo Navarro , Mathieu Raffinot, Flexible pattern matching in strings: practical on-line search algorithms for texts and biological sequences, Cambridge University Press, New York, NY, 2002
• 3: S. Altschul T. Madden A. Schäffer J. Zhang Z. Zhang W. Miller and D. Lipman, “Gapped BLAST and PSI-BLAST: A New Generation of Protein Database Search Programs,” <i>Nucleic Acids Research,</i> vol. 25, no. 17, pp. 3389-3402, 1997.
• 4: B. Ma J. Tromp and M. Li, “PatternHunter: Faster and More Sensitive Homology Search,” <i>Bioinformatics,</i> vol. 18, no. 3, pp. 440-445, 2002.
• 5: S. Schwartz J. Kent A. Smit Z. Zhang R. Baertsch R. Hardison D. Haussler and W. Miller, “Human-Mouse Alignments with BLASTZ,” <i>Genome Research,</i> vol. 13, pp. 103-107, 2003.
• 6: L. Noé and G. Kucherov, “Improved Hit Criteria for DNA Local Alignment,” <i>BMC Bioinformatics,</i> vol. 5, no. 149, Oct. 2004.
• 7: P. Pevzner and M. Waterman, “Multiple Filtration and Approximate Pattern Matching,” <i>Algorithmica,</i> vol. 13, pp. 135-154, 1995.
• 8: Andrea Califano , Isidore Rigoutsos, FLASH: A Fast Look-Up Algorithm for String Homology, Proceedings of the 1st International Conference on Intelligent Systems for Molecular Biology, p.56-64, July 01, 1993
• 9: Jeremy Buhler, Provably sensitive Indexing strategies for biosequence similarity search, Proceedings of the sixth annual international conference on Computational biology, p.90-99, April 18-21, 2002, Washington, DC, USA [doi>10.1145/565196.565208]
• 10: Uri Keich , Ming Li , Bin Ma , John Tromp, On spaced seeds for similarity search, Discrete Applied Mathematics, v.138 n.3, p.253-263, 15 April 2004 [doi>10.1016/S0166-218X(03)00382-2]
• 11: Jeremy Buhler , Uri Keich , Yanni Sun, Designing seeds for similarity search in genomic DNA, Proceedings of the seventh annual international conference on Research in computational molecular biology, p.67-75, April 10-14, 2003, Berlin, Germany [doi>10.1145/640075.640083]
• 12: B. Brejova D. Brown and T. Vinar, “Vector Seeds: An Extension to Spaced Seeds Allows Substantial Improvements in Sensitivity and Specificity,” <i>Proc. Third Int'l Workshop Algorithms in Bioinformatics (WABI),</i> pp. 39-54, Sept. 2003.
• 13: Estimating Seed Sensitivity on Homogeneous Alignments, Proceedings of the 4th IEEE Symposium on Bioinformatics and Bioengineering, p.387, May 19-21, 2004
• 14: Kwok Pui Choi , Louxin Zhang, Sensitivity analysis and efficient method for identifying optimal spaced seeds, Journal of Computer and System Sciences, v.68 n.1, p.22-40, February 2004 [doi>10.1016/j.jcss.2003.04.002]
• 15: M. Csürös, “Performing Local Similarity Searches with Variable Length Seeds,” <i>Proc. 15th Ann. Combinatorial Pattern Matching Symp. (CPM),</i> pp. 373-387, 2004.
• 16: M. Li B. Ma D. Kisman and J. Tromp, “PatternHunter II: Highly Sensitive and Fast Homology Search,” <i>J. Bioinformatics and Computational Biology,</i> vol. 2, no. 3, pp. 417-440, Sept. 2004.
• 17: Yanni Sun , Jeremy Buhler, Designing multiple simultaneous seeds for DNA similarity search, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.76-84, March 27-31, 2004, San Diego, California, USA [doi>10.1145/974614.974625]
• 18: D.G. Brown, “Multiple Vector Seeds for Protein Alignment,” <i>Proc. Fourth Int'l Workshop Algorithms in Bioinformatics (WABI),</i> pp. 170-181, Sept. 2004.
• 19: J. Xu D. Brown M. Li and B. Ma, “Optimizing Multiple Spaced Seeds for Homology Search,” <i>Proc. 15th Symp. Combinatorial Pattern Matching,</i> pp. 47-58, 2004.
• 20: B. John Oommen , Juan Dong, Generalized Swap-with-Parent Schemes for Self-Organizing Sequential Linear Lists, Proceedings of the 8th International Symposium on Algorithms and Computation, p.414-423, December 17-19, 1997
• 21: F. Li and G. Stormo, “Selection of Optimal DNA Oligos for Gene Expression Arrays,” <i>Bioinformatics,</i> vol. 17, pp. 1067-1076, 2001.
• 22: L. Kaderali and A. Schliep, “Selecting Signature Oligonucleotides to Identify Organisms Using DNA Arrays,” <i>Bioinformatics,</i> vol. 18, no. 10, pp. 1340-1349, 2002.
• 23: S. Rahmann, “Fast Large Scale Oligonucleotide Selection Using the Longest Common Factor Approach,” <i>J. Bioinformatics and Computational Biology,</i> vol. 1, no. 2, pp. 343-361, 2003.
• 24: J. Zheng T. Close T. Jiang and S. Lonardi, “Efficient Selection of Unique and Popular Oligos for Large EST Databases,” <i>Proc. 14th Ann. Combinatorial Pattern Matching Symp. (CPM),</i> pp. 273-283, 2003.
• 25: Stefan Burkhardt , Juha Kärkkäinen, One-Gapped q-Gram Filtersfor Levenshtein Distance, Proceedings of the 13th Annual Symposium on Combinatorial Pattern Matching, p.225-234, July 03-05, 2002

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.0 General

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

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
Index Terms- Filtration, string matching, gapped seed, gapped q-gram, local alignment, sequence similarity, seed family, multiple spaced seeds, dynamic programming, EST, oligonucleotide selection.