A Survey of Compute Intensive Algorithms for Ribo Nucleic Acids Structural Detection

Abstract

Problem statement: Finding an accurate RNA structural alignment from primary sequence due to it is time consuming and computationally NP-hard problem is a major bioinformatics challenge. According to our investigation majority of current researches were concerned on achieving faster execution time, improving space complexity and better cache management. Recently one research introduced cache-efficient Chip Multiprocessor (CMP) algorithms with good speed-up to exploit parallelism in detection the critical path length. Our contribution in this article was a comprehensive survey of methods for solving RNA secondary structure prediction with Pseudoknots (PK) and sequence alignment in bioinformatics. The aim was to highlight the challenges related issues which would provide sufficient information to assist the new coming researchers in this field as well as a good reference guide for bioinformatics professionals. Approach: We computed various algorithms that predicted an RNA molecules secondary structure from primary sequence, without pseudoknots from one side and pseudoknotted RNA secondary structure in the other side. Furthermore, we also reviewed and compared in two tables the methods that developed for RNA structural predictions. Results: Our findings of this survey confirmed that Dynamic Programming (DP) method via CMP algorithms can be used to predict the RNA secondary structure with simple PK and it gives good results. Conclusion: The methods for predicting RNA's structural are coming in two groups: Firstly, pseudoknotted RNA structural problem is computationally complex and secondly, common methods significantly gave not accurate enough results for predicting pseudoknotted RNA.