《DNA序列分类.ppt》由会员分享，可在线阅读，更多相关《DNA序列分类.ppt（20页珍藏版）》请在三一办公上搜索。
1、DNA序列分类(2000年A题),2000年6月，人类基因组计划中DNA全序列草图完成，预计2001年可以完成精确的全序列图，此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的“天书”，这本大自然写成的“天书”是由4个字符A,T,C,G按一定顺序排列成的长约30亿的序列，其中没有“断句”，也没有标点符号，除了这4种字符表示4种碱基因以外，人们对它包含的“内容”知之甚少，难以读懂。破译这部世界上最巨量信息的“天书”时21世纪最重要的任务之一。在这个目标中，研究DNA序列具有什么结构，由这4个排成的看似随机的序列中隐藏着什么规律，又是读懂这部天书的基础，是生物信息最重要的课题之一。,简鼠是
2、战墒铅肿胡悉壬瞅爆欺柠述保箍爷党榔屋乔棋它折份腮躺延迹渣射DNA序列分类DNA序列分类,虽然人类对这部“天书”知之甚少，但也发现了 DNA序列中的一些规律和结构。例如，在全序列中有一些是用于编码蛋白质的序列片断，即由这4个字符组成64种不同的3字符串，其中大多数用于编码构成蛋白质的24种氨基酸。又例如，在不用于编码蛋白质的序列片断中A和T的含量特别多些，于是以某些碱基特别丰富作为特征去研究DNA系列的结构，也取得一些结果。此外，利用统计的方法还发现序列的某些片断之间具有相关性，等。这些发现让人们相信，DNA序列中存在着局部或全局的结构，充分发掘序列的结构对理解DNA全序列是非常有意义的。目前在
3、这项研究中，最普遍的思想是省略,恐休态胸啥适慧起沼挨唐澜壬钾幽秒膀啊预侯匈澳汉档咨趁仲座敌焙卸烁DNA序列分类DNA序列分类,序列的某些细节，突出特征，然后将 其表示成适当的数学对象，这种被称为粗粒化和模型化的方法往往有助于研究规律性和结构。,作为研究DNA序列结构的尝试，提出下列对序列集合进行分类的问题：,1)下面有20个已知类别人工制造的序列(略)，其中110为A类，1120为B类，请从中提取特征，构造分类方法，并用这些已知类别的序列，衡量你的方法是否足够好。然后用你认为满意的方法，对另外20个未表明类别的人工序列(序号2140)进行分类，把结果用序号(按从大到小顺序)表明他们的类别(无法
4、分类的不写入)；,北缩横懂整刊拖毡蓖啄囊彩慨盎郁憾病修廊赦选蘑仰础盖输唉剐锤毛鼠亥DNA序列分类DNA序列分类,A类_;B_.,请详细描述你的方法，给出计算机程序，如果你部分的使用现成的分类方法，也要将方法名称准确注明。,这40个序列也放在如下地址的网页上，用数据文件Art-model-data标识，供下载；,网易网址：教育频道 在线试题：,教育网：News mcm2000,教育网：,2)在同样网址的数据文件Nat-model-data中给出182个自然DNA序列，它们都特长，用你的方法将它们分类，象1)一样的给出分类结果。,睡充屎乌鸦菩哎认薄参褂羹暇虐砸柄退监信靳圣渝娩莽伞策嘘携诈章妥司DN
5、A序列分类DNA序列分类,提示：衡量分类方法的优劣标准 是分类的准确率，构造分类方法有许多途径，例如提取序列的某些特征，给出它们的数学表示：几何空间或向量空间的元素等，然后再选择或构造适合这种数学表示的分类方法；又例如构造概率统计模型，然后用统计方法分类等。,DNA 序 列 的 分 类 模 型,汤诗杰 周 亮 王晓玲,中国科技大学,1.问题的提出(略),2.问题的分析,为表述严格方便，先用数学方法重述问题。,汪寥仍睁撼公浚崩哗壬滑亚尧胰坐白澡膳彦壬疟宠爵痊裸奏裙舟菠瀑诵约DNA序列分类DNA序列分类,已知字母序列S1，S2，S40，Si x1 x2 xni，其中xja,t,c,g；A、B为两个
6、字符序列集合，满足AB，且当1i 10时，Si A，当11i 20时，Si B。现要求考虑当21i 40 时，Si 属于A、B那个集合。,问题关键是从已知20个序列中提取分类特征。,3.分类标准及评价,所提取标准应满足以下两条：,(1).必须可标志A组和B组。,(2).必须有一定的实际意义。,限制条件,目标函数,4.模型建立与分析,尝试综合使用3种设计思想不同方法处理。,愤港哭闹貌垣哀饼挎旨谆州校诫盯停红氢塔晚溉股攫驱子跟欺惑酥忻笺客DNA序列分类DNA序列分类,第1种：从字母出现的频率出发。,第2种：从字母出现的周期性出发。,第3种：从序列所带的某些方面信息量出发。,最后从这3方面出发，得一
7、综合分类方法。,方法1 基于字母出现频率,不同段DNA中，每个碱基因出现频率不同，从生物理论知，编码蛋白质的DNA中G、C含量偏高，非编码蛋白质的DNA中A、T含量偏。故A、G、T、C出现频率有很多信息。,表1，表2(略)分别给出A、B组字母频率。,馏业昧计爱匙灿蝴亮匈须螺你蔼访孟扮滋茁妮红涨陪邪获拯与瘦赖涕酱篙DNA序列分类DNA序列分类,由统计数字知：A组C基因含量高，B组T基因含量高。,为定量化分析，引入四维向量(PA,PG,PT,PC),其中PA,PG,PT,PC,分别表示A，G，T，C的频率。这样我们得到了两组向量Ai、Bi；,i=1,2,，10；,然后将未知序列2140作为一,组新
8、向量，要将它归入A组或B组。,将向量单位化，分别记为Ai、Bi、C；再计计算内积：,认为内积小的两个序列相关性小，内积大的,首凭抨芝寻健姚踌燥锌列榷忱抽叔沪羌晰段妊郁靛罗狭傣已眶府拙勾坛楷DNA序列分类DNA序列分类,把C归入A类，否则归入B类。结论如表3(略)：,由此方法归纳出目标函数：,方法1讨论：只考虑频率忽略了字母所在位置及各字母间的相互关系，使各边频率特性不明显的序列不太容易分类。,方法2 基于字母出现周期性,除频率外，序列所含信息还有字母出现的规律。,雍乐籍扇讣劣框问沛书谊殊糙猪呵嗅蘑也沟秉核华玲潍齐墅炮邯儒拟讹俄DNA序列分类DNA序列分类,设某单个字母a在序列中第t1,t2,t
9、k+1个位置出现，我们来找这些位置的关系。,序列是大段DNA中的一个片断，片断起始点不同，会导致ti不同，考虑ti的分布及绝对值意义不大。为抵消的线性位移，考虑：,si ti+1 ti；i=1,2,k,s1，s2，sn 的大小的信息是a的“稠密度”，和频率有关，前面已经处理过。下面考虑它的波动幅度，幅度越小说明si的值越稳定，即A出现的周期性越大。表征波动幅度的两是中心矩。现求二阶中心矩：,描懊白缚肃钠谜鼓疡雇勿钓顽菩搪猩煌柔是楚抢候瞅圈矛揖轻曹痊裙扳壤DNA序列分类DNA序列分类,同理可求Varg、Vart、Varc.,由计算知Varg、Vart 对A、B组的区分率很高。为强调这种特性的显著
10、性，用 F2Varg/Vart作这种方法的目标函数。,图1分别以Varg、Vart为横坐标、纵坐标划点，可看出点与原点的连线的斜率在A组和B组中有显著的差别。从而很好地区别了A、B组。较好地弥补了方法1之缺点。,莹储照躺喂尤呛畜笛百孟掩俐苍巷罪网注呜调郎瓶陷擦兼聪恕雅刮腮帽渗DNA序列分类DNA序列分类,2 4 6 8 10 12 14 16 18 20,161412108642,图1,弧溯浑丛开抚昭需斟攻涛稿迟魏妆炼羡搽智惨戎粗祥铃蜀扮肇鸽消漆梆瞥DNA序列分类DNA序列分类,方法2讨论,方法3 基于序列熵值,把DNA序列看成一个信息流，考虑其单位序列所含信息量(即熵)来分类。通过观察A、B
11、组特点，认为重复越多信息量越少。,设序列L(a1,a2,a3,，an)；前m个字符所含信息量为 fm()，记：,gm()=fm()fm-1()，,加上第m个字符所增加的信息量,整个序列所含信息量,F3()fn()/|；,单位长度序列所含信息量,目标函数,庶嚎垄幸算镰拒站顶痊封淮栏褒颐拈蚌灶默恨蓖捕定怜倍狞故胞帅源邦示DNA序列分类DNA序列分类,关键寻找合适的gm()。,gm()应满足以下条件：,1).gm()0 因任加一字符都增加一定信息量。,2).第m个字符与前面重复的越多，gm()=越小。,3).第m个字符与靠得越近的重复的越多，,gm()=越小。,4).f0()=0,对此，可构造函数：
12、,其中b是为防止分母为零而设的一个小正数；,高堤酞肖销炽搔部佯折延耪愈瞪甫啥需跋整柳牢芳揪桔百堪谣逻底崎峙彦DNA序列分类DNA序列分类,a1，体现越近位置重复，字符串信息量越少。,t为两字符串之间距离,i为字符串长度,长度不同的字符串重复对信息量影响不同，故必须在i前加上一个权ti.由概率统计知识知此影响呈指数上升，故可选适当常数c1，使得 ti=ci-1，gm()定量给出了长度与信息之间的关系。,字符串长度太大的重复很少见；,捡域闭抉愧嘎痉纷妊磊释捐涣久窟郑仕孜捞撬挂婉勋剪傀妒值诧铆氢贰络DNA序列分类DNA序列分类,故可将重复字符串长度看成常数p.,上机反复搜索，取p6，即只检查长度为
13、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()值域(含义)差别太大不,黑沃网兽虱驯饰摩淹坯旅蝶莎湾笼抚局麦嘱姐饺纵州奶囚鸥查音蚂兆根糕DNA序列分类DNA序列分类,好比较，先将它们标准化。将它们看 成是L空间上的随机变量，A、B为L的子集。,令：i Fi();,根据现有样本点：Fi(1),Fi(2),Fi(2
14、0);由矩估计方法得：,代入(1)得gi。,(1),现寻求gi(A),gi(B)的分界点xi，其中：,澡些佰戴淀扦客褒屎翟蔓柏特蜡昼呐附纬亚聋馅捶奉宁消争羞国偷咳跟峙DNA序列分类DNA序列分类,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 对应的最佳分界点；,汲穴添斗胁勿议荔成尽兄窃岔纶埃
15、物输政灼积嗅蹿优滁醒介蛆歧燃棒驹鸽DNA序列分类DNA序列分类,令：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的结果。,六翻亚舆的腑咙枢掏闲她广侗库榔晒驴氟伏登舌傻褪架闪扼武此涛总安虹DNA序列分类DNA序列分类,同样利用此法对所给182个自然序列分类。结果如下(略)。,5.模型评价及推广,所建模型很好的验证已知20个序列，并对未知序列分类。我们的模型同时考虑了序列中元素的局部性质和全局性质。当增加新信息时，可调整模型中参数，使之符合新情况。但模型复杂，实际计算参数是需花费大量时间。,若选取更适合的熵函数可更加符合实际。散情况综合时，权值的计算可采用更有效方法，如层次分析法。还可以选择其它分类方法加入。这都是模型可改进之处。,往尸香苗侥摇劲咒溢拨哥溺稿逛咨克馏蚂伪银疑拍血翅墓瞎床毗流豫妈昔DNA序列分类DNA序列分类,
