Reseach Of RNA Secondary Structure Comprision Based On Dynamic Time Warping

The research of Ribonucleic Acid is one of the most important parts of the field of bioinformatics. RNA structure determines the biological function of RNA. In structural chemistry, structural biology and bioinformatics, Ribonucleic Acid secondary structures similarity comparison is a fundamental problem. RNA secondary structures similarity comparison can promote RNA secondary structure prediction and the research of RNA function.Firstly, this thesis describes and presents a new representation of RNA secondary structures, which expresses RNA secondary structure as a sequence series which consist of non-negative integers. This representation won’t be restricted by pseudoknots and can represent RNA secondary structures completely and uniquely.Secondly, this thesis proposes a new algorithm based on Dynamic Time Warping and the representation presented in this thesis to compare the similarity between RNA secondary structures, called DTW-RSC. With the algorithm, RNA secondary structures convert into time series as long as RNA series. And then calculate the warping distance between time series by Dynamic Time Warping inorder to measure the similarity between RNA secondary structures. The smaller the warping distance is, the more similar the RNA secondary structures are.Thirdly, this thesis improves DTW-RSC focus on the effective of algorithm and the cost of calculation process, and proposes a new RNA secondary structures comparison algorithm based on constrained and weighted Dynamic time warping, called CWDTW-RSC. CWDTW-RSC joins global constraint radius to narrow the range of search when calculating the warping path. And also, CWDTW-RSC increases the weight of point pair which makes greater influence on the differences of RNA secondary structures through weight adjustment. CWDTW-RSC makes the difference and similarity of the results more significant, increase the discrimination of comparison results of similar RNA secondary structures.Finally, this thesis proves the feasibility of the two algorithms proposed through two sets of experiments. The first set of experiments compare four RNA secondary structures data sets with different characters by DTW-RSC. In the second experiment, we treat the time cost and the distribution of results as evaluating indicator. The experiment proves that CWDTW-RSC presents greater discrimination of comparison results.