Study Of RNA Secondary Structure Prediction Algorithm Based On Stem

With the completion of human genome sequencing, deciphering genetic information and getting function of biological molecules have become an important task of post-genome age. In most of the time, characteristic of RNA molecular structure (tertiary structure) determine the function properties of molecules, and the researchers of the modern bioinformatics believe that the secondary structure is a necessary phase from a sequence to the tertiary structure, so the study of RNA secondary structure is one focus of bioinformatics.This paper will research for the RNA secondary structure prediction algorithm based on the fact that stems are treated as the basic unit of RNA secondary structure.Firstly, we start from the intelligent optimization algorithm, and propose a RNA secondary structure prediction algorithm HTARP based on a hybrid optimization of ACO algorithm and TS algorithm. In HTARP, stems are treated as the points of graph, and relationships of the non-free coexistence between stems are treated as edges to construct the undirected graph. Absorbing the local search ability of ACO and the global optimum ability of TS, this method gets the stem-combination through finding the greater independent set in undirected graph, and achieves the RNA secondary structure prediction. Experimental results of real RNA sequences show that it's valid for the RNA secondary structure prediction.After doing deep study on the relations theory of graph theory, we propose a new algorithm QuasiRP for predicting RNA secondary structure. The directed graph which is constructed by stems and free coexistence relationship is the basis of graph theory, and RNA secondary structure prediction problem is transformed to find the greater chain by quasi-order relationship. Finally, we do some experiments in the data set of the free sequences and pseudoknot sequences, and compare with the results of RNAStructure, PKnotsRG and GS algorithm. The experimental results show that this method is valid for most sequences and has better accuracy in the prediction based on the reduced time complexity.