第31卷第1期 数学的实践与认识 Vol31 No. 1 20011 MATHEMATICS N PRACT CE AND THEORY Jan 2001 sequences The second is the peridic p roperty of the DNA sequences The th ird is that amount of info m aton of the sequences By using this m ethod, we classify the nature sequences and artif ical sequences A t last, we analyze the characteristic in this model and cons ider the generalization of th is model 关于DNA序列分类问题的模型 冯涛,康喆雯,韩小军 指导老师贺明峰 (大连理工大学,大连116024) 编者按本文以统计方法提取样本特征,以之作为BP神经网络的输入,用MA卫LAB中相应算法进行训 练然后用于解决本分类问题,得到了较准确的结果本文提取特征时考虑较为全面,在此基础上正确地运 用了神经网络方法,发挥了神经网络适用于非线性问题、具有自适应能力的优点思路清楚,文字简练 摘要:本文提出了一种将人工神经元网络用于DNA分类的方法作者首先应用概率统计的方法对20个 已知类别的人工DNA序列进行特征提取,形成DNA序列的特征向量,并将之作为样本输入BP神经网络进 行学习作者应用了 MATLAB软件包中的 NeuralNetwork Too lbox(神经网络工具箱)中的反向传播(Back propagation BP)算法来训练神经网络在本文中,作者构造了两个三层BP神经网络,将提取的DNA特征向 量集作为样本分别输入这两个网络进行学习通过训练后,将20个未分类的人工序列样本和182个自然序 列样本提取特征形成特征向量并输入两个网络进行分类结果表明:本文中提出的分类方法能够以很高的 正确率和精度对DNA序列进行分类,将人工神经元网络用于DNA序列分类是完全可行的 1问题重述(略) DNA序列由四个碱基A、T、C、G按一定规律排列而成已知所给人工序列1-10属 于A类,11-20属于B类本题中,我们的主要工作有两个 1)提取A、B两类特征; 2)以所提取A、B两类特征为依据,把20个人工序列及182个自然序列分为A、B两类 可能存在同时不具有A、B两类特征,不能归为A、B中任一类的序列) 在本题中,先以序列1-20为依据,提取出A、B两类序列的统计特征,然后运用神经网 络中的BP网络对未知序列进行了分类识别 2模型建立的理论依据 神经网络是近年来发展的一种大规模并行分布处理的非线性系统,其主要特点有 1)能以任意精度逼近任意给定连续的非线性函数 2)对复杂不确定问题具有自适应和自学习能力 3)具有较强的容错能力和信息综合能力,能同时处理定量和定性的信息,能很好地协 调多种输入信息的关系 传统的分类识别方法,对于一般非线性系统的识别很困难,而神经网络却为此提供了 2 01995-2004 Tsinghua Tongfang Optical Disc Co, LId. All rights reserved
第 31 卷第 1 期 2001 年 1 月 数学的实践与认识 M A TH EM A T ICS IN PRA CT ICE AND TH EO R Y V o l131 N o11 Jan. 2001 sequences. T he second is the periodic p roperty of the DNA sequences. T he th ird is that amount of info rm ation of the sequences. By using th is m ethod, w e classify the nature sequences and artifical sequences. A t last, w e analyze the characteristic in th is model and consider the generalization of th is model. 关于D NA 序列分类问题的模型 冯 涛, 康吉吉雯, 韩小军 指导老师: 贺明峰 (大连理工大学, 大连 116024) 编者按: 本文以统计方法提取样本特征, 以之作为BP 神经网络的输入, 用M A TLAB 中相应算法进行训 练. 然后用于解决本分类问题, 得到了较准确的结果. 本文提取特征时考虑较为全面, 在此基础上正确地运 用了神经网络方法, 发挥了神经网络适用于非线性问题、具有自适应能力的优点. 思路清楚, 文字简练. 摘要: 本文提出了一种将人工神经元网络用于DNA 分类的方法. 作者首先应用概率统计的方法对 20 个 已知类别的人工DNA 序列进行特征提取, 形成DNA 序列的特征向量, 并将之作为样本输入BP 神经网络进 行学习. 作者应用了M A TLAB 软件包中的N eural N etwo rk Too lbox (神经网络工具箱) 中的反向传播(Back p ropagation BP) 算法来训练神经网络. 在本文中, 作者构造了两个三层BP 神经网络, 将提取的DNA 特征向 量集作为样本分别输入这两个网络进行学习. 通过训练后, 将 20 个未分类的人工序列样本和 182 个自然序 列样本提取特征形成特征向量并输入两个网络进行分类. 结果表明: 本文中提出的分类方法能够以很高的 正确率和精度对DNA 序列进行分类, 将人工神经元网络用于DNA 序列分类是完全可行的. 1 问题重述(略) DNA 序列由四个碱基A、T、C、G 按一定规律排列而成. 已知所给人工序列 1- 10 属 于A 类, 11- 20 属于B 类. 本题中, 我们的主要工作有两个: 1) 提取A、B 两类特征; 2) 以所提取A、B 两类特征为依据, 把 20 个人工序列及 182 个自然序列分为A、B 两类 (可能存在同时不具有A、B 两类特征, 不能归为A、B 中任一类的序列). 在本题中, 先以序列 1- 20 为依据, 提取出A、B 两类序列的统计特征, 然后运用神经网 络中的BP 网络对未知序列进行了分类识别. 2 模型建立的理论依据 神经网络是近年来发展的一种大规模并行分布处理的非线性系统[ 1 ] , 其主要特点有: 1) 能以任意精度逼近任意给定连续的非线性函数; 2) 对复杂不确定问题具有自适应和自学习能力; 3) 具有较强的容错能力和信息综合能力, 能同时处理定量和定性的信息, 能很好地协 调多种输入信息的关系. 传统的分类识别方法, 对于一般非线性系统的识别很困难, 而神经网络却为此提供了一 © 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved
第31卷第1期 数学的实践与认识 Vol31 No. 1 20011 MATHEMATICS N PRACT CE AND THEORY Jan 2001 DNA序列分类的数学模型 吕金翅,马小龙,曹芳 指导老师陶大程 (中国科学技术大学,合肥230026) 编者按:本文能从生物学背景提出不同的三种判别模型建模的分析和文字叙述条理清楚,模型一对 21-40和182样本均进行了分类,分类正确率较高 摘要:本文从三个不同的角度分别论述了如何对DNA序列进行分类的问题,依据这三个角度分别建立了 型 首先,从生物学背景和几何对称观点出发,建立了DNA序列的三维空间曲线的表达形式建立了初步 数学模型-积分模型,并且通过模型函数计算得到了1到20号DNA序列的分类结果,发现与题目所给分类 结果相同,然后我们又对后20个DNA序列进行了分类 然后,从人工神经网络的角度出发,得到了第二类数学模型人工神经网络模型并且选择了三种适用 于模式分类的基本网络,即感知机模型,多层感知机(BP网络)模型以及LvQ矢量量化学习器,同时就本问 题提出了对BP网络的改进(改进型多层感知机),最后采用多种训练方案,均得到了较理想的分类结果同 时也发现了通过人工神经网络的方法得到的分类结果与积分模型得到的分类结果是相同的(前四十个) 最后,我们对碱基赋予几何意义:A.CGT分别表示右下左上用DNA序列控制平面上点的移动 每个序列得到一个游动曲线,提取游动方向趋势作为特征,建立起了模型函数,同时也得到了后二十个DNA 序列的分类结果,而且发现结果与上述两个模型所得到的分类结果几乎相同(其中有一个不同,在本模型中 表示为不可分的).此模型保留的信息量更多,而且稳定性更强 1问题的重述(略 2基本假设及模型建立 第一类数学模型积分模型 DNA序列是一种用4种字母符号A、T、G、C)表达的一维链在这条链上不仅包含有 制造人类全部蛋白质的信息(也就是基因),还有按照特定的时空模式把这些蛋白质装配成 生物体的四维调控信息(三维空间和一维时间),找到这些信息的编码方式和调节规律是人 类基因组研究的首要科学问题下面我们首先将着手从几何学的角度来分析DNA序列 鉴于自然界对称这一朴素原理,我们的模型始于对4种碱基对称性的考察图1.1(略)从纯 化学的角度,我们可以将碱基进行两类划分:(1)按双环或单环结构,可分为嘌呤碱基R(A 或G)与嘧啶碱基Y(C或T)(2)按环中对应位置上是否存在氨基或酮基,可分为氨基碱基 M(A或C)与酮基碱基KG或T)从生物学的角度,在双螺旋结构中,按碱基对形成氢键的 数目或强弱,碱基又可分:强氢键碱基SG或C)与弱氢键碱基W(A或T),这一种划分既 包含了化学的也包含了DNA双螺旋的结构信息在内 参照基本粒子理论中的做法,我们利用三维 Euclid空间中的对称几何图形—立方体 G来表示碱基的上述三种对称性如图1.2所示,以G的中心为坐标原点建立三维直角坐 c1995-2004 Tsinghua Tongfang Optical Disc Co, Lid. Al rights reserved
第 31 卷第 1 期 2001 年 1 月 数学的实践与认识 M A TH EM A T ICS IN PRA CT ICE AND TH EO R Y V o l131 N o11 Jan. 2001 D NA 序 列 分 类 的 数 学 模 型 吕金翅, 马小龙, 曹 芳 指导老师: 陶大程 (中国科学技术大学, 合肥 230026) 编者按: 本文能从生物学背景提出不同的三种判别模型. 建模的分析和文字叙述条理清楚, 模型一对 21—40 和 182 样本均进行了分类, 分类正确率较高. 摘要: 本文从三个不同的角度分别论述了如何对DNA 序列进行分类的问题, 依据这三个角度分别建立了 三类模型. 首先, 从生物学背景和几何对称观点出发, 建立了DNA 序列的三维空间曲线的表达形式. 建立了初步 数学模型- 积分模型, 并且通过模型函数计算得到了 1 到 20 号DNA 序列的分类结果, 发现与题目所给分类 结果相同, 然后我们又对后 20 个DNA 序列进行了分类. 然后, 从人工神经网络的角度出发, 得到了第二类数学模型- 人工神经网络模型. 并且选择了三种适用 于模式分类的基本网络, 即感知机模型, 多层感知机(BP 网络) 模型以及LVQ 矢量量化学习器, 同时就本问 题提出了对BP 网络的改进(改进型多层感知机) , 最后采用多种训练方案, 均得到了较理想的分类结果. 同 时也发现了通过人工神经网络的方法得到的分类结果与积分模型得到的分类结果是相同的(前四十个). 最后, 我们对碱基赋予几何意义: A. C. G. T 分别表示右. 下. 左. 上. 用DNA 序列控制平面上点的移动, 每个序列得到一个游动曲线, 提取游动方向趋势作为特征, 建立起了模型函数, 同时也得到了后二十个DNA 序列的分类结果, 而且发现结果与上述两个模型所得到的分类结果几乎相同(其中有一个不同, 在本模型中 表示为不可分的). 此模型保留的信息量更多, 而且稳定性更强. 1 问题的重述(略) 2 基本假设及模型建立: 第一类数学模型: 积分模型 DNA 序列是一种用 4 种字母符号(A、T、G、C) 表达的一维链. 在这条链上不仅包含有 制造人类全部蛋白质的信息(也就是基因) , 还有按照特定的时空模式把这些蛋白质装配成 生物体的四维调控信息(三维空间和一维时间) , 找到这些信息的编码方式和调节规律是人 类基因组研究的首要科学问题. 下面我们首先将着手从几何学的角度来分析DNA 序列. 鉴于自然界对称这一朴素原理, 我们的模型始于对 4 种碱基对称性的考察. 图 111 (略) 从纯 化学的角度, 我们可以将碱基进行两类划分: (1) 按双环或单环结构, 可分为: 嘌呤碱基R (A 或 G) 与嘧啶碱基 Y (C 或 T ) (2) 按环中对应位置上是否存在氨基或酮基, 可分为: 氨基碱基 M (A 或C) 与酮基碱基 K (G 或 T ) 从生物学的角度, 在双螺旋结构中, 按碱基对形成氢键的 数目或强弱, 碱基又可分: 强氢键碱基 S(G 或 C) 与弱氢键碱基W (A 或 T ) , 这一种划分既 包含了化学的也包含了DNA 双螺旋的结构信息在内. 参照基本粒子理论中的做法, 我们利用三维 Euclid 空间中的对称几何图形——立方体 G 来表示碱基的上述三种对称性. 如图 112 所示, 以 G 的中心为坐标原点建立三维直角坐 © 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved
第31卷第1期 数学的实践与认识 Vol31 No. 1 20011 MATHEMATICS N PRACT CE AND THEORY Jan 2001 sequences The second is the peridic p roperty of the DNA sequences The th ird is that amount of info m aton of the sequences By using this m ethod, we classify the nature sequences and artif ical sequences A t last, we analyze the characteristic in this model and cons ider the generalization of th is model 关于DNA序列分类问题的模型 冯涛,康喆雯,韩小军 指导老师贺明峰 (大连理工大学,大连116024) 编者按本文以统计方法提取样本特征,以之作为BP神经网络的输入,用MA卫LAB中相应算法进行训 练然后用于解决本分类问题,得到了较准确的结果本文提取特征时考虑较为全面,在此基础上正确地运 用了神经网络方法,发挥了神经网络适用于非线性问题、具有自适应能力的优点思路清楚,文字简练 摘要:本文提出了一种将人工神经元网络用于DNA分类的方法作者首先应用概率统计的方法对20个 已知类别的人工DNA序列进行特征提取,形成DNA序列的特征向量,并将之作为样本输入BP神经网络进 行学习作者应用了 MATLAB软件包中的 NeuralNetwork Too lbox(神经网络工具箱)中的反向传播(Back propagation BP)算法来训练神经网络在本文中,作者构造了两个三层BP神经网络,将提取的DNA特征向 量集作为样本分别输入这两个网络进行学习通过训练后,将20个未分类的人工序列样本和182个自然序 列样本提取特征形成特征向量并输入两个网络进行分类结果表明:本文中提出的分类方法能够以很高的 正确率和精度对DNA序列进行分类,将人工神经元网络用于DNA序列分类是完全可行的 1问题重述(略) DNA序列由四个碱基A、T、C、G按一定规律排列而成已知所给人工序列1-10属 于A类,11-20属于B类本题中,我们的主要工作有两个 1)提取A、B两类特征; 2)以所提取A、B两类特征为依据,把20个人工序列及182个自然序列分为A、B两类 可能存在同时不具有A、B两类特征,不能归为A、B中任一类的序列) 在本题中,先以序列1-20为依据,提取出A、B两类序列的统计特征,然后运用神经网 络中的BP网络对未知序列进行了分类识别 2模型建立的理论依据 神经网络是近年来发展的一种大规模并行分布处理的非线性系统,其主要特点有 1)能以任意精度逼近任意给定连续的非线性函数 2)对复杂不确定问题具有自适应和自学习能力 3)具有较强的容错能力和信息综合能力,能同时处理定量和定性的信息,能很好地协 调多种输入信息的关系 传统的分类识别方法,对于一般非线性系统的识别很困难,而神经网络却为此提供了 2 01995-2004 Tsinghua Tongfang Optical Disc Co, LId. All rights reserved
第 31 卷第 1 期 2001 年 1 月 数学的实践与认识 M A TH EM A T ICS IN PRA CT ICE AND TH EO R Y V o l131 N o11 Jan. 2001 sequences. T he second is the periodic p roperty of the DNA sequences. T he th ird is that amount of info rm ation of the sequences. By using th is m ethod, w e classify the nature sequences and artifical sequences. A t last, w e analyze the characteristic in th is model and consider the generalization of th is model. 关于D NA 序列分类问题的模型 冯 涛, 康吉吉雯, 韩小军 指导老师: 贺明峰 (大连理工大学, 大连 116024) 编者按: 本文以统计方法提取样本特征, 以之作为BP 神经网络的输入, 用M A TLAB 中相应算法进行训 练. 然后用于解决本分类问题, 得到了较准确的结果. 本文提取特征时考虑较为全面, 在此基础上正确地运 用了神经网络方法, 发挥了神经网络适用于非线性问题、具有自适应能力的优点. 思路清楚, 文字简练. 摘要: 本文提出了一种将人工神经元网络用于DNA 分类的方法. 作者首先应用概率统计的方法对 20 个 已知类别的人工DNA 序列进行特征提取, 形成DNA 序列的特征向量, 并将之作为样本输入BP 神经网络进 行学习. 作者应用了M A TLAB 软件包中的N eural N etwo rk Too lbox (神经网络工具箱) 中的反向传播(Back p ropagation BP) 算法来训练神经网络. 在本文中, 作者构造了两个三层BP 神经网络, 将提取的DNA 特征向 量集作为样本分别输入这两个网络进行学习. 通过训练后, 将 20 个未分类的人工序列样本和 182 个自然序 列样本提取特征形成特征向量并输入两个网络进行分类. 结果表明: 本文中提出的分类方法能够以很高的 正确率和精度对DNA 序列进行分类, 将人工神经元网络用于DNA 序列分类是完全可行的. 1 问题重述(略) DNA 序列由四个碱基A、T、C、G 按一定规律排列而成. 已知所给人工序列 1- 10 属 于A 类, 11- 20 属于B 类. 本题中, 我们的主要工作有两个: 1) 提取A、B 两类特征; 2) 以所提取A、B 两类特征为依据, 把 20 个人工序列及 182 个自然序列分为A、B 两类 (可能存在同时不具有A、B 两类特征, 不能归为A、B 中任一类的序列). 在本题中, 先以序列 1- 20 为依据, 提取出A、B 两类序列的统计特征, 然后运用神经网 络中的BP 网络对未知序列进行了分类识别. 2 模型建立的理论依据 神经网络是近年来发展的一种大规模并行分布处理的非线性系统[ 1 ] , 其主要特点有: 1) 能以任意精度逼近任意给定连续的非线性函数; 2) 对复杂不确定问题具有自适应和自学习能力; 3) 具有较强的容错能力和信息综合能力, 能同时处理定量和定性的信息, 能很好地协 调多种输入信息的关系. 传统的分类识别方法, 对于一般非线性系统的识别很困难, 而神经网络却为此提供了一 © 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved
期 冯涛等关于DNA序列分类问题的模型 个强有力的工具它实质上是选择了一个适当的神经网络模型来逼近实际系统目前,在 神经网络中应用最多的是BP网络 对于具有n个输入节点,m个输出节点的BP网络,输入到输出的关系可以看作是一个 n维欧式空间到m维欧式空间的映射,F:R→R",这一映射是高度非线性映射KT Funahashi于1989年证明了这样的一个定理2.如果BP网络隐层节点可以根据问题的不 同作相应的配置的话,那么用三层的激励函数为双曲线正切型的BP网络,可以以任意精度 逼近任意连续函数这一定理保证了BP网络在分类识别问题中的可用性 将复杂系统看作是一个黑箱,以实测输入,输出数据为学习样本,送入BP网络,网络通 过样本进行学习,在学习过程中,网络的权值不断地修改,使输入到输出的映象逐渐与实 际对象的特性相逼近,但网络输出的整体误差E小于给定的标准时,整个网络便模拟出实 际系统的外部特性 实际分类识别问题中,输入空间一般是多维欧式空间,我们可以计算空间中点与点的欧 式距离,并根据这些距离知道哪些样本互相靠得近,哪些样本相距甚远,也就是说在输入空 间中存在着一个距离度量,只要输入模式接近于某个输出模式,由于BP网络所具有的联想 记忆能力,则网络的输出亦会接近学习样本的输出 3模型的基本假设 1)假设碱基序列的特征值包括以下两个内容:(1)单个碱基在序列中的数量特征,即 ,T,C,G四种碱基在序列中的含量,(2)特征碱基串在序列中的数量特征(包括双字符碱 基串和三字符碱基串) 2)由于给定的已知碱基序列是从DNA全序列中随机截取出来的,因此无法确定序列 的起始位,无法从序列中辨认出氨基酸假设在对DNA序列分类时,是从碱基层次上进行 分类,而不是从氨基酸层次上分类 模型的建立与求解 41提取A、B两类的特征 经过计算,我们提取出A、B两类的统计特征(a)和(b),具体方法如下 特征(a):单个字符出现的频率特征a)对应基本假设1中的第1条 对1-20每个人工序列,我们统计出单个字符A、T、C、G出现的频率PiP=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、C、G四字母的不同组合(如两两组合,三三组合,四四组合) 出现频率的分析,可以知道对于双字符串和三字符串,均出现了数种多次出现较有规律的 组合形式,而对于四四组合及更长的组合,字符串重复出现的频率小,分散度大,未得出较有 规律的组合方式我们认为充分统计并分析序列1-20种双字符串及三字符串出现的规 律已能较为全面地认识序列中的局部相关性及A、B两类的特征差异因此,只对序列1- 20种的双、三字符串进行统计分析,找出特征双字符串,特征三字符串 2 21995-2004 Tsinghua Tong/ang Optical Disc Co, Ltd. All rights reserved
个强有力的工具. 它实质上是选择了一个适当的神经网络模型来逼近实际系统. 目前, 在 神经网络中应用最多的是BP 网络. 对于具有 n 个输入节点,m 个输出节点的BP 网络, 输入到输出的关系可以看作是一个 n 维欧式空间到 m 维欧式空间的映射, F: R n→R m , 这一映射是高度非线性映射. K. T. Funahash i 于 1989 年证明了这样的一个定理[ 2 ] : 如果BP 网络隐层节点可以根据问题的不 同作相应的配置的话, 那么用三层的激励函数为双曲线正切型的BP 网络, 可以以任意精度 逼近任意连续函数. 这一定理保证了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 i, P i= T iö(S— M + 1) , i= A , T , C, G S 为序列长度,M 为字符长度(这里,M = 1) , T i 为每个序列中 i 出现的次数. 序列 1- 20 特征(a) 的数值如下: (略) 特征(b): 特征字符串出现的频率. 特征(b) 对应基本假设 1 中的第 2 条 通过对序列 1- 20 种A、T、C、G 四字母的不同组合(如两两组合, 三三组合, 四四组合) 出现频率的分析, 可以知道: 对于双字符串和三字符串, 均出现了数种多次出现较有规律的 组合形式, 而对于四四组合及更长的组合, 字符串重复出现的频率小, 分散度大, 未得出较有 规律的组合方式. 我们认为: 充分统计并分析序列 1- 20 种双字符串及三字符串出现的规 律已能较为全面地认识序列中的局部相关性及A、B 两类的特征差异. 因此, 只对序列 1- 20 种的双、三字符串进行统计分析, 找出特征双字符串, 特征三字符串. 1 期 冯 涛等: 关于DNA 序列分类问题的模型 72 © 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved
数学的实践与认识 以下是以提取特征三字符串为例介绍统计算法 第一步确定各字符串的优先权重 三字符串共有64种可能排列方式,对这些三字符串进行初次排列,确定优先权重 以A类序列1为例, aggcacggaa.gttg 1)指针指向第一个字符a,向后数两个字符,第一个出现的三字符串是ag,记录agg 2)指针向后移一个字符,第二个出现的三字符串是ggc 3)以此类推,记录到该序列中最后一个三字符串(1gg)(特别的,如果相邻两个字符串 完全相同,只纪录一次) 同理可得序列2-10种所有出现的三字符串,最后把A类中所有这些三字符串按其出 现频率大小进行排序,出现频率多的字符串优先权重就大 第二步选出特征字符串,对字符串进行二次排序,找出特征字符串 仍以A类序列1为例 aggcacggaa 1)先考虑前5个字符,agca,其中包含了3个三字符串:ag,gge,gca,按第一步所得的 三字符串优先权重的大小,确定这3个字符串中有一个为特征字符串(如果gsc在前10个 序列中出现的频率比agg和gca大,那么在本例中就选ggc,而不考虑第一个字符a 2)再把指针移至特征字符串后的第一个字符(本例中移向a)重复(1)操作以此类推, 直至找出A类序列1-10种所有特征字符串 我们采用分类统计的方法进行排序B类的操作方法同A类 第三步把A、B两类的所有特征字符串进行排序,计算出每个特征字符串在两类序列 (1-20)中出现的总次数如果小于5次,认为此字符串不能体现A、B两类的特征差异,不 予考虑这样,统计出1-20中出现频率较大的特征三字符串(共21种),他们在每个序列 中出现的频率为3*该字符串在本序列中出现的次数/(sM+1),这里,M=3) 统计特征二字符串时,采取类似的方法,得出15个特征二字符串:他们在每个序列中 出现的频率为2*该字符串在本序列中出现的次数/(S-M+1),这里,M=3) 42网络输入与输出变量的选取及处理 选取网络的输入变量时,如输入变量过少,能引起建模不充分,过多的输入变量会降低 网络的学习速度,延长收敛时间,使模型的输入输出关系过于复杂结合本题的实际情况, 我们提出两套输入变量选取方案 方案1输入每个序列中单字符及特征三字符串出现的频率(共25个输入变量) 方案2输入每个序列中单字符及特征双字符串出现的频率(共19个输入变量) 如果要同时考虑单字符,特征双、三字符串出现的频率共需40个输入变量,模型过于复 杂因此,暂不考虑这种方案 规定:A类序列的期望输出值为-1,B类为1这样,通过观察BP网络的输出值,可以 直观地判断未知序列的类别 43BP网络的结构与参数 BP网络的结构与参数决定着网络学习的效果和分类识别的精度其中,输入、输出节 点数由实际问题决定,本题中输出节点为1个需要选择的是网络的激发函数,隐层数及各 层隐节点数 对方案1、2,各构造网络1、2与之相对应对于这两个网络,均选用三层BP网络,各层 C1995-2004 Tsinghua Tongfang Optical Disc Co.,, LId. All rights reserved
以下是以提取特征三字符串为例介绍统计算法: 第一步 确定各字符串的优先权重 三字符串共有 64 种可能排列方式, 对这些三字符串进行初次排列, 确定优先权重. 以A 类序列 1 为例, aggcacggaa. . . . . . gcttgg. 1) 指针指向第一个字符 a, 向后数两个字符, 第一个出现的三字符串是 agg, 记录 agg. 2) 指针向后移一个字符, 第二个出现的三字符串是 ggc. 3) 以此类推, 记录到该序列中最后一个三字符串(tgg) (特别的, 如果相邻两个字符串 完全相同, 只纪录一次). 同理可得序列 2- 10 种所有出现的三字符串, 最后把A 类中所有这些三字符串按其出 现频率大小进行排序, 出现频率多的字符串优先权重就大. 第二步 选出特征字符串, 对字符串进行二次排序, 找出特征字符串. 仍以A 类序列 1 为例: aggcacggaa 1) 先考虑前 5 个字符, aggca, 其中包含了 3 个三字符串: agg, ggc, gca, 按第一步所得的 三字符串优先权重的大小, 确定这 3 个字符串中有一个为特征字符串(如果 ggc 在前 10 个 序列中出现的频率比 agg 和 gca 大, 那么在本例中就选 ggc, 而不考虑第一个字符 a). 2) 再把指针移至特征字符串后的第一个字符(本例中移向 a) 重复(1) 操作. 以此类推, 直至找出A 类序列 1- 10 种所有特征字符串. 我们采用分类统计的方法进行排序,B 类的操作方法同A 类. 第三步 把A、B 两类的所有特征字符串进行排序, 计算出每个特征字符串在两类序列 (1- 20) 中出现的总次数. 如果小于 5 次, 认为此字符串不能体现A、B 两类的特征差异, 不 予考虑. 这样, 统计出 1- 20 中出现频率较大的特征三字符串(共 21 种) , 他们在每个序列 中出现的频率为: 33 该字符串在本序列中出现的次数ö(S—M + 1) , 这里,M = 3) 统计特征二字符串时, 采取类似的方法, 得出 15 个特征二字符串: 他们在每个序列中 出现的频率为: 23 该字符串在本序列中出现的次数ö(S—M + 1) , 这里,M = 3). 4. 2 网络输入与输出变量的选取及处理 选取网络的输入变量时, 如输入变量过少, 能引起建模不充分, 过多的输入变量会降低 网络的学习速度, 延长收敛时间, 使模型的输入输出关系过于复杂. 结合本题的实际情况, 我们提出两套输入变量选取方案. 方案 1 输入每个序列中单字符及特征三字符串出现的频率(共 25 个输入变量) 方案 2 输入每个序列中单字符及特征双字符串出现的频率(共 19 个输入变量) 如果要同时考虑单字符, 特征双、三字符串出现的频率共需 40 个输入变量, 模型过于复 杂. 因此, 暂不考虑这种方案. 规定: A 类序列的期望输出值为- 1,B 类为 1. 这样, 通过观察BP 网络的输出值, 可以 直观地判断未知序列的类别. 4. 3 BP 网络的结构与参数 BP 网络的结构与参数决定着网络学习的效果和分类识别的精度. 其中, 输入、输出节 点数由实际问题决定, 本题中输出节点为 1 个. 需要选择的是网络的激发函数, 隐层数及各 层隐节点数. 对方案 1、2, 各构造网络 1、2 与之相对应. 对于这两个网络, 均选用三层BP 网络, 各层 82 数 学 的 实 践 与 认 识 31 卷 © 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved