Research On Prediction Of RNA Secondary Structure With Pseudoknots

As a kind of biological macromolecules,RNA plays an important role in the cells' life,including gene expression,gene transformation,gene regulation and the catalysis.Unlike DNA,RNA structure is more complicated that's why RNA has rich functional features.On the one hand,the cost of detecting RNA spacial structure using physical experiment method is so high.On the other hand,only rely on the physics experiment cannot meet the vast amounts of sequences data.So predicting RNA secondary structure with algorithm has become an important approach.There is a class of substructure formed by stem nesting and crossing called pseudoknots.Due to the pseudoknots have been confirmed that playing a key role in many kinds of RNA catalysis,so recently researchers pay more attention to it.In this paper,the genetic algorithm is applied to the RNA secondary structure prediction with two kinds of pseudoknots.And verifying the usability and effectiveness of the algorithm through the test.Moreover,we put forward an heterogeneous parallel algorithm based on OpenCL to solve the problem of prediction efficiency.We analysis the parallelizability of serial prediction algorithm and redistribute the computing task.Using heterogeneous mode with CPU+GPU accelerate the prediction algorithm.Finally,we compare the difference of efficiency between serial algorithm and parallel algorithm through test.The main work and contributions are as follows:(1)We propose an improved genetic algorithm.Comparing with traditional genetic algorithm,the improved genetic operation makes the prediction algorithm more close to the folding process of RNA secondary structure.It based on minimum free energy,combining Mathews&Turner and Dirks&Pierce energy parameters,can predict two kinds of pseudoknots including H-type pseudoknots.Finally,we select a test set from the RNA STRAND database.Test result shows that the sensitivity can reach 0.79 and the positive predictive value can reach 0.81.It is proved that the prediction algorithm is effective and can be a reference of RNA secondary structure analysis.(2)The prediction algorithm of RNA secondary structure with pseudoknots based on genetic algorithm is inefficient.To solve this problem,we propose an accelerated algorithm based on Open CL.Firstly,we analysis the parallelizability of serial prediction algorithm and find that two steps of the serial algorithm can be accelerated which are filling with helix matrix and individual evolution.Secondly,we accelerate those two steps using GPU based on OpenCL.Finally tested in the same test set,compared with serial algorithm,the improved heterogeneous parallel algorithm can obtain the speedup of 2.8 x times on average.It is proved that the parallel algorithm reduces the computing time effectively to improve the efficiency of prediction.