Related Experiment Video
Updated: May 8, 2026
07:55
Using SCOPE to Identify Potential Regulatory Motifs in Coregulated Genes
Published on: May 31, 2011
PMS6: A Fast Algorithm for Motif Discovery
Shibdas Bandyopadhyay1, Sartaj Sahni, Sanguthevar Rajasekaran
1Department of CISE, University of Florida, Gainesville, FL 32611.
IEEE ... International Conference on Computational Advances in Bio and Medical Sciences : [Proceedings]. IEEE International Conference on Computational Advances in Bio and Medical Sciences
|August 21, 2013
Summary
A new algorithm, PMS6, significantly speeds up (l, d)-motif discovery, finding strings in datasets with few mismatches. PMS6 offers substantial runtime and preprocessing improvements over previous methods like PMS5.
Area of Science:
- Bioinformatics
- Computational Biology
- Algorithm Development
Background:
- Motif discovery is crucial for understanding biological sequences.
- Existing algorithms face challenges with large datasets and permissible mismatches.
- The (l, d)-motif discovery problem requires finding short sequences (motifs) present in a dataset with a specified number of allowed differences.
Purpose of the Study:
- To introduce PMS6, a novel and efficient algorithm for the (l, d)-motif discovery problem.
- To evaluate the performance of PMS6 against the fastest existing algorithm, PMS5.
- To demonstrate the computational advantages of PMS6 in terms of runtime and preprocessing time.
Main Methods:
- Development of the PMS6 algorithm for (l, d)-motif discovery.
- Comparative analysis of PMS6 and PMS5 on various challenge instances (e.g., (21,8), (17,6), (23,9), (13,4)).
- Measurement of runtime and preprocessing time for both algorithms.
Main Results:
- PMS6 demonstrates a runtime advantage over PMS5, with ratios ranging from 1.69 to 2.20.
- PMS6 significantly reduces preprocessing time, being up to 34 times faster than PMS5 for (23,9) instances.
- When factoring in preprocessing, the overall runtime ratio of PMS5/PMS6 ranges from 1.95 to 2.75.
Conclusions:
- PMS6 represents a significant advancement in motif discovery algorithms.
- The new algorithm offers substantial speedups, making it more suitable for large-scale biological data analysis.
- PMS6 provides a more efficient solution for identifying (l, d)-motifs compared to prior methods.
