1、 2000年年6月人类基因组计划中月人类基因组计划中DNA全全序列草图完成序列草图完成,2004年年10月绘制了精确的全月绘制了精确的全序列图序列图,标志着生命科学标志着生命科学“登月计划登月计划”又向又向前迈出一步前迈出一步,从此人类拥有了一部记录着自从此人类拥有了一部记录着自身生老病死及遗传进化全部信息的身生老病死及遗传进化全部信息的“天天书书”。DNA作为一种遗传物质作为一种遗传物质,早已在早已在50多年多年前就被发现。它是由前就被发现。它是由4种碱基种碱基:腺嘌呤腺嘌呤(A)、胞嘧呤胞嘧呤C)、鸟嘌呤、鸟嘌呤(G)及胸腺嘧呤及胸腺嘧呤(T)按一按一定顺序排成的长约定顺序排成的长约30亿
2、的序列。亿的序列。n虽然全序列图绘制成功，但这个几十亿的长序列中虽然全序列图绘制成功，但这个几十亿的长序列中既没有断句既没有断句,也没有标点符号，除了这也没有标点符号，除了这4个字符表示个字符表示4种碱基以外，人们对它包含的种碱基以外，人们对它包含的“内容内容”知之甚少，知之甚少，难以读懂。难以读懂。n 破译这部世界上最巨量信息的破译这部世界上最巨量信息的“天书天书”是二十一世是二十一世纪最重要的任务之一。在这个目标中，研究纪最重要的任务之一。在这个目标中，研究DNA全全序列具有什么结构，由这序列具有什么结构，由这4个字符排成的看似随机的个字符排成的看似随机的序列中隐藏着什么规律，又是解读这部
3、天书的基础，序列中隐藏着什么规律，又是解读这部天书的基础，是生物信息学（是生物信息学（Bioinformatics）最重要的课题之）最重要的课题之一。一。n但人们也发现了但人们也发现了DNA序列中的一些规律性和结构。例序列中的一些规律性和结构。例如，在全序列中有一些是用于编码蛋白质的序列片段，如，在全序列中有一些是用于编码蛋白质的序列片段，即由这即由这4个字符组成的个字符组成的64种不同的种不同的3字符串，其中大多字符串，其中大多数用于编码构成蛋白质的数用于编码构成蛋白质的20种氨基酸。又例如，在不用种氨基酸。又例如，在不用于编码蛋白质的序列片段中，于编码蛋白质的序列片段中，A和和T的含量特别
4、多些，的含量特别多些，于是以某些碱基特别丰富作为特征去研究于是以某些碱基特别丰富作为特征去研究DNA序列的序列的结构也取得了一些结果。此外，利用统计的方法还发现结构也取得了一些结果。此外，利用统计的方法还发现序列的某些片段之间具有相关性，等等。这些发现让人序列的某些片段之间具有相关性，等等。这些发现让人们相信，们相信，DNA序列中存在着局部的和全局性的结构，序列中存在着局部的和全局性的结构，充分发掘序列的结构对理解充分发掘序列的结构对理解DNA全序列是十分有意义全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某些的。目前在这项研究中最普通的思想是省略序列的某些细节，突出特征，然后
5、将其表示成适当的数学对象。这细节，突出特征，然后将其表示成适当的数学对象。这种被称为粗粒化和模型化的方法往往有助于研究规律性种被称为粗粒化和模型化的方法往往有助于研究规律性和结构。和结构。作为研究作为研究DNA序列结构的尝试序列结构的尝试,提出以下提出以下DNA序列的序列的分类问题分类问题:(1)现有现有20个已知类别的人造个已知类别的人造DNA序列序列,其中第其中第110序列为序列为A类类,第第1120序列为序列为B类类,现要求从中提现要求从中提取特征取特征,构造分类方法构造分类方法,并用构造的方法对另外第并用构造的方法对另外第2140个未标明类别的人工序列进行分类个未标明类别的人工序列进行
6、分类,并写出结果。并写出结果。(2)用构造的分类方法来给部分天然用构造的分类方法来给部分天然DNA序列进序列进行分类行分类,给出分类结果。给出分类结果。序列n1.aggcacggaaaaacgggaataacggaggaggacttggcacggcattacacggaggacgaggtaaaggaggcttgtctacggccggaagtgaagggggatatgaccgcttggn2.cggaggacaaacgggatggcggtattggaggtggcggactgttcggggaattattcggtttaaacgggacaaggaaggcggctggaacaaccggacggtggcagc
7、aaagga方法1 基于字母出现频率的分类不同段的不同段的DNA序列中，每个碱基出现的概率并不相同。序列中，每个碱基出现的概率并不相同。A组的组的G含量较高含量较高，B组的组的T含量较高含量较高，为做定量化的分析为做定量化的分析!引入引入数学中的内积概念数学中的内积概念，即将即将（A，T，G，C）的频率分别作为四的频率分别作为四维向量的四个分量维向量的四个分量（PA，PT，PG，PC），于是得到两组向量），于是得到两组向量Ai,Bi(i=1,10)然后将未知的然后将未知的某个某个序列作为一个新的向量序列作为一个新的向量C，将它归入将它归入A组或组或B组组。在。在Hilbert空间中将向量归一化
8、后计算内积空间中将向量归一化后计算内积内积小的两个序列内积小的两个序列!我们可以认为它们的相关性小我们可以认为它们的相关性小!而内积大的而内积大的序列序列!我们就认为其相关性大我们就认为其相关性大方法一 评价n方法一是从概率统计的角度分析问题方法一是从概率统计的角度分析问题n局限性：统计字母出现的频率时，忽略了局限性：统计字母出现的频率时，忽略了字母所在位置以及各个字母之间的相互关字母所在位置以及各个字母之间的相互关系，造成用这种方法对已知分类的序列进系，造成用这种方法对已知分类的序列进行检验时，个别频率特性不明显的序列不行检验时，个别频率特性不明显的序列不太容易分类，所以这种方法虽然有其科学
9、太容易分类，所以这种方法虽然有其科学性，但还不够完善，不能完全体现序列的性，但还不够完善，不能完全体现序列的所有特征。所有特征。方法二 基于字母出现周期性对于某单个字母，以对于某单个字母，以a为例为例,，设它在序列中第，设它在序列中第t1,t2,tk+1个个位置出现，我们试图找出这些数字之间的关联，首先，可以认位置出现，我们试图找出这些数字之间的关联，首先，可以认识到考查识到考查ti 的分布及绝对值是意义不大的的分布及绝对值是意义不大的,因为序列是一大段因为序列是一大段DNA中的一个片断，片断的起始段不同会导致中的一个片断，片断的起始段不同会导致ti的不同，于是的不同，于是为了抵消为了抵消ti
10、的线性位移，考虑下面一组值的线性位移，考虑下面一组值即字母即字母a出现的间距。出现的间距。由所得数据知由所得数据知，Varg 与与Vart上述方法对上述方法对A、B组的区分率组的区分率很高很高，于是可以用，于是可以用 可以考虑序列可以考虑序列si的波动幅度，而表征波动幅度的量在统的波动幅度，而表征波动幅度的量在统计中是中心矩。计中是中心矩。作为这种方法的目标函数作为这种方法的目标函数可以把一串可以把一串DNA序列看成一个信息流，关于序列看成一个信息流，关于A、B的分类，的分类，可以考虑其单位序列所含信息量（即熵）的多少。从直观上可以考虑其单位序列所含信息量（即熵）的多少。从直观上来看，我们可以
11、认为重复得越多，信息量越少。来看，我们可以认为重复得越多，信息量越少。设序列为设序列为L（a1,a2,an)，前，前m个字符所带的信息量为个字符所带的信息量为fm(L)记记即即gm(L)为加上第为加上第m个字母之后所增加的信息量个字母之后所增加的信息量现在的问题就归结为如何找出一个合适的现在的问题就归结为如何找出一个合适的gm(l)，不妨设，不妨设g具有以下性质：具有以下性质：性质性质1：gm(l)0，即任意加上一个字符，它或多或少带有一定，即任意加上一个字符，它或多或少带有一定信息量。信息量。性质性质2：第：第m个字符个字符(或者是以它结尾的较短序列或者是以它结尾的较短序列)与前面的序与前面
12、的序列列(信息流信息流)重复得越多，重复得越多，gm(l)的值必然越小。的值必然越小。性质性质3：第：第m个字符个字符(或者是以它结尾的较短序列或者是以它结尾的较短序列)如果和与它如果和与它靠得越近的重复，靠得越近的重复，gm(l)的值越小，和与它离得越远的重复的值越小，和与它离得越远的重复gm(l)的值越大。的值越大。性质性质4：f0(l)=0。以第以第m个字符结尾的个字符结尾的i字串且以第字串且以第t个字符结个字符结尾的尾的i字串完全相同字串完全相同否则否则定义为单位长度所带的信息量定义为单位长度所带的信息量不妨设不妨设ti=ci-1，c0，p=6另外当取另外当取a=0.392，b=0.1
13、，c=2可以将可以将A、B组的组的F值分得较值分得较开，并可以用来处理未知数据。开，并可以用来处理未知数据。方法三讨论n这种方法从序列的信息量（熵）入手，认为当序列这种方法从序列的信息量（熵）入手，认为当序列中有大量的重复元素时，信息量就会比重复少的序中有大量的重复元素时，信息量就会比重复少的序列所含有的信息少，所以，其侧重点是是序列前后列所含有的信息少，所以，其侧重点是是序列前后的重复性，也就是序列元素的相关性。的重复性，也就是序列元素的相关性。n从从A、B两类数据中可以很清楚地看到两类数据中可以很清楚地看到B组中序列重组中序列重复量大，所含的信息明显少于复量大，所含的信息明显少于A组。而这
14、个特征就被组。而这个特征就被我们定义的熵函数凸显出来。我们定义的熵函数凸显出来。n将将DNA序列看成一个信息流的方法由于其在实际问序列看成一个信息流的方法由于其在实际问题中的广泛背景，将会是一个很有价值的想法。统题中的广泛背景，将会是一个很有价值的想法。统计学和信息论的一套非常成熟的强大工具也会在计学和信息论的一套非常成熟的强大工具也会在DNA研究中发挥巨大的作用。研究中发挥巨大的作用。考虑采用序列中的考虑采用序列中的A、G、T、C的含量百分比作为的含量百分比作为该序列的特征百分比分别记为该序列的特征百分比分别记为na,ng,nt,nc则得到一组表征则得到一组表征该序列特征的四维向量（该序列特
15、征的四维向量（na,ng,nt,nc），由相关性取三维），由相关性取三维向量（向量（na,ng,nt）即可）即可一般的判别问题为：设有一般的判别问题为：设有k个类别个类别G1,G2,Gk，对任，对任意一个属于意一个属于Gi类样品类样品x，其特征向量，其特征向量X的值都可以获得，现的值都可以获得，现给定一个由已知类别的一些样品给定一个由已知类别的一些样品x1,x2,xn组成的学习样组成的学习样本，要求对一个来自这本，要求对一个来自这k个类别的某样品个类别的某样品x，根据其特征向，根据其特征向量量X的值作出其所属类别的判的值作出其所属类别的判断。断。方法四常规数学模型方法四常规数学模型A 欧氏距离
16、(Euclid)分类模型n把每个样本视为三维空间的一个点，以其到不同集合几何中心的欧氏距离作为判据，具体的算法如下：1、计算属于A类与属于B类的20个样本点集合各自的几何中心:2、对于给定的样本点、对于给定的样本点Xi，分别计算该点到，分别计算该点到CA,CB的的欧的的欧氏距离：氏距离：3、判别准则如下：、判别准则如下：a、若、若DADB，则判为，则判为A类类b、DBDA，则判为，则判为B类类c、若、若DADB，则列为不可判，则列为不可判用上述算法对已知学习样本用上述算法对已知学习样本A1A20进行分类，除了进行分类，除了A4分类错误外，其余都分类正确。分类错误外，其余都分类正确。模型评价n用
17、欧氏距离作为判据虽然简便直观，但存用欧氏距离作为判据虽然简便直观，但存在着明显的缺陷。从概率统计的角度来看，在着明显的缺陷。从概率统计的角度来看，用欧氏距离描述随机点之间的距离并不好。用欧氏距离描述随机点之间的距离并不好。因此当待分类样本是随机样本，具有一定因此当待分类样本是随机样本，具有一定的统计性质时，这个模型并不能很好的描的统计性质时，这个模型并不能很好的描述两个随机点之间的接近程度。述两个随机点之间的接近程度。B 氏距离（Mahalanobis)分类模型为了克服采用欧氏距离时的缺陷，我们采用马氏为了克服采用欧氏距离时的缺陷，我们采用马氏距离来代替欧氏距离。马氏距离定义为：距离来代替欧氏
18、距离。马氏距离定义为：判别准则如下：判别准则如下：a、若、若dm(X,A)dm(X,B)，则判为，则判为A类类b、若、若 dm(X,B)dm(X,A)，则判为，则判为B类类c、若、若dm(X,A)=dm(X,B)，则列为不可判，则列为不可判用上述算法对已知学习样本用上述算法对已知学习样本A1A20进行分类，除了进行分类，除了A4分类错误外，其余都分类正确。分类错误外，其余都分类正确。CFisher准则分类模型准则分类模型nFisher分类法是另一种基于几何特性的分分类法是另一种基于几何特性的分类法类法n分类法的思想也是把三维空间的样本映射分类法的思想也是把三维空间的样本映射为一维的特征值为一维
19、的特征值yn具体的作法是先引入一个与样本同维的待具体的作法是先引入一个与样本同维的待定向量定向量u，令，令y=uTxnu的选取的选取,要使同一类别产生的要使同一类别产生的y尽量聚拢尽量聚拢,不不同类别产生的同类别产生的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进行分类，
20、除了进行分类，除了A4分类错误外，其余都分类正确。分类错误外，其余都分类正确。方法四 三种分类模型的比较有的未知序列，三种方法给出了不同结果有的未知序列，三种方法给出了不同结果n对于任一个序列，当三种分类法结果完全一致时，对于任一个序列，当三种分类法结果完全一致时，认为它判别有效。认为它判别有效。n对于任一个序列，当三种分类法结果不完全一致对于任一个序列，当三种分类法结果不完全一致时，时，认为该序列为不可判类认为该序列为不可判类。考虑制定一个联合判定准则考虑制定一个联合判定准则方法五方法五 基于碱基相关性的分类模型基于碱基相关性的分类模型n通常任意两个数值序列的相关性都是通过通常任意两个数值序
21、列的相关性都是通过这两个序列的相关函数来刻画的，由于本这两个序列的相关函数来刻画的，由于本序列是非数值的序列，同时无法将碱基按序列是非数值的序列，同时无法将碱基按通常的方式进行数值化，因而刻画任意两通常的方式进行数值化，因而刻画任意两个序列的相关程度的变量需要重新定义个序列的相关程度的变量需要重新定义!定义一：相关运算定义一：相关运算对于任意碱基对于任意碱基m和和n，相关运算，相关运算的值由下表给定；的值由下表给定；定义二：哑元定义二：哑元除四个碱基外，另行定义一个哑元，除四个碱基外，另行定义一个哑元，规定任意碱基与哑元作相关运算的结果规定任意碱基与哑元作相关运算的结果都为都为0。定义三：序列
22、的延拓定义三：序列的延拓即在该序列的左右两端均用哑元填充即在该序列的左右两端均用哑元填充定义四：序列的相关度定义四：序列的相关度 对于任意的两个序列对于任意的两个序列AN、BM，定义序列，定义序列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属同一类的可能性。属同一类的可能性。基
23、于相关度的分类算法基于相关度的分类算法n1、对于任意一个未知序列、对于任意一个未知序列S将其与序列将其与序列A1A20中的每一个依次作求相关度的运算，结果记为中的每一个依次作求相关度的运算，结果记为SS1,SS2,SS20。n2、定义、定义S与与A、B类的平均相关度分别为类的平均相关度分别为n3、判别准则、判别准则若若SASB，则将，则将S判定给判定给A类类若若SBSA，则将，则将S判定给判定给B类类若若SASB，则将，则将S列为不可判类列为不可判类4、W可作为衡量该序列分类的可信性的一个标准，可作为衡量该序列分类的可信性的一个标准，显然当显然当W 越接近于越接近于1，该序列与，该序列与A类的
24、相关性和与类的相关性和与B类的相关性区别就越小，分类结果就越不可信。反类的相关性区别就越小，分类结果就越不可信。反之之W 与与1差的越远，该序列与差的越远，该序列与A类的相关性和与类的相关性和与B类类的相关性区别就越大，分类结果就越可信。的相关性区别就越大，分类结果就越可信。方法五的改进方法五的改进 带反馈的相关度分类算法带反馈的相关度分类算法 一般说来，带反馈的算法以神经网络算法最具一般说来，带反馈的算法以神经网络算法最具有代表性，但对于一般的分类算法而言，可以采有代表性，但对于一般的分类算法而言，可以采用多次反复分类的办法来实现反馈的目的用多次反复分类的办法来实现反馈的目的n1、对全部未知
25、样本进行相关度分类，计算出所有未、对全部未知样本进行相关度分类，计算出所有未知样本的知样本的W值值;n2、在所有被判为、在所有被判为A类的待分类序列中，取出类的待分类序列中，取出W值最值最大的一个作为标准学习样本加入到大的一个作为标准学习样本加入到A类的标准样本中；类的标准样本中；n3、在所有被判为、在所有被判为B类的待分类序列中，取出类的待分类序列中，取出W值最值最小的一个作为标准学习样本加入到小的一个作为标准学习样本加入到B类的标准样本中；类的标准样本中；n4、重复对剩余的待分类序列进行相关度分类，并按、重复对剩余的待分类序列进行相关度分类，并按上述步骤不断扩充标准学习样本，直至全部的待分
26、上述步骤不断扩充标准学习样本，直至全部的待分类序列都被加入到标准学习样本中。类序列都被加入到标准学习样本中。用新算法对未知序列进行了重新分类，得到了不同用新算法对未知序列进行了重新分类，得到了不同于原无反馈分类算法的结果，而且新的分类结果的于原无反馈分类算法的结果，而且新的分类结果的W 值明显与值明显与1离开的更大。可以看出反馈对算法的离开的更大。可以看出反馈对算法的性能有一定的改进性能有一定的改进!六 其它一些研究方法基于生物学的特征抽取基于生物学的特征抽取三联体，具有三联体形式的遗传密码子对蛋白三联体，具有三联体形式的遗传密码子对蛋白质的合成具有决定性作用。有理由认为它在序列中质的合成具有
27、决定性作用。有理由认为它在序列中的出现体现了该序列的本质特征的出现体现了该序列的本质特征基于人工神经网络的模型基于人工神经网络的模型 人工神经网络是一种带反馈的自适应算法，本人工神经网络是一种带反馈的自适应算法，本问题采用神经网络模型是合适的问题采用神经网络模型是合适的它可以在给定特征它可以在给定特征向量的情况下代替一般的距离分类模型向量的情况下代替一般的距离分类模型运用模糊聚类分析运用模糊聚类分析 可以从可以从DNA序列的全局角度出发序列的全局角度出发,来研究来研究DNA序序列的分类列的分类,忽略忽略DNA序列的局部结构的特征序列的局部结构的特征,从全局从全局的角度对的角度对DNA序列进行研
28、究。序列进行研究。生物信息学的发展趋势生物信息学的发展趋势n获取人和各种生物的完整基因组获取人和各种生物的完整基因组,建立相关数据库建立相关数据库,发展分子标发展分子标记辅助育种技术记辅助育种技术n发现新基因和新的单核苷酸多态性发现新基因和新的单核苷酸多态性n基因组中非编码蛋白质基因组中非编码蛋白质n完整基因组的比较研究完整基因组的比较研究n在基因组水平研究生物进化在基因组水平研究生物进化n从功能基因组到系统生物学从功能基因组到系统生物学n蛋白质结构模拟与药物设计蛋白质结构模拟与药物设计n新型高效算法在生物信息学中的应用新型高效算法在生物信息学中的应用n在生物信息学中在生物信息学中,许多研究就是对新算法的许多研究就是对新算法的需求需求,“算法是算法是core、算法是、算法是key、算法是、算法是soul”。n生物信息学对我们提出了很多富有魅力的生物信息学对我们提出了很多富有魅力的话题话题,比如比如DNA 序列拼接、比对序列拼接、比对,蛋白质折蛋白质折叠叠,疾病基因发现疾病基因发现,药物作用靶点预测等等。药物作用靶点预测等等。有些问题甚至是有些问题甚至是NP 性质的性质的,这些问题到现在这些问题到现在还是没有办法解决的还是没有办法解决的,必须等到新的算法出必须等到新的算法出现现,才能够得到解决。才能够得到解决。
