Shuffled Flog Leaping Algorithm For RNA Secondary Structure Prediction And Its Parallelization

As mankind enters the post-genome era, it is an important task to obtain the biologicalfunction of biomolecules. Because RNA is one of the most important molecules in thebiological system, the inference of its function becomes a key task. RNA biological functionsare determined by its secondary and tertiary structures, and the experimental methods, whichare used to determine the secondary and tertiary structures, are extremely expensive anddifficult. So those experimental methods cannot be widely used in practice. There has been alarge number of RNA sequence information, therefore, on the basis of known biologicalstructure and functional characteristics, bioinformatics method, which uses computersimulation and mathematical modeling to predict the secondary structure and tertiary structureof RNA, has become an effective method. Today, RNA secondary structure prediction hasbecome an important task and a hotspot in the field of bioinformatics. Due to the fact thatbase stacking force is the main force of the stable RNA secondary structure and thecontinuous base-stacking constitute stems, structure prediction can be translated into acombinatorial optimization problem which is based on a combination of stem regions and thepursuit of free energy minimization. This prediction method has great progress in the past tenyears.Computational intelligence is a branch of artificial intelligence. Many computationalintelligence methods, such as genetic algorithm, simulated annealing algorithm and manyswarm intelligence algorithms have been used in RNA secondary structure predictionsuccessfully. Specifically, swarm intelligence algorithms, which have good performance oncombinatorial optimization problems, have showed promising results. Shuffled frog leapingalgorithm (SFLA) is a newly proposed swarm intelligence algorithm. SFLA has been appliedto RNA secondary structure prediction and has good results. Aim to improve the predictionprecision and speed up the computation, this thesis introduces immune memory operator andrandom disturbance operator into SFLA and studies the parallelization of SFLA.Firstly, this thesis introduces some basics about RNA, such as composition, classification,structures and its graphic representations, which serve as the basis of prediction algorithm.Secondly, main RNA secondary structure prediction methods at present are reviewed.Emphasis is put on such algorithms as genetic algorithm, simulated annealing, swarmintelligence algorithms and some heuristic methods. Then research status, energy model,coding mechanism, implementation and their advantages and disadvantages of those fouralgorithms are analyzed.Thirdly, principles of traditional SFLA and discrete shuffled frog leaping algorithm(DSFLA), which has been applied to RNA secondary structure prediction, are also analyzed.To enhance its performance, this thesis introduces immune memory operator and random disturbance operator into DSFLA. Simulation results show those operators can improveDSFLA’s performance.Finally, parallel computer system and parallel algorithm design theory are introduced.OpenMP parallel programming model is introduced into DSFLA. Parallel DSFLA isimplemented and simulations are carried on multi-core computer.