RNA Secondary Structure Dynamic Programming Comparison Algorithm

RNA molecules are folded into different shapes of RNA secondary structures in different ways.RNA structures determine RNA function,and different structures have different functions.Therefore,the RNA secondary structure comparison is of great significance to the prediction of the secondary structure of RNA and the functional research of RNA.Because of the complexity of RNA folding,compared with computer algorithm,it can get better and better comparison results,and reduce the error rate of manual comparison.First of all,based on the sequence representation,a dynamic programming based RNA secondary structure comparison algorithm is proposed.The sequence representation is a sequence of RNA secondary structures,each of which is an RNA pairing information.Based on the Sequence representation and Dynamic programming,the RNA secondary structure comparison algorithm and Dynamic Planning Sequence algorithm(DPS)are proposed.Sequence length and the length of the original RNA secondary structure,the dynamic programming algorithm can be used to calculate the distance between the two sequences,through the distance to measure the size of the two RNA secondary structure.The similar distance results is inversely proportional to the degree of similarity.The results of small similarity is rather high.Second,from DPS than results and running time of the algorithm for the consideration,in order to achieve algorithm optimization for the purpose,based on Dynamic programming multithreaded weighted RNA secondary structure alignment algorithm,namely the weighted Dynamic Planning Sequence(Weight Adjustment Dynamic Planning Sequence,hereinafter referred to as WA-DPS)algorithm.Adjust the weights as the proportion of the value of the elements in the sequence,will compare the results give decisive strong sequence point certain weight value,improve the ratio on the results of the difference degree,improve the precision of RNA secondary structure sequence alignment results.And reduce the time cost of the algorithm by using multithreaded methods.In addition,the algorithm is optimized and proposed in parallel weighted dynamic programming,namely the cwDPS-rsc algorithm,in terms of the comparison effect and computation time of DPS-rsc algorithm.In the process of calculation using the weight adjustment mechanism,improve the calculation to the structure difference influence the sequence of points for the calculation of the weight,the result difference and similarity is more significant,improve RNA secondary structure data sets at the degree of differentiation.And reduce the time cost of the algorithm by using parallel methods.Finally,the feasibility of DPS algorithm and wa-dps algorithm is verified by three comparison experiments.In the first experiment,DPS algorithm,RBP algorithm and Hausdorff algorithm were used to compare the sequence of RNA secondary structures in four sets of data sets.In the second experiment,the improvement effect of wa-dps algorithm was evaluated by comparing the results of the algorithm with the real RNA secondary structure sequence as the reference basis.The third experiment is based on the experimental running time to verify the improvement effect of the parallel wa-dps algorithm.Three experimental results show that the DPS algorithm is very feasible,and the wa-dps algorithm is more different than the results,and the parallel wa-dps algorithm can save the experimental time.