DNA序列的分类.pdf

第31卷第1期2001年1月数学的实践与认识MA THEMA T ICS I N PRACT ICE AND THEORYVol131No11Jan.2001任意选出比较多的(为了保证较高的准确性),利用keyword作为分类标准,然后利用本文提供的加权系数的确定方法就可以定出一个具体的定量标准.具有一定实用价值.参考文献:1李涛,贺勇军等.MATLAB工具箱应用指南应用数学篇.电子工业出版社 12袁亚湘.最优化方法.科学出版社 13张乃孝,裘宗燕.数据结构c+与面向对象的途径.高教出版社 14汪仁官.概率论引论.北京大学出版社 15陈家鼎,孙山泽等.数理统计学讲义.高教出版社 1The Grouping of DNA SequencesM odelYAN G Jian,WAN G Chi,YAN G Yong(Peking U niversity,Beijing100871)Abstract:In this paper,a method to classify the DNA sequences is proposed.M athematicalmethods such as statistics and opti m ization are used to build the model.The data is analysedsufficiently and the“critical words”is got,which can represent the characteristics of eachgroup.A ccording to this,a quantitative standard for grouping is brought forward.Thismodelcan properly classify the given data through testing.First,the stringswhich appear repeatedly(called words)in the given data are scanned out.The standard frequency and dispersion foreach word are calculated.Second,using the L east Squares method,the priority function isfixed.Through stepw ise opti m ization,the coefficients are made stable.Third,the key wordsare selected out and calculate the weight according to the priority function.A t last,using the“analyse hierarchy process”,the undeterm ined data is classified.This method can classify theundeterm ined data(No.21No.40)fairly well,it can also give good result for the last 182sequences.DNA序 列 的 分 类韩轶平,余杭,刘威指导老师:杨启帆(浙江大学,杭州310027)编者按:本文借助于计算机符号处理的能力来把握序列中不同碱基的丰度特征,从而进行了利用数理统计方法的分类研究.而后引入相关度分类判别算法及反馈机制来比较碱基的相对位置,在既定方向上颇具新意地把工作推向深入.不足之处在于,未能使用相关度工具对各类样本分别进行分析;此外,“纯数学”必须与其他学科紧密结合才会有优秀的建模工作,本文虽然对编码氨基酸的三联体进行初步探讨,着墨处自是轻淡许多.1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/摘要:本文对A题中给出的DNA序列分类问题进行了讨论.从“不同序列中碱基含量不同”入手建立了欧氏距离判别模型,马氏距离判别模型以及Fisher准则判定模型;又从“不同序列中碱基位置不同”入手建立了利用序列相关知识的相关度分类判别算法,并进一步研究了带反馈的相关度分类判别算法.对于题中所给的待分类的人工序列和自然序列,本文都一一作了分类.接着,本文又对其它各种常见的分类算法进行了讨论,并着重从分类算法的稳定性上对几种方法作了比较.1问题的重述(略)2模型的条件和假设(略)3符号约定na:任一给定序列中碱基A的百分含量;ng:任一给定序列中碱基G的百分含量;nt:任一给定序列中碱基T的百分含量;nc:任一给定序列中碱基C的百分含量.Gi:由某些具有相同属性的个体组成的类4问题的分析和解答411概述根据题意,我们首先要提取出一个序列的特征,然后给出它的数学表示,最后选择并构造基于这种数学表示的分类方法.对于一个任意一个DNA序列,我们认为,反映该序列特征的方面有两个:11 碱基的含量,反映了该序列的内容;21 碱基的排列情况,反映了该序列的形式.412基于碱基含量特征分类的模型首先,我们考虑采用序列中的A,G,T,C的含量百分比作为该序列的特征.这样的抽取特征的方法具有其生物学的意义.前面提到过,在不用于编码蛋白质的序列片断中,A和T的含量特别多些,因此以某些碱基特别丰富作为特征去研究DN A序列的结构是具有可行性的.将序列中的A,G,T,C的含量百分比分别记为na,ng,nt,nc,则得到一组表征该序列特征的四维向量(na,ng,nt,nc).考虑到na,nt,ng,nc线性相关(na+ng+nt+nc=1),所以我们采用简化的三维向量(na,nt,ng)来进行计算.对于标号为i的序列,记它的特征向量为X i.显然,任意序列的特征向量与一个3维空间的点对映.一般的判别问题为:设有k个类别G1,G2,Gk,对任意一个属于Gi类样品x,其特征向量X的值都可以获得.现给定一个由已知类别的一些样品x1,x2,xn组成的学习样本,要求对一个来自这k个类别的某样品x,根据其特征向量X的值作出其所属类别的判断.在本题DNA序列分类中,k=2,G1=A,G2=B,特征向量X是三维的.学习样本共包含n=20个样本,其中10个属于A,10个属于B.我们分别采用了欧氏距离(Euclid)分类模型,马氏距离(M ahalanobis)分类模型和Fisher判别模型来对序列样本分类.931期韩轶平等:DNA序列的分类 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/41211欧氏距离(Euclid)分类模型在欧氏距离(Euclid)分类模型中,把每个样本视为三维空间的一个点,以其到不同集合几何中心的欧氏距离作为判据.具体的算法如下:11 计算属于A类与属于B类的10个样本点的集合各自的几何中心:CA=11010i=1XiCB=11020i=11Xi21 对于给定的样本点Xi,分别计算该点到CA的欧氏距离DA=Xi-CA,以及该点到CB的欧氏距离DB=Xi-CB;31 判别准则如下:(1)若DADB,则将Xi点判为B类;(3)若DA=DB,则将Xi点判为不可判类;用上述算法对已知样学习样本A 1A 20进行分类,结果是除了A 4被错误的分到了B类外,其余的19个样本全部正确,分类准确率达到95%.用上述算法对未知的人工序列A 21A 40进行分类,得到的结果是:A类:22,23,25,27,29,30,32,34,35,36,37,39;B类:21,24,26,28,31,33,38,40用上述算法对未知的自然序列N 1N 182进行分类,得到的结果见附录.(略)用欧氏距离作为判据虽然简便直观,但存在着明显的缺陷:从概率统计的角度来看,用欧氏距离描述随机点之间的距离并不好.因此当待分类样本是随机样本,具有一定的统计性质时,这个模型并不能很好的描述两个随机点之间的接近程度.41212马氏距离(Mahalanobis)分类模型为了克服采用欧氏距离时的缺陷,我们采用马氏距离来代替欧氏距离.改进后的算法如下:设:三维总体G的均值为=(1,2,3)T,协方差矩阵为非奇异阵V3x3,则三维样本X到总体G的马氏距离为:dm(X,G)=(X-)TV-1(X-)其中未知的 可用学习样本的均值来代替,协方差矩阵V可用学习样本的样本协方差矩阵来代替.将马氏距离用于判别模型,遵循判据如下:11 若dm(X,A)dm(X,B),则判定x为B类;31 若dm(X,A)=dm(X,B),则判定x为不可判类;用上述算法对已知样学习样本A 1A 20进行分类,结果是除了A 4被错误的分到了B类外,其余的19个样本全部正确,分类准确率达到95%.用上述算法对未知序列A 21A 40进行分类,得到的结果是:A类:22,23,25,27,29,30,32,33,34,35,36,37B类:21,24,26,28,31,38,39,40用上述算法对未知的自然序列N 1N 182进行分类,得到的结果见附录 1(略)04数学的实践与认识31卷 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/41213Fisher准则分类模型在多维空间里分类的方法不仅仅是距离分类法一种,常用的Fisher分类法就是另一种基于几何特性的分类法.在距离判别模型中,三维空间的样品X被映射为一维的距离d来作判断.Fisher分类法的思想也是把三维空间的样本映射为一维的特征值y,并依据y来进行判别.具体的作法是先引入一个与样本同维的待定向量u,再将y取为X坐标的线性组合y=uTx.而u的选取.要使同一类别产生的y尽量聚拢,不同类别产生的y尽量拉开.这样,我们便可将样品X到某一类G的距离定义为y=uTx与yc=uTc之间的欧氏距离:L(X,G)=y-yc=uT(x-c)其中c为G的几何中心.Fisher分类的判据为:1若L(X,A)L(X,B),则判定x为B类;3若L(X,A)=L(X,B),则判定x为不可判类.根据对u的要求,Fisher提出了比较有效的选择算法,利用该算法,从学习样本中获得:u=(0.3365,-0.087,0.9377)TL(X,A)=0133653(na-0.2860)-0.0873(nt-0.1550)+0.93773(ng-0.3830)L(X,B)=0133653(na-0.2940)-0.0873(nt-0.5010)+0.93773(ng-0.1010)用上述算法对已知样学习样本A 1A 20进行分类,结果仍然是除了A 4被错误的分到了B类外,其余的19个样本全部正确,分类准确率达到95%.对于未知序列A 21A 40进行分类,得到的结果是:A类:22,23,25,27,29,34,35,36,37;B类:21,24,26,28,30,31,32,33,38,39,40用上述算法对未知的自然序列N 1-N 182进行分类,得到的结果见附录 1(略)41214三种距离分类模型的比较表1欧氏距离法马氏距离法Fisher准则法30AAB32AAB33BAB39ABB这三种模型在分类结果上有一定的区别,对于序列A 30,A 32,A 33及A 39,三种方法给出了不同结果,见表1.对于这种情况,我们提出一个联合判定准则:对于任一个序列,当三种分类法结果完全一致时,认为它判别有效;若不然,当三种分类法结果不一致时,认为该序列为不可判类.对于三种方法都无法正确分类的A 4序列,可认为是异常情况,不影响算法的性能.413基于碱基位置特征分类的模型虽然上述采用碱基A,T,G,C在DNA序列里的含量作为该序列的特征的方法有一定的生物学意义并且在DNA序列的分类中获得了比较理想的结果.但是,用这种方法抽取特征,没有充分体现碱基排列的信息量,仅仅考虑碱基含量并没有体现碱基在序列中的排列情况.例如,序列(A TGC)与序列(CGTA)有着相同的碱基含量,他们的特征向量是完全一样的,并不能体现在排列结构上的不同.因此,直接从序列本身的碱基排列顺序来考察序列就成为一种更加合适的提取特征的方式.因此采纳数值序列中的相关性分析设计了算法.141期韩轶平等:DNA序列的分类 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/通常任意两个数值序列的相关性都是通过这两个序列的相关函数来刻画的.由于本题中的DNA序列是非数值的序列,同时无法将碱基按通常的方式进行数值化,因而刻画任意两个序列的相关程度的变量需要重新定义.表2“AGTCA1000G0100T0010C000141311定义一:相关运算“”对于任意碱基m和n,相关运算“mn”的值由表2定义:41312定义二:哑元O除四个碱基外,我们另行定义一个哑元O,规定任意碱基与哑元作相关运算的结果都为0.41313定义三:序列的延拓对于任意一个长度为N的序列A i(其中0iN),定义它的延拓为如下一个无限序列:A+j:当0jN时,A+j=Aj;当-j 0及Nj 1,则将X点判为A类;若W 1,则将X点判为B类;若W=1,则将X点判为不可判类;51W可作为衡量该序列分类的可信性的一个标准.显然当W越接近于1,该序列与A类的相关性和与B类的相关性区别就越小,分类结果就越不可信;反之,W与1差的越远,该序列与A类的相关性和与B类的相关性区别就越小,分类结果就越可信.这个变量对我们下面带有反馈的相关度分类算法具有重要的意义.用上述算法对已知样学习样本A 1-A 20进行分类,得到的结果是分类完全正确,A,B类可以完全分开,准确率达到100%.对于未知序列A 21A 40进行分类,得到的结果是:A类:22 23 25 27 29 34 35 36 37B类:21 24 26 28 30 31 32 33 38 39 40用上述算法对未知的自然序列N 1N 182进行分类,得到的结果见附录(略)141317相关度分类算法的改进带有反馈的分类算法上述的相关度分类算法是一次性学习过程,学习的过程只体现在学习样本的过程中,而在对未知样本分类的过程中没有对已分类情况作出修正,即是属于无反馈型的学习.然而,采用反馈型的学习过程会有更好的分类结果.一般说来,带反馈的算法以神经网络算法最具有代表性.但对于一般的分类算法而言,可以采用多次反复分类的办法来实现反馈的目341期韩轶平等:DNA序列的分类 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/的.针对上述的相关度分类算法,我们设计了如下带反馈的相关度分类算法:11 对全部182个样本进行相关度分类;21 计算全部182个W的值31 在所有被判为A类的待分类序列中,取出W值最大的一个,作为标准学习样本,加入到A类的标准样本中(若有多个,则全部加入到A类中,若无被判为A类的序列,则保持A类标准学习样本不变.)41 在所有被判为B类的待分类序列中,取出W值最小的一个,作为标准学习样本,加入到B类的标准样本中(若有多个,则全部加入到B类中,若无被判为B类的序列,则保持B类标准学习样本不变.)51 重复对剩余的待分类序列进行相关度分类,并按上述步骤不断扩充标准学习样本,直至全部的待分类序列都被加入到标准学习样本中.我们用新算法编程对182个序列进行了重新分类,得到了不同于原无反馈分类算法的结果,而且新的分类结果的W值明显与1离开的更大,这使我们有理由相信,反馈对算法的性能有一定的改进.5进一步研究的问题511基于生物学的特征抽取我们上述的两种特征抽取方法更多的是从纯数学眼光来研究序列的特征.除此之外,我们还可以考虑DNA序列在生物学意义下的数学特征.一个比较容易考虑到的方面便是三联体在DNA序列中的出现.由于具有三联体形式的遗传密码子对蛋白质的合成具有决定性作用,有理由认为它在序列中的出现体现了该序列的本质特征.题中没有明确的指明所给的序列是全序列还是序列片断,我们无法对三联体在序列中的出现位置进行定位,一种代替的方法是将序列假定为全序列,从第一个碱基开始三个三个一组的划分为密码子,然后统计64个密码子的出现概率,形成64维的向量.再使用距离分类等模型,或利用生物学的知识先将64维向量的某几维合并,降维后再分类.我们编程演算后,觉得该种分类方法比较依赖于密码子的划分,一位碱基的缺失或错位均会造成分类错误,所以必须加以修改,一条思路是尝试将序列移一位或二位再划分密码子,由于时间所限,没有进一步研究.512基于人工神经网络的模型人工神经网络是一种带反馈的自适应算法,随着计算机速度提高被广泛应用.对于本题的情况采用神经网络模型是合适的,它可以在给定特征向量的情况下代替一般的距离分类模型.对于基于碱基含量的特征向量(na,nt,ng),构造了如下的反向传播算法:11 网络简单的分为两层,一层为输入层,有3个单元,分别为权重a,b,c;一层为输出层,有1个单元,为判别结果;各单元均为Sigmoid型函数激励.21 设定(a,b,c)的初值为(0,0,0);A类学习样本的标准输出定为1;B类学习样本的标准输出定为031 对每一个学习样本,计算S=a3na+b3nt+c3ng作为输出;41 将学习样本的标准输出与S相减,所得的差用来指导权重的改变,权重的改变遵从W idrow2Hoff准则.44数学的实践与认识31卷 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/51 反复学习样本,到权重值稳定收敛.61 代入待分类样本,分类.用上述算法所得到的结果与普通的分类模型没有区别.事实上当权值稳定收敛后,S=a3na+b3nt+c3ng就是特征空间的一张(超)平面,从这一点来说,人工神经网络模型与一般的距离分类模型得到的结果没有两样.考虑到人工神经网络模型还存在结果对初值有较强敏感性,缺乏选择理想步长的准则和收敛性等问题,在一定的时间内,我们无法较好的解决这些问题,所以我们也没有作进一步讨论.6算法的稳定性前面比较算法的时候,曾多次提到分类算法的稳定性问题.分类算法的稳定性是除了算法的成功率之外的另一较重要的指标.所谓分类算法的稳定性,是指算法在样本发生了轻微变化时作出正确判别的能力.对于本题,是指算法在样本序列发生了轻微的碱基缺失,错位,错排情况时作出正确判别的能力.因为本题要求我们研究的是DNA序列粗粒化和模型化的问题,所以分类时是对序列的整体特征进行区分.局部碱基的组成变化应该对算法的分类结果没有影响.我们所提出的几个模型均较好的满足了这一点.参考文献:1孙乃恩,孙东旭,朱德煦.分子遗传学 1 南京大学出版社,199612白其峥 1 数学建模案例分析 1 海洋出版社,200013潘德惠 1 数学模型的统计方法 1 辽宁科学技术出版社,198614阎平凡,黄端旭 1 人工神经网络 1 安徽教育出版社,199115李振刚 1 分子遗传学概论 1 中国科学技术大学出版社,199016Duane Hanselman1BruceL ittlefieldM asteringMATLAB:a comprehensive tutorial and reference 1Prentice Hall,19961Classif ication of DNA SequencesHAN Yi2ping,YU Hang,L I U W ei(Zhejiang U niv.,Hangzhou310027)Abstract:This paper proposes several methods for the classification of DNA sequences.W enoticed that different sequences have different alkali radicals and therefore set up models usingEuclidean distance,M ahalanobis distance and Fisher principle.W e also noticed that differentsequences have different permutations of alkali radicals and an algorithm using relativityanalysis is proposed.Further we discussed a relativity analysis algorithm w ith feed2backmechanism.A s to the natural and artificial data given our algorithm swork well and fine resultsare given.A t last several other common algorithm s are compared,especially ontheirstabilities.541期韩轶平等:DNA序列的分类 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/