欢迎来到天天文库
浏览记录
ID:15155530
大小:51.00 KB
页数:21页
时间:2018-08-01
《基于结构信息的rna多序列比对》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、基于结构信息的RNA多序列比对【摘要】本研究提出了一种考虑了结构信息的同源RNA多序列比对算法,它先利用热力学方法计算出每条序列的配对概率矩阵,得到结构信息,由此构造各条序列的结构信息矢量,结合传统序列比对方法,提出优化目标函数,采用动态规划算法和渐进比对得到最后的多序列比对。试验证实了该方法的有效性。【关键词】多序列比对;RNA二级结构;配对概率矩阵;结构信息矢量;动态规划Abstract:WepresentedaRNAsequencesmulti-alignmentmethodbasedonstructuralinformation.Firstly,wecomputedba
2、sepairingprobabilityofeverysequencebythermodynamicmethod.Secondly,thestructuralinformationvectorwasconstructedthroughgottenstructureinformationandbeenpairalignmenteachother,asresult,aguidetreewasconstructed.Finally,combinetraditionalsequencealignment,wepresentedtheobjectivefunctionandgotthefi
3、nalmulti-alignmentbydynamicprogrammingalgorithmandprogressivealignmentwithguidetree.Wetestvalidityofourmethodon7sequencesofIREthroughcomparingwithClutalWandT-Coffee.21Keywords:Multiplesequencesalignment;Secondarystructures;Basepairingprobability;Structuralinformationvector;Dynamicprogramminga
4、lgorithm1引言多序列比对是生物序列分析的基础,传统的多序列比对(如ClustralW[1]、T-Coffee[2])通常用于数据库搜索或是结构特点探测,但是对RNA分子,这些方法就不适用了,因为RNA分子的功能主要由其二级结构确定,在进化过程中RNA的结构比序列具有更强的保守性,许多RNA有关的分析研究也正是应用了这一特点,如RNA结构分析[3-5]、RNA同源搜索[6]、非编码RNA探测[7-8]和基于RNA的系统进化推断[9]。而这些RNA序列分析方法都是要求先进行准确的多序列比对,这里的准确,就是指序列比对不仅要考虑序列信息,而且要更多的考虑结构信息。21基于序列和
5、结构信息的RNA多序列比对一般可以分为两类[10]:概率方法和非概率方法。概率方法基于上下文无关语法(SCFG),要求一个初始比对作为输入,而输出的质量对初始比对的依靠性较强。该方法被用于对RNA家族进行建模或是通过比较分析来预测二级结构,比如Cove[11]、RNACAD[12]和Pfold[4]。非概率方法,像MARNA[10],RNAlign[13],PMmulti[14],这种方法先进行双序列比对,然后渐进的完成多序列比对。我们提出的方法属于后者。2算法Sankoff[15]首先提出同时进行序列比对和结构预测,但是该算法的时间复杂度为O(N6),空间复杂度为O(N4),其
6、中N为序列长度。已有的几个采用此方法的程序都使用了不同的限制,比如,Foldalign[16]利用了核心比对和贪婪算法,而Dynalign[17]则是通过限制两个序列间的最大距离来减少复杂度。我们采用类似Sankoff算法的思路,但不是为了同时进行序列比对和结构预测,只是为了得到考虑结构信息的多序列比对。基本步骤是:首先,对每条序列,分别计算出其碱基配对概率矩阵,然后将这些矩阵变换成易于比较的结构信息矢量,通过两两比对这些矢量,构造出一个比对指导树,最后根据比对指导树,渐进的得到多序列比对。2.1碱基对配对概率矩阵为了得到配对概率矩阵,首先要进行划分函数的计算,McCaskill
7、[18]给出了RNA二级结构的划分函数的概念。RNA二级结构的划分函数Q定义为:21Q=∑Se-△G(S)/RT(1)式中,ΔG是结构的Gibbs自由能变化量,R是气体常数,T是绝对温度,S是所有可能二级结构的集合。McCaskill提出了一种动态规划算法来确定二级结构形成中的划分函数,该算法给出了序列中每个可能碱基对的配对概率,用一个概率点图显示,程序RNAfold[20-21]就是采用的这种算法。因为对能量规则进行了简化,对多分支环的处理是用单链碱基的自由能来模拟碱基堆积间的
此文档下载收益归作者所有