Research On Prediction Algorithm Of RNA Secondary Structure Including Pseudoknots

The prediction of RNA secondary structure is a hotspot in RNA research. Many secondary structure prediction methods have been presented and rich results have been achieved. But most of these methods cann't properly deal well with pseudoknots prediction, either of relatively high complexity or of low accuracy. On this issue, this thesis studies a more reliable covariance model and a more effective heuristic algorithm for the consensus structure prediction of homology RNA sequences. With the relatively low complexity, the algorithms presented in this thesis improve the accuracy of pseudoknots prediction and provide multiple suboptimal structures. The thesis mainly includes two sections of following contents and conclusions.(1) Based on stacking covariance and minimum free energy, the thesis presents an iteration algorithm to predict the consensus structure with pseudoknots of homology RNA sequences. With emphasis on the impact of neighbour base pairs on covariance, the algorithm introduces a model of stacking covariance into Ifold and combines with minimum free energy to assess RNA secondary structure with pseudoknots though iterations. The numerical test shows that this algorithm can correctly predict pseudoknots, with the mean sensitivity and specificity better than that of other algorithms. The performance of the algorithm achieves the best result when the factor of stacking covariance is 5:1.(2) A seed set expansion algorithm for predicting multiple suboptimal consensus structures of homology RNA sequences is presented. The algorithm applies seed set expansion algorithm derived from HotKnots to predict consensus structure of homology RNA sequences. The seed sets are made up of seeds and expanded to multiple suboptimal consensus structures. The numerical test shows that multiple suboptimal structures are all close to the reference structures and some stable substructures can be achieved. The mean sensitivity and specificity of the algorithm are better than that of the reference algorithms and the time complexity is more than that of iteration algorithms and far less than that of dynamic programming algorithms.