Fast filtering for RNA homology search

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• RNA homology search benefits from secondary structure information, but traditional methods like covariance models are computationally expensive.
• Existing acceleration strategies often use sequence-only filters, potentially losing structural information.

Purpose of the Study:

• To develop a computationally efficient filter for RNA homology search that incorporates secondary structure information.
• To improve the speed and scalability of RNA secondary structure-based homology detection.

Main Methods:

• Introduction of the multi-segment CYK (MSCYK) filter, employing a heuristic of ungapped structural alignment.
• Implementation of a vector-parallel approach for the MSCYK filter.
• Integration of MSCYK with existing gapped alignment methods into a filtering pipeline.

Main Results:

• The MSCYK filter reduces computational time complexity from O(N⁴) to O(N³) and space complexity from O(N³) to O(N²).
• Vector-parallel implementation of MSCYK achieves up to a 100-fold speed-up compared to standard methods.
• Combined filtering pipeline shows synergistic results, maintaining RNA secondary structure scoring throughout.

Conclusions:

• The MSCYK filter provides a significant computational advantage for RNA homology searches.
• This method enhances the efficiency of RNA secondary structure analysis in large-scale genomic studies.
• The developed filtering pipeline offers a powerful and scalable approach for RNA bioinformatics.