RNA Secondary Structure Prediction Algorithm Based On Dynamic Weighted Matching Algorithm

RNA is a kind of molecular that plays an important role in the biological genetics. Research on the structure and function of RNA is one of the important areas of bioinformatics.Today,the knowledge of function of RNA itself has been expanded greatly. Research on RNA structure and function may be taken as the breakpoint of research on structure and function of protein ,it also may be taken as the breakpoint of research on the gene information of DNA sequence. Function of biological molecular relys on a certain sencondary structure or tertiary structure,or even quarternary structure. Because of fast decomposition and hard crystallization of RNA, it is not easy for experiment methods such asX-ray crystallography and NMR to determine RNA 3D-structures. Moreover, using this means is not only very time consuming and labor intensive but also costly.Therefore, the use of computational methods to predict RNA structure is highly desired and effective.In this thesis, we review and summarize various existing RNA structure prediction methods as well as explore the developing direction of the leading RNA structure prediction methods of new generation. Besides putting forward some new thinkings, we have also put forward a new algorithm on RNA secondary structure prediction. The thesis mainly includes two parts of following contents and conclusions:(1) Currently some important prediction methods of RNA secondary structure are introduced, and the existing problems among them are analyzed. Firstly, two models of the traditional comparative sequence analysis method-covariance model and stochastic context-free grammars model are roughly described here. Secondly, we introduce the famous free energy minimization algorithm and base pair maximization algorithm, and detailedly explain their realization with dynamic programming algorithm as well as RNA free energy parameters. Thirdly, one kind of heuristic algorithm based on stem combination is introduced,which contains helix stacking method, genetic algorithm and neural network algorithm etc. These methods stand for some new ideas on the way to seek RNA structure predictionmethods of new generation. Finally, through the comparison analysis of above algorithms, we conclude the future requirements of RNA structure prediction and list some websites about RNA structure prediction.(2) On the basis of Maximum Weighted Matching (MWM) algorithm We establish an RNA dynamic weighted matching model and study its potentiality to predict pseudoknots. we introduce a dynamic weight related with stem length, which use a recursive algorithm to predict RNA secondary structures by searching the stem structure with maximum weight summation step-by-step. This algorithm not only avoids the complicated free energy calculation, but also attains higher prediction accuracy. Moreover, our algorithm can predict some types of potential pseudoknots in the RNA structure. It is superior to free energy minimization algorithm in ease to realize, algorithm complexity, potentiality to predict pseudoknots and ability to utilize information.So we can find out that this type of model is most hopeful to develop into the leading method in the future RNA secondary structure prediction.