基于结构信息的rna多序列比对

《基于结构信息的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］就是采用的这种算法。因为对能量规则进行了简化，对多分支环的处理是用单链碱基的自由能来模拟碱基堆积间的