DNA序列的分类模型 503 而现有样本点f(11),f(12),…,f(120)利用距估计方法估计得 1∑f(4) ES,) 代入(1)即得g 现估计g投射L的点到实轴上后,k;(A)和g(B)的分界点x,其中 g(A)=|g(a)|a∈A g;(B)=g(b)|b∈B 以g1为例,A的10个样本点和B的10个样本点不能被一个分界点分开,由极大似然 估计的思想,分界点应该把尽可能多的点分开,即 x∈(-0.276758,0.482296) 由于g(1)的分布未知故只能假设其满足较均匀的分布,则A,B的分界点的最好估计 为28(A)+E(B) ,而E(4)+E(B)的矩估计为(4)=0(由g的定义),恰 好0∈(-0.276758,0.48296),则x1=0是分界点的最佳估计 同理,x2=0,x3=0分别是g2,g3对应分界点的最佳估计 令F=a1g1+a2g2+a33,则其分界点为x=a1×0+a2X0+a3×0=0 由F的构造方法知,F作用到A样本上大于零,作用到B样本上小于零我们确定适 当的权值,以此作为A,B的分类法即可,根据不同的实际情况,可以相应调节这三个权值, 以体现分类中的不同因素所在的比重.在下面的计算中,我们简单的取a1=1,a2=-1,a 0.5.得到的结果如表4,表5所示: 序号”目标函数值序号目标函数值序号目标函数值序号日目标函数值。 1.75355 111.38528 16-2.60295 A21.7589471.25115B12 1.22372B17-0.0165438 32.5887 1.41371 0.940004 18 组40.27582组91.9011组140.93612组192.6043 52.1781 01.97282 15-2.27465 3.603 表5 目标函数值 序号 目标函数值 21 1.9645 1.06638 B 0.873279 A 0.668504 B 2.32887 A 33 24 1.48005 2.60904 A I.184 B 36 1.22298 1.22569 1.83991 3.71616 3.01466 2.69272 0.499763 A
全国大学生数学建模竞赛优秀论文汇编 由以上数据可以看出,我们构造的目标函数具有较好的区分度.对于A组,目标函数值 都大于零;而对B组,目标函数值都小于零.也就是说,用这种方法,对A、B组样本的区分 率已达到了100%正如前面所说,这种方法综合了序列中的许多信息.因此,我们完全可 以采用这个标准来区分C组,表5是对C组区分的结果 对20个未标明分类的人工序列的分类结果为 A类:22,23,25,27,29,30,34,35,36,37,39B类:21,24,26,28,31,32,3,38,40 同样的,我们利用这种方法对所给的182个自然序列进行了分类,结果如下所示(略) 5模型的评价及推广 在我们的模型基础上提出的分类方法可以很好的验证已知的20个序列,并且很好的完 成了对未知类型序列的分类.我们认为这种模型,同时考虑了序列中元素的局部性质和序 列的全局性质,具有相当的实际背景当我们知道分类标准的更多信息时,我们可以很方便 的调整模型中的参数,使之符合新的情况,具有很好的自学习性,但这个模型比较复杂,在 实际计算中参数选择需要花费大量计算时间进行搜索 我们在模型中使用的基于信息流的方法中,如果选取更为合适的熵函数,一定可以使它 更加符合实际情况;在三种方法综合的时候,所取的权值也是可以采用更为有效的方法选 取,如应用层次分析法;还可以选取其他分类方法加入.这些都是本模型可以改进的地方 参考文献 [1]姜启源.数学模型(第二版)高等教育出版社,199. [2]刘郁强等.序列空间方法.广东科技出版社,1996. [3]刘祖洞.遗传学(第二版,高等教育出版社,199 4]姜丹,钱玉美,信息理论与编码,中国科学技术大学出版社,1992 5]王玲玲等.常用统计方法,华东师范大学出版社,1994 [6]陆璇.应用统计.清华大学出版社,199
关于DNA序列分类问题的模型 冯涛康喆雯韩小军 (大连理工大学,大连116024) 指导老师贺明峰 编者按本文以统计方法提取样本特征,以之作为BP神经网络的输入,用 MATLAB中 相应算法进行训练.然后用于解决本分类问题,得到了较准确的结果.本文提取特征时考虑 较为全面,在此基础上正确地运用了神经网络方法,发挥了神经网络适用于非线性问题、具有 自适应能力的优点,思路清楚,文字简练 摘要本文提出了一种将人工神经元网络用于DNA分类的方法,作者首先应用概率 统计的方法对20个已知类别的人工DNA序列进行特征提取,形成DNA序列的特征向量,并 将之作为样本输人BP神经网络进行学习.作者应用了 MATLAB软件包中的 Neural Network Toolbox(神经网络工具箱)中的反向传播( Back propagation BP)算法来训练神经网络、在本文 中,作者构造了两个三层BP神经网络,将提取的DNA特征向量集作为样本分别输入这两个 网络进行学习,通过训练后,将20个未分类的人工序列样本和182个自然序列样本提取特征 形成特征向量并输入两个网络进行分类.结果表明:本文中提出的分类方法能够以很高的正 确率和精度对DNA序列进行分类,将人工神经元网络用于DNA序列分类是完全可行的 1问题重述(略) DNA序列由四个碱基AT、C、G按一定规律排列而成,已知所给人工序列1-10属于 A类,11-20属于B类.本题中,我们的主要工作有两个: 1)提取A、B两类特征; 2)以所提取A、B两类特征为依据,把20个人工序列及182个自然序列分为A、B两类 (可能存在同时不具有AB两类特征,不能归为A、B中任一类的序列) 在本题中,先以序列1-20为依据,提取出A、B两类序列的统计特征,然后运用神经网 络中的BP网络对未知序列进行了分类识别 2模型建立的理论依据 神经网络是近年来发展的一种大规模并行分布处理的非线性系统),其主要特点有: 1)能以任意精度逼近任意给定连续的非线性函数; 2)对复杂不确定问题具有自适应和自学习能力 3)具有较强的容错能力和信息综合能力,能同时处理定量和定性的信息,能很好地协 调多种输入信息的关系 传统的分类识别方法,对于一般非线性系统的识别很困难,而神经网络却为此提供了 个强有力的工具.它实质上是选择了一个适当的神经网络模型来通近实际系统,目前,在 神经网络中应用最多的是BP网络 对于具有n个输入节点,m个输出节点的BP网络,输入到输出的关系可以看作是 个n维欧式空间到m维欧式空间的映射,F:R”→Rm,这一映射是高度非线性映射,KT
506 全国大学生数学建模竞赛优秀论文汇编 Funahashi于1989年证明了这样的一个定理2:如果BP网络隐层节点可以根据问题的不 同作相应的配置的话,那么用三层的激励函数为双曲线正切型的B网络,可以以任意精度 逼近任意连续函数.这一定理保证了BP网络在分类识别问题中的可用性 将复杂系统看作是一个黑箱,以实测输人,输出数据为学习样本,送入BP网络,网络通 过样本进行学习,在学习过程中,网络的权值不断地修改3,使输入到输出的映象逐渐与实 际对象的特性相通近,但网络输出的整体误差E小于给定的标准时,整个网络便模拟出实 际系统的外部特性 实际分类识别问题中,输入空间一般是多维欧式空间,我们可以计算空间中点与点的欧 式距离,并根据这些距离知道哪些样本互相靠得近,哪些样本相距甚远,也就是说在输入空 中存在着一个距离度量,只要输入模式接近于某个输出模式,由于BP网络所具有的联想 记忆能力,则网络的输出亦会接近学习样本的输出 3模型的基本假设 1)假设碱基序列的特征值包括以下两个内容:(1)单个碱基在序列中的数量特征,即 A,T,C,G四种碱基在序列中的含量;(2)特征碱基串在序列中的数量特征(包括双字符碱基 串和三字符碱基串) 2)由于给定的已知碱基序列是从DNA全序列中随机截取出来的,因此无法确定序列 的起始位,无法从序列中辨认出氨基酸.假设在对DNA序列分类时,是从碱基层次上进行 分类,而不是从氨基酸层次上分类 4)模型的建立与求解 4.1提取A、B两类的特征 经过计算我们提取出A、B两类的统计特征(a)和(b),具体方法如下: 特征(a):单个字符出现的频率.特征(a)对应基本假设1中的第1条 对1-20每个人工序列,我们统计出单个字符A、T、C、G出现的频率P,Pi=Ti/(S M+1),=A,T,C,G S为序列长度,M为字符长度(这里,M=1),Ti为每个序列中i出现的次数 序列1-20特征(a)的数值如下:(略 特征(b):特征字符串出现的频率.特征(b)对应基本假设1中的第2条 通过对序列1-20种A、T、CG四字母的不同组合(如两两组合,三三组合,四四组合) 出现频率的分析,可以知道:对于双字符串和三字符串,均出现了数种多次出现较有规律的 组合形式,而对于四四组合及更长的组合,字符串重复出现的频率小,分散度大,未得出较有 规律的组合方式.我们认为:充分统计并分析序列1-20种双字符串及三字符串出现的规 律已能较为全面地认识序列中的局部相关性及A、B两类的特征差异.因此,只对序列1 20种的双、三字符串进行统计分析,找出特征双字符串,特征三字符串 以下是以提取特征三字符串为例介绍统计算法 第一步确定各字符串的优先权重 三字符串共有64种可能排列方式,对这些三字符串进行初次排列,确定优先权重 以A类序列1为例, aggcacggaa.,g gctts
关于DNA序列分类问题的模型 507 1)指针指向第一个字符a,向后数两个字符,第一个出现的三字符串是ag,记录ag 2)指针向后移一个字符,第二个出现的三字符串是 3)以此类推,记录到该序列中最后一个三字符串(tgg)(特别的,如果相邻两个字符串 完全相同,只纪录一次) 同理可得序列2-10种所有出现的三字符串,最后把A类中所有这些三字符串按其出 现频率大小进行排序,出现频率多的字符串优先权重就大 第二步选出特征字符串,对字符串进行二次排序,找出特征字符串 仍以A类序列1为例: aggcacggaa 1)先考虑前5个字符,agca,其中包含了3个三字符串:ag,gc,ga,按第一步所得的 三字符串优先权重的大小,确定这3个字符串中有一个为特征字符串(如果gge在前10个 序列中出现的频率比ag和gca大,那么在本例中就选g,而不考虑第一个字符a) 2)再把指针移至特征字符串后的第一个字符(本例中移向a)重复(1)操作.以此类推 我们采用分类统计的方法进行排序,B类的操作方法同A类 第三步把A、B两类的所有特征字符串进行排序,计算出每个特征字符串在两类序列 (1-20)中出现的总次数.如果小于5次,认为此字符串不能体现A、B两类的特征差异,不 予考虑,这样,统计出1-20中出现频率较大的特征三字符串(共21种),他们在每个序列 中出现的频率为:3*该字符串在本序列中出现的次数/(SM+1),这里,M=3) 统计特征二字符串时,采取类似的方法,得出15个特征二字符串:他们在每个序列中 出现的频率为:2“该字符串在本序列中出现的次数/(S-M+1),这里,M=3) 4.2网络输入与输出变量的选取及处理 选取网络的输入变量时如输入变量过少,能引起建模不充分,过多的输入变量会降低 网络的学习速度,延长收敛时间,使模型的输入输出关系过于复杂.结合本题的实际情况, 我们提出两套输入变量选取方案 方案1输入每个序列中单字符及特征三字符串出现的频率(共25个输入变量) 方案2输入每个序列中单字符及特征双字符串出现的频率(共19个输入变量) 如果要同时考虑单字符特征双、三字符串出现的频率共需40个输入变量,模型过于复 杂.因此,暂不考虑这种方案 规定:A类序列的期望输出值为1,B类为1.这样,通过观察BP网络的输出值,可以 直观地判断未知序列的类别 .3BP网络的结构与参数 BP网络的结构与参数决定着网络学习的效果和分类识别的精度.其中,输入、输出节 点数由实际问题决定,本题中输出节点为1个.需要选择的是网络的激发函数,隐层数及各 层隐节点数 对方案1、2,各构造网络1、2与之相对应对于这两个网络,均选用三层BP网络,各层 激发函数均为双曲线正切函数(函数值在-1~+1之间变化) R. P Lippmann研究中指出(4);对于任给K个实数值样本,有2K+1个隐节点的三层 网络可以记忆它们,这个隐单元的激发函数可以是任何渐近函数.基于这一结论,我们根据