dna序列分类模型研究(new)

1、DNA序列分类模型研究 2000年年6月人类基因组计划中月人类基因组计划中DNA全全序列草图完成序列草图完成, 2004年年10月绘制了精确的全月绘制了精确的全序列图序列图,标志着生命科学标志着生命科学“登月计划登月计划”又向又向前迈出一步前迈出一步,从此人类拥有了一部记录着自从此人类拥有了一部记录着自身生老病死及遗传进化全部信息的身生老病死及遗传进化全部信息的“天天书书” 。 DNA作为一种遗传物质作为一种遗传物质,早已在早已在50多年多年前就被发现。它是由前就被发现。它是由4种碱基种碱基:腺嘌呤腺嘌呤(A) 、胞嘧呤胞嘧呤C) 、鸟嘌呤、鸟嘌呤(G)及胸腺嘧呤及胸腺嘧呤(T)按一按一定顺序

2、排成的长约定顺序排成的长约30亿的序列。亿的序列。虽然全序列图绘制成功，但这个几十亿的长序列虽然全序列图绘制成功，但这个几十亿的长序列中既没有断句中既没有断句,也没有标点符号，除了这也没有标点符号，除了这4个字符个字符表示表示4种碱基以外，人们对它包含的种碱基以外，人们对它包含的“内容内容”知知之甚少，难以读懂。之甚少，难以读懂。 破译这部世界上最巨量信息的破译这部世界上最巨量信息的“天书天书”是二十是二十一世纪最重要的任务之一。在这个目标中，研究一世纪最重要的任务之一。在这个目标中，研究DNA全序列具有什么结构，由这全序列具有什么结构，由这4个字符排成的个字符排成的看似随机的序列中隐藏着什么

3、规律，又是解读这看似随机的序列中隐藏着什么规律，又是解读这部天书的基础，是生物信息学部天书的基础，是生物信息学（Bioinformatics）最重要的课题之一。）最重要的课题之一。但人们也发现了但人们也发现了DNA序列中的一些规律性和结构。序列中的一些规律性和结构。例如，在全序列中有一些是用于编码蛋白质的序列例如，在全序列中有一些是用于编码蛋白质的序列片段，即由这片段，即由这4个字符组成的个字符组成的64种不同的种不同的3字符串，字符串，其中大多数用于编码构成蛋白质的其中大多数用于编码构成蛋白质的20种氨基酸。又种氨基酸。又例如，在不用于编码蛋白质的序列片段中，例如，在不用于编码蛋白质的序列片

4、段中，A和和T的的含量特别多些，于是以某些碱基特别丰富作为特征含量特别多些，于是以某些碱基特别丰富作为特征去研究去研究DNA序列的结构也取得了一些结果。此外，序列的结构也取得了一些结果。此外，利用统计的方法还发现序列的某些片段之间具有相利用统计的方法还发现序列的某些片段之间具有相关性，等等。这些发现让人们相信，关性，等等。这些发现让人们相信，DNA序列中存序列中存在着局部的和全局性的结构，充分发掘序列的结构在着局部的和全局性的结构，充分发掘序列的结构对理解对理解DNA全序列是十分有意义的。目前在这项研全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某些细节，突出特究中最普通的思想

5、是省略序列的某些细节，突出特征，然后将其表示成适当的数学对象。这种被称为征，然后将其表示成适当的数学对象。这种被称为粗粒化和模型化的方法往往有助于研究规律性和结粗粒化和模型化的方法往往有助于研究规律性和结构。构。作为研究DNA序列结构的尝试,提出以下DNA序列的分类问题: (1)现有20个已知类别的人造DNA序列,其中第110序列为A类,第1120序列为B类,现要求从中提取特征,构造分类方法,并用构造的方法对另外第2140个未标明类别的人工序列进行分类,并写出结果。 (2)用构造的分类方法来给部分天然DNA序列进行分类,给出分类结果。序列1.aggcacggaaaaacgggaataacgga

