【作者】 陆斌；

【导师】 骆志刚；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2009， 硕士

【摘要】 RNA序列结构比对是生物信息学的基础研究内容之一。通过对RNA序列和结构进行相似度比较,人们可以发现RNA序列中蕴含的功能和进化信息,对RNA序列分类、二级结构预测、发现序列保守区域都具有极其重要的研究意义。本文首先介绍了RNA序列结构的基本知识,给出了RNA序列结构比对问题的详细描述,分析了已有的RNA序列结构比对算法,对现有算法进行了分析和比较,并指出了当前比对算法存在的主要问题。接着详细阐述了树模型的构造和操作,给出了RNA序列结构与树模型的对应关系。针对目前低相似度RNA序列比对结果准确度不高的问题,本文基于RNA树形结构模型,提出了一种基于动态规划思想的RNA双序列结构比对算法,对算法进行了设计和实现。通过比较与其他比对算法在同一数据集上的运行结果,本文算法在低相似度RNA序列比对上表现出较高的准确度。在RNA双序列结构比对的基础上,本文结合T-coffee算法思想,设计并实现了RNA多序列结构比对算法,通过数值实验讨论了RNA多序列比对结果与序列数目及序列平均相似度的关系,同时验证了本文算法的有效性。更多还原

【Abstract】 RNA sequence-structure alignment is one of the basic research contents in bioinformatics. Through the similarity comparison of RNA sequences and structures, people are able to find the functional and evolutional information hiding in RNA sequences. This has vital researching significance in the classification of RNA sequences, the prediction of RNA secondary structures and finding conserved regions in sequences.The paper first introduces the basic knowledge of the RNA sequence and structure, gives the detailed description of RNA sequence-structure alignment problems, analysis the existing RNA sequence-structure algorithms, and then gives analysis and comparison of present algorithms and points out the main problems of the present algorithms, describes the constructing and operating on the tree model in detail, give the relation between RNA sequence-structure and tree model.Considering the unsatisfied accuracy of current sequence-structure alignment algorithms on low similar RNA sequences, this paper presents a pairwise RNA sequence-structure alignment algorithm based on dynamic programming using the tree model, design and implement the algorithm. The comparison with other algorithms on the same data sets shows that the algorithm of this paper can give a higher accuracy on the low similar RNA sequences. Furthermore, Based on the ideas of T-coffee, the pair-wise RNA sequence-structure algorithm of this paper is extended to a multiple RNA sequence-structure alignment algorithm. Then, the relation between the results of the multiple RNA sequence-structure alignment and the number of sequences, average sequence similarity is discussed and the validity of our algorithm is verified.更多还原