Research Of RNA Secondary Structure Prediction Algorithm Including Pseudoknots

With development of research on bioinformatics and RNA, RNA is no longer simply considered as an information intermediary from DNA to proteins. In RNA viruses and some animal cells, RNA serves as the carrier of germ plasma and control the combining of proteins. Moreover, in some cancer cells or embryo cells, RNA can even transfer into DNA. The functions of RNA are determined by its structures, and research on RNA secondary structure prediction algorithms has become a keystone in the domain of biological information processing. As a kind of complex secondary structure in RNA, pseudoknots determine some important biological functions. So it is a hotspot to study the RNA secondary structure prediction algorithm including pseudoknots in the research of RNA secondary structure prediction algorithm.First of all, this thesis advances a genetic algorithm of RNA secondary structure prediction based on dynamic weigh. Dynamic weight results from improvement of maximal weight, which comes from improvement of maximal stack. On the basis of RNA secondary structure prediction genetic algorithm based on free energy minimization, this thesis replaces the free energy minimization model with the dynamic weight model. As indicated by the experiments, the new algorithm can not only predict pseudoknots, but can predict complicated non-plane pseudoknots as well.Second, this thesis proposes RNA secondary structure prediction algorithm based on fast dynamic weighted matching. This algorithm, on the one hand, has the same great accuracy and ideal space complexity of O(n6) as dynamic weighted matching algorithm does. On the other hand, it has been improved on the basis of dynamic weighted matching algorithm. That is, first, by importing fast searching of max dynamic weighted stem algorithm, time complexity of dynamic weighted matching algorithm, which is O(n3logn), descends to O(n3) of the new algorithm; Second, the new algorithm expands the searching area of pseudoknots. Experiment indicates that compared with dynamic weighted matching algorithm, RNA secondary structure prediction algorithm based on fast dynamic weighted matching can predict more possibly existing pseudoknots.