RNA分子通过不同的折叠方式,折叠成不同形状的RNA二级结构,RNA结构决定RNA功能,不同的结构具有不同的功能。因此RNA二级结构比对对研究RNA二级结构的预测以及RNA的功能性的研究有重要意义。由于RNA折叠方式较复杂,通过计算机算法进行比对,可以得到更准确的比对结果,减少人工比对出错率。首先,在序列表示法的基础上提出基于动态规划的RNA二级结构比对算法。序列表示法是将RNA二级结构表示成序列,序列中的每一个元素为RNA配对信息。基于序列表示法并结合动态规划,提出RNA二级结构比对算法,动态规划序列算法(Dynamic Planning Sequence,简称DPS)。序列长度与原始RNA二级结构的长度一样,用动态规划算法来计算两条序列间距离,通过距离的大小来衡量两条RNA二级结构的相似程度,距离结果和相似性程度呈反比,结果小的相似性反而高。其次,出于从DPS算法的比对结果和运行时间二者考虑,以达到算法优化为目的,提出多线程加权基于动态规划的RNA二级结构比对算法,即加权动态规划序列(Weight Adjustment Dynamic Planning Sequence,简称WA-DPS)算法。将权值作为调整序列中元素的值的比重,将对比对结果决定性较强的序列点赋予一定的权重值,提高比对结果的区别度,改善RNA二级结构序列比对结果的精准性。并通过使用多线程的方法,减少算法的时间花费。最后,通过三个对比实验分别验证DPS算法和WA-DPS算法的可行性。第一个实验,分别在四组不同数据集上运用DPS算法、RBP算法以及Hausdorff算法,进行RNA二级结构序列比对。第二个实验,以算法的比对结果是否更加接近真实RNA二级结构序列为参考依据,来评价WA-DPS算法的改进效果。第三个实验,以实验运行时间为参考依据,来验证并行WA-DPS算法的改进效果。三个实验结果显示,DPS算法是具有非常好的可行性,WA-DPS算法比对结果差异性更高,并行WA-DPS算法能节省实验时间。