6、ggaggacttggcacggcattacacggaggacgaggtaaaggaggcttgtctacggccggaagtgaagggggatatgaccgcttgg2.cggaggacaaacgggatggcggtattggaggtggcggactgttcggggaattattcggtttaaacgggacaaggaaggcggctggaacaaccggacggtggcagcaaagga方法1 基于字母出现频率的分类不同段的不同段的DNA序列中，每个碱基出现的概率并不相同。序列中，每个碱基出现的概率并不相同。A组的组的G含量较高含量较高，B组的组的T含量较高含量较高，为做定量化的分析为做

7、定量化的分析!引入引入数学中的内积概念数学中的内积概念，即将即将（A，T，G，C）的频率分别作为四的频率分别作为四维向量的四个分量维向量的四个分量（PA，PT，PG，PC），于是得到两组向量），于是得到两组向量Ai,Bi (i=1,10)然后将未知的然后将未知的某个某个序列作为一个新的向量序列作为一个新的向量C，将它归入将它归入A组或组或B组组。在。在Hilbert空间中将向量归一化后计算内积空间中将向量归一化后计算内积内积小的两个序列内积小的两个序列!我们可以认为它们的相关性小我们可以认为它们的相关性小!而内积大的而内积大的序列序列!我们就认为其相关性大我们就认为其相关性大方法一 评价方法一

8、是从概率统计的角度分析问题方法一是从概率统计的角度分析问题局限性：统计字母出现的频率时，忽略了字母局限性：统计字母出现的频率时，忽略了字母所在位置以及各个字母之间的相互关系，造成所在位置以及各个字母之间的相互关系，造成用这种方法对已知分类的序列进行检验时，个用这种方法对已知分类的序列进行检验时，个别频率特性不明显的序列不太容易分类，所以别频率特性不明显的序列不太容易分类，所以这种方法虽然有其科学性，但还不够完善，不这种方法虽然有其科学性，但还不够完善，不能完全体现序列的所有特征。能完全体现序列的所有特征。方法二 基于字母出现周期性对于某单个字母，以对于某单个字母，以a为例为例,，设它在序列中第

9、，设它在序列中第t1,t2,tk+1个个位置出现，我们试图找出这些数字之间的关联，首先，可以认位置出现，我们试图找出这些数字之间的关联，首先，可以认识到考查识到考查ti 的分布及绝对值是意义不大的的分布及绝对值是意义不大的,因为序列是一大段因为序列是一大段DNA中的一个片断，片断的起始段不同会导致中的一个片断，片断的起始段不同会导致ti的不同，于是的不同，于是为了抵消为了抵消ti的线性位移，考虑下面一组值的线性位移，考虑下面一组值即字母即字母a出现的间距。出现的间距。方法二 基于字母出现周期性由所得数据知由所得数据知，Varg 与与Vart上述方法对上述方法对A、B组的区分率组的区分率很高很高

10、，于是可以用，于是可以用 可以考虑序列可以考虑序列si的波动幅度，而表征波动幅度的量在统的波动幅度，而表征波动幅度的量在统计中是中心矩。计中是中心矩。作为这种方法的目标函数作为这种方法的目标函数可以把一串可以把一串DNA序列看成一个信息流，关于序列看成一个信息流，关于A、B的分类，的分类，可以考虑其单位序列所含信息量（即熵）的多少。从直观上可以考虑其单位序列所含信息量（即熵）的多少。从直观上来看，我们可以认为重复得越多，信息量越少。来看，我们可以认为重复得越多，信息量越少。设序列为设序列为L（a1,a2,an)，前，前m个字符所带的信息量为个字符所带的信息量为fm(L)记记即即gm(L)为加上

