Multiple Structural Alignment Of RNA Sequences Based On Stem Fragments

The secondary structure prediction of RNA based on comparative genomics is a hot problem, being one of the key processes of this method, MSA(Multiple Sequences Alignment) affects the precision of prediction greatly. For the loss of structural information in traditional MSA algorithms, the problem of structure alignment algorithms becomes prevailing, and many algorighms are developed. But because of the memory limitation, the structure alignment algorithms in existence are difficult to deal with sequences of more than 1000 bases lenth, and another problem is that structure alignment algorithms maybe obtain a faulty result caused by ignoring pseudoknot. To solve these problems, this thesis presents a new method of structure alignment based on stem fragments for RNA sequences, the main work and contributions of this thesis are as follows:1. An algorithm of finding and comparing stem fragments is presented. We use a sliding window to improve the method of finding stem fragments based on folding matrix, and use parallel technique to reduce the time complexity caused by the sliding window.2. An algorithm of pairwise structural alignment of RNA sequences is given based on the stem. Through the sequence splitting and recursion, we make the pairwise structural alignment by dividing long sequences into short sequences based on the stems, and given an algorithm based on the stem alignment.3. An algorithm of MSA of RNA sequences based on the stem is designed. We use the weight matrix and the direction-tree to construct the multiple sequences alignment based on pairwise structural alignments.We also introduce a parallel technique to reduce the time complexity. The numerical exprement shows that our method is sufficient to solve the structural aligment of RNA sequences with no more than 2000 lenth with high precision. Our method obtain better alignment results from sequences with high similarity, compared with PMmulti and MARNA.