Related Experiment Videos
Fast and simple character classes and bounded gaps pattern matching, with applications to protein searching
Gonzalo Navarro1, Mathieu Raffinot
1Department of Computer Science, University of Chile, Blanco Encalada 2120, Santiago, Chile. gnavarro@dcc.uchile.cl
Summary
This study introduces two novel algorithms for efficiently searching patterns with character classes and bounded gaps (CBG) in biological sequences. These methods significantly outperform traditional regular expression searches for protein pattern matching.
Area of Science:
- Bioinformatics
- Computational Biology
- Pattern Recognition
Background:
- Protein pattern matching often involves complex patterns with character classes and bounded gaps (CBG).
- Current methods rely on converting CBGs to regular expressions (REs), which are computationally intensive and slow for pattern matching.
- Existing RE search algorithms are not optimized for the specific structure of CBGs, leading to inefficiencies.
Purpose of the Study:
- To develop novel, efficient algorithms for exact and approximate searching of CBG patterns.
- To provide a simpler and faster alternative to current RE-based pattern matching techniques.
- To enable faster and more accurate protein pattern identification.
Main Methods:
- Designed two new practical algorithms for CBG pattern matching.
- Algorithm 1: Scans each text character exactly once.
- Algorithm 2: Optimizes by potentially skipping text characters, offering speed advantages but with occasional re-scans.
- Developed a criterion to select the optimal algorithm based on CBG structure.
- Incorporated methods for approximate matching with a tolerance for errors.
Main Results:
- Both new algorithms demonstrate significantly faster performance compared to RE search techniques.
- Algorithm 2 is generally faster than Algorithm 1, especially for certain CBG structures.
- Experimental results using the PROSITE database confirm the superior speed of the proposed algorithms in most cases.
- The criterion for algorithm selection effectively identifies the most efficient method a priori.
Conclusions:
- The developed CBG matching algorithms offer a substantial improvement in speed and simplicity over existing RE-based methods.
- These algorithms are highly effective for protein pattern matching and other applications involving CBG patterns.
- The ability to perform approximate matching further enhances the utility of these algorithms in biological sequence analysis.