11、第为加上第m个字母之后所增加的信息量个字母之后所增加的信息量现在的问题就归结为如何找出一个合适的现在的问题就归结为如何找出一个合适的gm(l)，不妨设，不妨设g具有以下性质：具有以下性质：性质性质1：gm(l)0，即任意加上一个字符，它或多或少带有一定，即任意加上一个字符，它或多或少带有一定信息量。信息量。性质性质2：第：第m个字符个字符(或者是以它结尾的较短序列或者是以它结尾的较短序列)与前面的序与前面的序列列(信息流信息流)重复得越多，重复得越多，gm(l)的值必然越小。的值必然越小。性质性质3：第：第m个字符个字符(或者是以它结尾的较短序列或者是以它结尾的较短序列)如果和与它如果和与它靠

12、得越近的重复，靠得越近的重复，gm(l)的值越小，和与它离得越远的重复的值越小，和与它离得越远的重复gm(l)的值越大。的值越大。性质性质4：f0(l)=0。以第以第m个字符结尾的个字符结尾的i字串且以第字串且以第t个字符结个字符结尾的尾的i字串完全相同字串完全相同否则否则t定义为单位长度所带的信息量定义为单位长度所带的信息量不妨设不妨设ti=ci-1，c0，p=6另外当取另外当取a=0.392，b=0.1，c=2可以将可以将A、B组的组的F值分得较值分得较开，并可以用来处理未知数据。开，并可以用来处理未知数据。方法三讨论这种方法从序列的信息量（熵）入手，认为当序列中这种方法从序列的信息量（熵

13、）入手，认为当序列中有大量的重复元素时，信息量就会比重复少的序列所有大量的重复元素时，信息量就会比重复少的序列所含有的信息少，所以，其侧重点是是序列前后的重复含有的信息少，所以，其侧重点是是序列前后的重复性，也就是序列元素的相关性。性，也就是序列元素的相关性。从从A、B两类数据中可以很清楚地看到两类数据中可以很清楚地看到B组中序列重复组中序列重复量大，所含的信息明显少于量大，所含的信息明显少于A组。而这个特征就被我组。而这个特征就被我们定义的熵函数凸显出来。们定义的熵函数凸显出来。将将DNA序列看成一个信息流的方法由于其在实际问题序列看成一个信息流的方法由于其在实际问题中的广泛背景，将会是一个

14、很有价值的想法。统计学中的广泛背景，将会是一个很有价值的想法。统计学和信息论的一套非常成熟的强大工具也会在和信息论的一套非常成熟的强大工具也会在DNA研究研究中发挥巨大的作用。中发挥巨大的作用。考虑采用序列中的考虑采用序列中的A、G、T、C的含量百分比作为的含量百分比作为该序列的特征百分比分别记为该序列的特征百分比分别记为na,ng,nt,nc则得到一组表征则得到一组表征该序列特征的四维向量（该序列特征的四维向量（na,ng,nt,nc），由相关性取三维），由相关性取三维向量（向量（na,ng,nt）即可）即可一般的判别问题为：设有一般的判别问题为：设有k个类别个类别G1,G2,Gk，对任，对

15、任意一个属于意一个属于Gi类样品类样品x，其特征向量，其特征向量X的值都可以获得，现的值都可以获得，现给定一个由已知类别的一些样品给定一个由已知类别的一些样品x1,x2,xn组成的学习样组成的学习样本，要求对一个来自这本，要求对一个来自这k个类别的某样品个类别的某样品x，根据其特征向，根据其特征向量量X的值作出其所属类别的判的值作出其所属类别的判断。断。方法四常规数学模型方法四常规数学模型A 欧氏距离(Euclid)分类模型把每个样本视为三维空间的一个点，以其到不同集合几何中心的欧氏距离作为判据，具体的算法如下：1、计算属于A类与属于B类的20个样本点集合各自的几何中心:2、对于给定的样本点、

