Faster RNA Similarity Searches
Author Information
Author(s): Eric P. Nawrocki, Sean R. Eddy
Primary Institution: Howard Hughes Medical Institute, Janelia Farm Research Campus, Ashburn, Virginia, United States of America
Hypothesis
Can query-dependent banding (QDB) improve the speed of RNA similarity searches without sacrificing accuracy?
Conclusion
The QDB method significantly accelerates RNA similarity searches while maintaining sensitivity and specificity.
Supporting Evidence
- QDB reduces the average case time complexity of CM alignment from LN^2.4 to LN^1.3.
- The method provides a 4-fold speedup for typical RNA queries.
- Benchmarks show increased sensitivity and specificity due to improved parameterization.
Takeaway
This study introduces a new way to search for similar RNA sequences faster, making it easier for scientists to find important RNA structures.
Methodology
The study developed a new algorithm called query-dependent banding (QDB) to speed up RNA similarity searches by precalculating regions of the dynamic programming lattice.
Potential Biases
The reliance on primary sequence conservation may introduce bias in RNA family alignments.
Limitations
The QDB method may sacrifice some accuracy for speed, and optimal alignments are not guaranteed to lie within the high-probability bands.
Digital Object Identifier (DOI)
Want to read the original?
Access the complete publication on the publisher's website