Research On Prediction Of RNA Secondary Structure With Pseudoknots

Ribonucleic acid (RNA) is a kind of essential biological macromolecules, andplays a key role in connecting DNA with protein in the process of gene expression.RNA has important biological functions like catalysis and regulating gene expression.The structure of a RNA molecule affects its functions. Because using laboratorymethods to determine RNA structures cost enormously, predicting RNA structures withalgorithms has become an important approach. Pseudoknot is a kind of RNA tertiarystructures formed by stem nesting. Pseudoknot is so complex that predicting it hasbecome a challenge.In this thesis, tabu search and cuckoo search are introduced into RNA secondarystructure prediction with pseudoknots. By designing free-energy based objectivefunction which considers all pseudoknot types, and designing algorithm modificationsfor tabu search and cuckoo search, two novel prediction algorithms are proposed.Results of stimulation experiments have proved that the two proposed algorithms areuseful and effective. The main contributions of this thesis include:1. A novel tabu search based algorithm to predict RNA secondary structures withpseudoknots is proposed. By using the original intensification search mechanism toexploit the regions around the current solution, and adding a diversification searchmechanism to enhance the diversity of solutions, a free-energy based objective functionis optimized effectively in order to predict RNA secondary structures with pseudoknots.Stimulation experiments were conducted on13real RNA sequences including tobaccomosaic virus sequence and beet western yellow virus sequence, sensitivity andspecificity of the proposed algorithm on sequences with H-type pseudoknots are89.77%and89.03%respectively, sensitivity and specificity results on sequences withpseudoknotted structures that are not H-type pseudoknots are63.56%and63.41%respectively, sensitivity and specificity results on all sequences are enhanced by5.65%and8.63%by average comparing to the results of STAR, HotKnots and RnaPredictalgorithms, and the prediction time efficiency is improved by20.35times by averagecomparing to the results of RnaPredict algorithm. 2. A novel algorithm based on cuckoo search model to predict secondary structureswith pseudoknots is proposed. By adding a tabu search mechanism and an adaptiveparameter function, the nest search mechanism and egg-abandon search mechanism canbe improved to minimal optimize a free-energy based objective function by stemcombination and predict RNA secondary structures. Stimulation experiments wereconducted on13real RNA sequences including mouse mammary umor virus sequence,sensitivity and specificity of the proposed algorithm on sequences with H-typepseudoknots are94.23%and93.06%respectively, sensitivity and specificity results onsequences with pseudoknotted structures that are not H-type pseudoknots are71.17%and77.04%respectively, sensitivity and specificity results on all sequences areenhanced by10.21%and17.03%by average comparing to the results of STAR,HotKnots and RnaPredict algorithms, and the prediction time efficiency is improved by11.28times by average comparing to the results of RnaPredic algorithm.