16、对于给定的样本点Xi，分别计算该点到，分别计算该点到CA,CB的的欧氏距离：的的欧氏距离：3、判别准则如下：、判别准则如下：a、若、若DADB，则判为，则判为A类类b、DBDA，则判为，则判为B类类c、若、若DADB，则列为不可判，则列为不可判用上述算法对已知学习样本用上述算法对已知学习样本A1A20进行分类，除了进行分类，除了A4分类错误外，其余都分类正确。分类错误外，其余都分类正确。模型评价用欧氏距离作为判据虽然简便直观，但用欧氏距离作为判据虽然简便直观，但存在着明显的缺陷。从概率统计的角度存在着明显的缺陷。从概率统计的角度来看，用欧氏距离描述随机点之间的距来看，用欧氏距离描述随机点之间的

17、距离并不好。因此当待分类样本是随机样离并不好。因此当待分类样本是随机样本，具有一定的统计性质时，这个模型本，具有一定的统计性质时，这个模型并不能很好的描述两个随机点之间的接并不能很好的描述两个随机点之间的接近程度。近程度。B 氏距离（Mahalanobis)分类模型为了克服采用欧氏距离时的缺陷，我们采用马氏为了克服采用欧氏距离时的缺陷，我们采用马氏距离来代替欧氏距离。马氏距离定义为：距离来代替欧氏距离。马氏距离定义为：判别准则如下：判别准则如下：a、若、若dm(X,A)dm(X,B)，则判为，则判为A类类b、若、若 dm(X,B)dm(X,A)， ，则判为，则判为B类类c、若、若dm(X,A)

18、=dm(X,B)， ，则列为不可判，则列为不可判用上述算法对已知学习样本用上述算法对已知学习样本A1A20进行分类，除了进行分类，除了A4分类错误外，其余都分类正确。分类错误外，其余都分类正确。CFisher准则分类模型准则分类模型Fisher分类法是另一种基于几何特性的分类法是另一种基于几何特性的分类法分类法分类法的思想也是把三维空间的样本映分类法的思想也是把三维空间的样本映射为一维的特征值射为一维的特征值y具体的作法是先引入一个与样本同维的具体的作法是先引入一个与样本同维的待定向量待定向量u，令，令y=uTxu的选取的选取,要使同一类别产生的要使同一类别产生的y尽量聚拢尽量聚拢,不同类别产

19、生的不同类别产生的y尽量拉开尽量拉开样品样品X到某一类到某一类G的距离定义为：的距离定义为：其中其中c为为G的几何中心的几何中心判别准则如下：判别准则如下：a、若、若L(X,A)L(X,B)，则判为，则判为A类类b、若、若L(X,B)L(X,A)， ，则判为，则判为B类类c、若、若L(X,A)=L(X,B)， ，则列为不可判，则列为不可判用上述算法对已知学习样本用上述算法对已知学习样本A1A20进行分类，除了进行分类，除了A4分类错误外，其余都分类正确。分类错误外，其余都分类正确。方法四 三种分类模型的比较有的未知序列，三种方法给出了不同结果有的未知序列，三种方法给出了不同结果对于任一个序列，

20、当三种分类法结果完全一致对于任一个序列，当三种分类法结果完全一致时，认为它判别有效。时，认为它判别有效。对于任一个序列，当三种分类法结果不完全一对于任一个序列，当三种分类法结果不完全一致时，致时， 认为该序列为不可判类认为该序列为不可判类。考虑制定一个联合判定准则考虑制定一个联合判定准则方法五方法五 基于碱基相关性的分类模型基于碱基相关性的分类模型通常任意两个数值序列的相关性都是通通常任意两个数值序列的相关性都是通过这两个序列的相关函数来刻画的，由过这两个序列的相关函数来刻画的，由于本序列是非数值的序列，同时无法将于本序列是非数值的序列，同时无法将碱基按通常的方式进行数值化，因而刻碱基按通常的

21、方式进行数值化，因而刻画任意两个序列的相关程度的变量需要画任意两个序列的相关程度的变量需要重新定义重新定义!定义一：相关运算定义一：相关运算对于任意碱基对于任意碱基m和和n，相关运算，相关运算的值由下表给定；的值由下表给定；定义二：哑元定义二：哑元除四个碱基外，另行定义一个哑元，除四个碱基外，另行定义一个哑元，规定任意碱基与哑元作相关运算的结果规定任意碱基与哑元作相关运算的结果都为都为0。定义三：序列的延拓定义三：序列的延拓即在该序列的左右两端均用哑元填充即在该序列的左右两端均用哑元填充定义四：序列的相关度定义四：序列的相关度 对于任意的两个序列对于任意的两个序列AN、BM，定义序列，定义序列

