Related Experiment Videos
Calculating the exact probability of language-like patterns in biomolecular sequences
1atteson@peaplant.biology.yale.edu
Proceedings. International Conference on Intelligent Systems for Molecular Biology
|October 23, 1998
Summary
New algorithms precisely calculate the probability of random strings matching regular expressions, aiding motif searches and gene finding. These methods are faster and more versatile than previous approaches, handling complex patterns and general probability models like Markov chains.
Area of Science:
- Computational biology
- Bioinformatics
- Algorithm design
Background:
- Statistical significance is crucial for pattern searches in biological sequences.
- Previous algorithms had limitations in speed, pattern complexity, and probability models.
Purpose of the Study:
- To develop novel algorithms for exact probability computation of random string matching regular expressions.
- To improve upon existing methods in terms of speed, pattern flexibility, and model generality.
Main Methods:
- Developed exact computation algorithms for regular expression matching probabilities.
- Extended pattern matching to include arbitrary length gaps.
- Incorporated general probability models, including Markov chains.
Main Results:
- Algorithms are faster and more efficient for common cases.
- Successfully computed probabilities for PROSITE patterns up to length 2000, significantly larger than previous limits.
- Demonstrated feasibility for large DNA sequences (up to 1 megabase) and gene models.
Conclusions:
- The new algorithms provide a computationally feasible and more general approach for statistical significance assessment in sequence analysis.
- These advancements enable more accurate and extensive pattern discovery in genomics and bioinformatics.