Rna Secondary Structure Prediction Based On Tabu Search

Ribonucleic acid (RNA) is an important biological molecule, which plays a key role in catalyzing RNA cleavage and splicing, modifying pre-RNA, regulating gene expression etc, not only carrying and transferring the genetic information in cell. How to play the biological functions of RNA, what other potential fuctions RNA has, and how to utilize the known RNA to design drugs and cure diseases. These tasks are before us. Especially, after determining all gene sequences in 2001, Human Genome Project (HGP) brought a mass biological data. It is significant to accelerate the study of RNA.RNA structure is essential for its biological function. There are three structural levels in RNA: primary, secondary and tertiary structure. In contrast to RNA primary structure, its secondary and tertiary structure has rich biological significance. The RNA structure is key to know the function mechanism of RNA. Due to fast decomposition and hard crystallization of RNA, it is accurate to determine RNA tertiary structure by the way of X-ray crystallography and nuclear magnetic resonance (NMR), but these methods are expensive and costly. Especially, these methods do not well adopt to analyze the mass biological data. So far, to predict RNA secondary structure is an important subject to further study the RNA tertiary structure. It is a main avenue of research of RNA secondary structure in virtue of the algorithm based on computer simulation.In this thesis, we discuss a novel method for predicting RNA secondary structure based on Tabu Search. The thesis includes the following work:1. set forth the biology background of RNA, and give the description of RNA secondary structure related;2. analyze the mainly known methods of predicting RNA secondary structure from the perspective of algorithm design idea, including the comparative sequence analysis method, dynamic programming method, and heuristic method, and give the merits and shortage of the methods;3. put forward a novel method for predicting RNA secondary structure called RNA secondary structure prediction based on Tabu Search (RNATS). RNATS based on Tabu Search, takes the measure of stem similarity, constructs the neighbourhood and diversification region by adding, deleting and substituting stack, designs the tabu list, the visited region list and the radius of visited region to avoid circuity search and explore the unvisited regions, and adopts two phases of intensification search and diversification search to exploit the RNA secondary structure with minimum free energy. The experimental simulation proves that RNATS is efficient to search the minimum free energy and predict RNA secondary structure.