Research On Algorithms Of RNA Secondary Structure Prediction

RNA can act as a carrier of genetic information, a catalyst of biochemical reactions, an adapter molecule in protein synthesis, and a structural molecule in cellular organelles.The function of a RNA molecule has a close relation with its secondary structure. So the research work about RNA secondary structure has become more and more important.The Most accurate structure can be determined by X-ray diffraction or nuclear magnetic resonance,but this is difficult because not only it is expensive and slow but also most RNAs can not be crystallized currently.Obviously it is necessary to study RNA secondary structure by means of some prediction algorithms based on computation theory,these prediction algorithms can raise efficiency greatly for scientists to know RNA secondary structure.Firstly,some major algorithms and theories for RNA secondary structure prediction are introduced in this dissertation,they include the methods based on thermodynamic energy minimization principle(such as Zuker's mfold mehod,Genetic simulated annealing algorithm,Hopfield network method,and Immune particle swarm algorithm), phylogenetic comparative methods(covariance mutation prediction model, stochastic context free grammar algorithm),and classification method with BP neural network. The author analyzes the advantage and limitation of these algorithms by comparing them,and then gives a summary of development demand and trendency for RNA secondary structure prediction.Nextly,a modified artificial fish swarm optimization algorithm is presented in this paper,which can self-adaptively change some parameter's values , improve the behavior of fish and reduce the search space,therefore it can rapidly close to the global best result by avoiding the blindness of searching at the later stage owing to the improvement on basic fish swarm algorithm.At the same time,a RNA secondary structure prediction model based on modified fish swarm algorithm is presented,state space that is described with sets in our model largely shrinks the search space,so,when compared with SetPSO(Particle Swarm optimization with Set,SetPSO) method and GSA(Genetic Simulated Annealing,GSA)method,our algorithm not only is effective but also has much lower runtime cost.Thirdly, the PSO(Partcle Swarm Optimization,PSO)algorithm is analysed in detail.There are some defects for its application in solving combinatorial optimization problems,for example,the PSO algorithm is prone to stay in local optimal results instead of the global optimal objective answer due to it's rapid convergence.Aiming at this drawback,an improved algorithm called LEPSO(Local Elite Particle Swarm Optimization,LEPSO) algorithm is proposed.In the new algorithm,every particle has fixed neighbours, and adjusts its state for next step according to its past optimal value and the local impact factor of its neighbours in every iteration. Because of keeping diversiform directions of movement for each particle,the new algorithm can easily find global best result. The author realizes a RNA secondary structure prediction model with LEPSO algorithm,some new operators are defined to match the velocity and position formula,they skillfully avoid assigning values for all parameters,so that make the algorithm easily understandable.Lastly,the author sets up a set of labels which is called as eNSSEL(extended New Secondary Structure Element Label,eNSSEL) labels,these labels not only can express the simple stem-loop motif in a RNA secondary structure,but also can describe pseudoknots structure.Each base in a RNA molecule can be marked by a kind of label,so a RNA sequence can be converted to a label sequence. Corresponsively,a label sequence can be reverted to RNA secondary structures with a simple method.If only a label sequence for a RNA molecule has been known, the secondary structure for the molecule can be acquired by reversion.When a label is regarded as a structure type associated with a base in RNA molecule,the problem for RNA secondary structure prediction can be considered a classification problem. Consequently a SVMs(Support Vector Machines,SVMs) model for RNA secondary structure prediction is created in terms of classification theory.Experiment shows that this model not only can solve high runtime complexity problem of traditional algorithms, but also can efficiently predict long RNA sequences which are difficult with traditional folding algorithms.it gives a new thought of RNA secondary structure prediction for long sequence with pseudoknots.