22、A和序列和序列B的相关序列的相关序列Si定义序列定义序列B对序列对序列A的相关度为的相关度为例如序列例如序列AT,C,T与序列与序列BA,G,T,C,T,C的相关度为：的相关度为：公理一：任意给定三个序列公理一：任意给定三个序列S、A、B，若，若A与与S的相关度大于的相关度大于B与与S的相关度，则的相关度，则A与与S属属同一类的可能性大于同一类的可能性大于B与与S属同一类的可能性。属同一类的可能性。基于相关度的分类算法基于相关度的分类算法1、对于任意一个未知序列、对于任意一个未知序列S将其与序列将其与序列A1A20中的每一个依次作求相关度的运算，结果中的每一个依次作求相关度的运算，结果记为记为

23、SS1,SS2,SS20。2、定义、定义S与与A、B类的平均相关度分别为类的平均相关度分别为3、判别准则、判别准则若若SASB，则将，则将S判定给判定给A类类若若SBSA，则将，则将S判定给判定给B类类若若SASB，则将，则将S列为不可判类列为不可判类4、 W可作为衡量该序列分类的可信性的一个标准，可作为衡量该序列分类的可信性的一个标准，显然当显然当W 越接近于越接近于1，该序列与，该序列与A类的相关性和与类的相关性和与B类的相关性区别就越小，分类结果就越不可信。反类的相关性区别就越小，分类结果就越不可信。反之之W 与与1差的越远，该序列与差的越远，该序列与A类的相关性和与类的相关性和与B类类

24、的相关性区别就越大，分类结果就越可信。的相关性区别就越大，分类结果就越可信。方法五的改进方法五的改进 带反馈的相关度分类算法带反馈的相关度分类算法 一般说来，带反馈的算法以神经网络算法一般说来，带反馈的算法以神经网络算法最具有代表性，但对于一般的分类算法而言，最具有代表性，但对于一般的分类算法而言，可以采用多次反复分类的办法来实现反馈的目可以采用多次反复分类的办法来实现反馈的目的的1、对全部未知样本进行相关度分类，计算出所有未知、对全部未知样本进行相关度分类，计算出所有未知样本的样本的W值值;2、在所有被判为、在所有被判为A类的待分类序列中，取出类的待分类序列中，取出W值最大值最大的一个作为标

25、准学习样本加入到的一个作为标准学习样本加入到A类的标准样本中；类的标准样本中；3、在所有被判为、在所有被判为B类的待分类序列中，取出类的待分类序列中，取出W值最小值最小的一个作为标准学习样本加入到的一个作为标准学习样本加入到B类的标准样本中；类的标准样本中；4、重复对剩余的待分类序列进行相关度分类，并按上、重复对剩余的待分类序列进行相关度分类，并按上述步骤不断扩充标准学习样本，直至全部的待分类序述步骤不断扩充标准学习样本，直至全部的待分类序列都被加入到标准学习样本中。列都被加入到标准学习样本中。用新算法对未知序列进行了重新分类，得到了不同于用新算法对未知序列进行了重新分类，得到了不同于原无反馈分类算法的结果，而且新的分类结果的原无反馈分类算法的结果，而且新的分类结果的W 值值明显与明显与1离开的更大。可以看出反馈对算法的性能有一离开的更大。可以看出反馈对算法的性能有一定的改进定的改进!六 其它一些研究方法基于生物学的特征抽取基于生物学的特征抽取三联体，具有三联体形式的遗传密码子对蛋白质三联体，具有三联体形式的遗传密码子对蛋白质的合成具有决定性作用。有理由认为它在序列中的出的合成具有决定性作