《DNA序列分类》PPT课件.ppt

DNA序列分类(2000年A题) 2000年6月，人类基因组计划中DNA全序列草 图完成，预计2001年可以完成精确的全序列图，此 后人类将拥有一本记录着自身生老病死及遗传进化 的全部信息的“ 天书”，这本大自然写成的“ 天书” 是由4个字符A,T,C,G按一定顺序排列成的长约30 亿的序列，其中没有“ 断句”，也没有标点符号， 除了这4种字符表示4种碱基因以外，人们对它包含 的“ 内容”知之甚少，难以读懂。破译这部世界上 最巨量信息的“ 天书”时21世纪最重要的任务之一 。在这个目标中，研究DNA序列具有什么结构， 由这4个排成的看似随机的序列中隐藏着什么规律 ，又是读懂这部天书的基础，是生物信息最重要的 课题之一。 虽然人类对这部“ 天书”知之甚少， 但也发现了 DNA序列中的一些规律和结构。例 如，在全序列中有一些是用于编码蛋白质的序列 片断，即由这4个字符组成64种不同的3字符串， 其中大多数用于编码构成蛋白质的24种氨基酸。 又例如，在不用于编码蛋白质的序列片断中A和 T的含量特别多些，于是以某些碱基特别丰富作 为特征去研究DNA系列的结构，也取得一些结 果。此外，利用统计的方法还发现序列的某些片 断之间具有相关性，等。这些发现让人们相信， DNA序列中存在着局部或全局的结构，充分发 掘序列的结构对理解DNA全序列是非常有意义 的。目前在这项研究中，最普遍的思想是省略 序列的某些细节，突出特征，然后将 其表示成适当的数学对象，这种被称为粗粒化 和模型化的方法往往有助于研究规律性和结构 。 作为研究DNA序列结构的尝试，提出下列 对序列集合进行分类的问题： 1)下面有20个已知类别人工制造的序列(略)，其 中110为A类，1120为B类，请从中提取特征 ，构造分类方法，并用这些已知类别的序列，衡 量你的方法是否足够好。然后用你认为满意的方 法，对另外20个未表明类别的人工序列(序号21 40)进行分类，把结果用序号(按从大到小顺序) 表明他们的类别(无法分类的不写入)； A类_;B_. 请详细描述你的方法，给出计算机程序， 如果你部分的使用现成的分类方法，也要将方 法名称准确注明。 这40个序列也放在如下地址的网页上，用 数据文件Art-model-data标识，供下载； 网易网址：www,163.com 教育频道 在线试题： 教育网： News mcm2000 教育网：/mcm 2)在同样网址的数据文件Nat-model-data中给 出182个自然DNA序列，它们都特长，用你的 方法将它们分类，象1)一样的给出分类结果 。 提示：衡量分类方法的优劣标准 是分类的准确率，构造分类方法有许多途径， 例如提取序列的某些特征，给出它们的数学表 示：几何空间或向量空间的元素等，然后再选 择或构造适合这种数学表示的分类方法；又例 如构造概率统计模型，然后用统计方法分类等 。 DNA 序 列 的 分 类 模 型 汤诗杰 周 亮 王晓玲 中国科技大学 1.问题的提出(略) 2.问题的分析 为表述严格方便，先用数学方法重述问题。 已知字母序列S1， S2， S40， Si x1 x2 xni，其中xja,t,c,g；A、B为两个 字符序列集合，满足AB，且当1i 10时 ， Si A，当11i 20时， Si B。现要求考虑 当21i 40 时， Si 属于A、B那个集合。 问题关键是从已知20个序列中提取分类特征。 3.分类标准及评价 所提取标准应满足以下两条： (1).必须可标志A组和B组。 (2).必须有一定的实际意义。 限制条件 目标函数 4.模型建立与分析 尝试综合使用3种设计思想不同方法处理。 第1种：从字母出现的频率出发。 第2种：从字母出现的周期性出发。 第3种：从序列所带的某些方面信息量出发。 最后从这3方面出发，得一综合分类方法。 方法1 基于字母出现频率 不同段DNA中，每个碱基因出现频率不同， 从生物理论知，编码蛋白质的DNA中G、C含 量偏高，非编码蛋白质的DNA中A、T含量偏 。故A、G、T、C出现频率有很多信息。 表1，表2(略)分别给出A、B组字母频率。 由统计数字知：A组C基因含量高， B组T基因含量高。 为定量化分析，引入四维向量(PA, PG, PT, PC ), 其中PA, PG, PT, PC,分别表示A，G，T，C 的频率。这样我们得到了两组向量Ai、Bi； i=1, 2, ，10；然后将未知序列2140作为一 组新向量，要将它归入A组或B组。 将向量单位化，分别记为Ai、Bi、C ；再计 计算内积： 即：内积 (PA, PG, PT, PC )A(PA, PG, PT, PC )未知 |A|未知| 认为内积小的两个序列相关性小，内积大的 认为相关性大。故当： CAi CBi时： i=1 10 i=1 10 把C归入A类，否则归入B类。结论如表3(略) ： 由此方法归纳出目标函数：F1() CAi i=1 10 CBi i=1 10 方法1讨论：只考虑频率忽略了字母所在 位置及各字母间的相互关系，使各边频率特 性不明显的序列不太容易分类。 方法2 基于字母出现周期性 除频率外，序列所含信息还有字母出现的规律。 设某单个字母a在序列中第t1, t2, tk+1个位置 出现，我们来找这些位置的关系。 序列是大段DNA中的一个片断，片断起始 点不同，会导致ti不同，考虑ti的分布及绝对 值意义不大。为抵消的线性位移，考虑： si ti+1 ti； i=1,2,k s1， s2 ， sn 的大小的信息是a的“ 稠密 度”，和频率有关，前面已经处理过。下面 考虑它的波动幅度，幅度越小说明si的值越 稳定，即A出现的周期性越大。表征波动幅 度的两是中心矩。现求二阶中心矩： 同理可求Varg、 Vart、 Varc. 由计算知Varg、 Vart 对A、B组的区分 率很高。为强调这种特性的显著性，用 F2Varg/ Vart作这种方法的目标函数。 图1分别以Varg、 Vart为横坐标、纵坐标划 点，可看出点与原点的连线的斜率在A组 和B组中有显著的差别。从而很好地区别了 A、B组。较好地弥补了方法1之缺点。 2 4 6 8 10 12 14 16 18 20 16 14 12 10 8 6 4 2 横轴：G间隔方差 纵轴：T间隔方差 A B 图1 方法2讨论 方法3 基于序列熵值 把DNA序列看成一个信息流，考虑其单位 序列所含信息量(即熵)来分类。通过观察A、B 组特点，认为重复越多信息量越少。 设序列L(a1, a2, a3, ，an )；前m个字符所 含信息量为 fm()，记： gm()= fm() fm-1()， 加上第m个 字符所增加 的信息量 fn() g i()， i=1 n 整个序列所含信息量 F3() fn()/|； 单位长度序列所含信息量 目标 函数 关键寻找合适的gm()。 gm()应满足以下条件： 1). gm()0 因任加一字符都增加一定信息量。 2).第m个字符与前面重复的越多，gm()= 越小。 3).第m个字符与靠得越近的重复的越多， gm()= 越小。 4). f0()=0 对此，可构造函数： gm()= b b+t11+ t22+ tpp. 其中b是为防止分母为零而设的一个小正数； i= at it； i=1 m it = 1 以第m-t个字符结尾的i字符串与第t 个字符串结尾的第 i字符串完全相同 0 否则 a1，使得 ti=ci-1， gm()定量给出了长度 与信息之间的关系。 字符串长度太大的重复很少见； 故可将重复字符串长度看成常数p. 上机反复搜索，取p6，即只检查长度 为 16的字符串则可。 取a=0.392; b=0.1; c=3则可将A、B组F3()值 分开，并可用来处理未知序列。 方法3讨论： 综合模型的建立 上面得到的三个目标函数： F1()、 F2()、 F3()都是定义在(由a, g, t, c四字母组成的序 列)序列空间L上的实函数。现在必须找一 个F，使F可以体现序列各个特征。 因F1()、 F2()、 F3()值域(含义)差别太大不 好比较，先将它们标准化。将它们看 成 是L空间上的随机变量，A、B为L的子集。 令：i Fi(); i E(i) Var(i) gi 根据现有样本点： Fi(1), Fi(2), ,Fi(20); 由 矩估计方法得： 代入(1)得gi 。 (1) 现寻求gi (A), gi (B)的分界点xi ，其中： gi (A)=gi(a)|aA； gi (B)=gi(b)|bB； 以g1为例，不能用一个分界点把A、B分开。根 据极大似然估计的思想，分界点应把尽可能多的 点分开，即x1(0.276758，0.482296)； 因为g1 分布未知，只能设其为均匀分布 ，则A、B最佳分界点x1为： 恰属于(0.276758，0.482296)； 类似可得： x2x30为g2 , g3 对应的最 佳分界点； Egi (A)+Egi (B) 2 0 矩估计 x1= 令：F a1 g1a2 g2a3 g3 ； 则其分界点： x= a1 0a2 0a3 0 = 0 选取适当的a1，a2，a3 使F作用在A样本上 大于零；作用在B样本小于零；则可以此作为A 、B的分类方法。 根据不同实际情况，调节a1、a2、a3 以体现 分类中的不同因素所在的比重。 表4，表5是取a11，a21，a30. 5所得 结果。 由表4 (略)知：A组目标函数值F0，B组F0 ；故用此方法区分A、B组样本准确率为100。 表5是用此法区分C的结果。 同样利用此法