DNA序列分类的神经网络方法

文章编号:1006-9348(2003)02-0065-04

计　算　机　仿　真

2003年2月　　

DNA序列分类的神经网络方法

李银山1,2,杨春燕3,张伟4

(1.天津大学建筑工程学院,天津,300072;2.太原理工大学应用力学研究所,太原030024;3.中国平安保险公司广东分公司,广州510090;4.北京工业大学机电工程学院,北京100022)

摘要:该文将人工神经网络方法用于DNA分类。首先应用概率统计的方法对20个已知类别的人工DNA序列进行特征提取,形成DNA序列的特征向量,并将之作为样本输入BP神经网络进行学习。采用MATLAB软件包中的神经网络工具箱中的反向传播算法来训练神经网络。构造了两个三层BP神经网络,将提取的DNA特征向量集作为样本分别输入这两个网络进行学习。通过训练后,将20个未分类的人工序列样本和182个自然序列样本提取特征向量并输入两个网络进行分类。结果表明:分类方法能够以很高的正确率和精度对DNA进行分类,将人工神经网络用于DNA序列分类是完全可行的。关键词:分类;神经网络;遗传密码中图分类号:TP183　　文献标识码:A

1　问题描述[1]

2000年6月,人类基因组计划中DNA全序列草图完成,预计2001年可以完成精确的全序列图,此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的“天书”。这本大自然写成的“天书”是由4个字符A,T,C,G按一定顺序排成的长约30亿的序列,其中没有“断句”也没有标点符号,除了这4个字符表示4种碱基以外,人们对它包含的“内容”知之甚少,难以读懂。破译这部世界上最巨量信息的“天书”是二十一世纪最重要的任务之一。在这个目标中,研究DNA全序列具有什么结构,由这4个字符排成的看似随机的序列中隐藏着什么规律,又是解读这部天书的基础,是生物信息学最重要的课题之一。虽然人类对这部“天书”知之甚少,但也发现了DNA序列中的一些规律性和结构。例如,在全序列中有一些是用于编码蛋白质的序列片断,即由这4个字符组成的64种不同的3字符串,其中大多数用于编码构成蛋白质的20种氨基酸。又例如,在不用于编码蛋白质的序列片断中,A和T的含量特别多些,于是以某些碱基特别丰富作为特征去研究DNA序列的结构也取得了一些结果。此外,利用统计的方法还发现序列的某些片断之间具有相关性,等等。这些发现让人们相信,DNA序列中存在着局部的和全局性的结构,充分发掘序列的结构对理解DNA全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某些细节,突出特征,然后将其表示成适当的数学对象。这种被称为粗粒化和模型化的方法往往有助于研究规律和结构。

作为研究DNA序列的结构的尝试,提出以下对序列集

合进行分类的问题:

①有20个已知类别的人工制造的序列(见网址),其中序列标号1～10为A类,11～20为B类。请从中提取特征,构造分类方法,并用这些已知类别的序列,衡量你的方法是否足够好。然后用你认为满意的方法,对另外20个未标明类别的人工序列(标号21～40)进行分类,把结果用序号(按从小到大的顺序)标明它们的类别(无法分类的不写入):

A类

;B类

。

请详细描述你的方法,给出计算程序。如果你部分地使用了现成的分类方法,也要将方法名称准确注明。

这40个序列放在如下地址的网页上,用数据文件Art-model-data标识,供下载:

网易网址:www.163.com教育频道在线试题;教育网:www.cbi.pku.edu.cnNewsmcm2000教育网:www.csiam.edu.cn/mcm

②在同样网址的数据文件Nat-model-data中给出了182个自然DNA序列,它们都较长。用你的分类方法对它们进行分类,像①一样地给出分类结果。

2　遗传密码

[2]

生命是核酸和蛋白质相互作用的系统。遗传信息储存在DNA或RNA书写的核酸序列中,这序列就是遗传信息的载体。如果说核酸是4种碱基书写的语言,蛋白质是用20种氨基酸书写的语言,则遗传密码就是这两种语言的联系。

蛋白质是生命功能的执行者,DNA的复制保证了细胞分裂过程中的准确传递。DNA能指导生成蛋白质,同时蛋白质又反作用于核酸、调节DNA信息的表达、遗传密码的破译,有效地揭示了信息如何从核酸传递到蛋白质的秘密。

遗传信息储存在核酸序列中,用信息量来描述核酸序列的各种变化。信息量是从一个不确定性的消息集合的信息

资金项目:国家自然科学基金“九五”重大项目资助(19990510)

山西省自然科学基金项目(20001007)

收稿日期:2000-02-28

—65—源中,获得一个确定信息时所减少的不确定性的度量。它的单位是比特(Bit)。其意义是:如果在两种机会均等的可能性中选择一种,那么信息量为一比特,如果要连续回答K个“是”或“否”才能弄清楚,那么这个问题的信息量就是K比特。用4种碱基来编码20种氨基酸,至少要碱基的三联体,也就是说编码一个氨基酸的核苷酸(碱基)数不能小于3。从信息论的观点来看,一个氨基酸的信息量是4.32比特,而一个核苷酸的信息量仅2比特,必须用3个核苷酸才能编码一个氨基酸。4个核苷酸的三联体(密码子)共有64种(4×4×4=64)用64种密码子编码20种氨基酸,则有些氨基酸就对应几个密码子,即密码简并,这种简并大多发生在密码子的第三位碱基。

德国著名医学家Schonberger曾将《易经》的思想置于现代科学的角度来研究生物遗传工程,推出了遗传密码表如表1所示。

表1　遗传密码表

氨基酸

TPhe

T

PheLeuLeuLeu

C

LeuLeuLeuVal

G

ValValValIle

A

IleMet(起始)Met(起始)

CSerSerSerSerProProProProAlaAlaAlaAlaThrThrThrThr

GCysCysTrpTrpArgArgArgArgGlyGlyGlyGlySerSer终止终止

ATyrTyr终止终止HisHisGlnGlnAspAspGluGluAsnAsnLysLys

TCGATCGATCGATCGA

传统的分类识别方法,对于一般非线性系统的识别很困难,而神经网络却为此提供了一个强有力的工具。它实质上是选择了一个适当的神经网络模型来逼近实际系统,通常采用如下几种方案:①单层感知器;②BP网络;③改进型BP网络;④LVQ矢量量化学习。

目前,在神经网络中应用最多的是BP网络。

对于具有n个输入节点,m个输出节点的BP网络,输入到输出的关系可以看作是一个n维欧氏空间到m维欧氏空间的映射F:Rn※Rm,这一映射是高度非线性映射。K.T.Funahashi于1989年证明以下的定理。

定理:如果BP网络隐层节点可以根据问题的不同作相应的配置的话,那么用三层的激励函数为双曲线正切型的BP网络,可以以任意精度逼近任意连续函数。

这一定理保证了BP网络在分类识别问题中的可用性。将复杂系统看作是一个黑箱,以实测输入,输出数据为学习样本,送入BP网络,网络通过样本进行学习,在学习过程中,网络的权值不断地修改,使输入到输出的映象逐渐与实际对象的特性相逼近,当网络输出的整体误差E小于给定的标准时,整个网络便模拟出实际系统的外部特性。

实际分类识别问题中,输入空间一般是多维欧氏空间,我们可以计算空间中点与点的欧氏距离,并根据这些距离知道哪些样本互相靠得近,哪些样本相距甚远,也就是说在输入空间中存在着一个距离度量,只要输入模式接近于某个输出模式,由于BP网络所具有的联想记忆能力,则网络的输出亦会接近学习样本的输出。

4　模型的建立与求解[4,5]

4.1　特征提取

这是一个比较典型的分类问题,为了表述的严格和方便,我们用数学的方法来重述这个问题。已知字母序列S1,S2,…,S40,Si=x1x2x3…xj…xn,其中xj∈{a,t,c,g};有字

i

符序列集合A,B,满足A∩B= ,并当1≤i≤10时,Si∈A;当11≤i≤20时,Si∈B。现要求考虑当21≤i≤40时,Si与集合A及集合B的关系。

在这里,问题的关键就是要从已知的分好类的20个字母序列中提取用于分类的特征。知道了这些特征,我们就可以比较容易地对那些未标明类型的序列进行分类。

首先,我们提取的特征应该满足以下两个条件:①所取特征必须可以标志A组和B组;②所取特征必须是有一定的实际意义的。

对于这样的一个复杂的分类问题,需要考虑的因素很多,也就是说,可供我们使用的分类特征有许多。如何从众多的因素中提取分类的主要因素,是我们处理这个问题的困难之处,上面的第一个条件是我们的分类方法所必须满足的,可以看作是个限制条件;而第二个条件是我们在设计分类方法时必须考虑到的,可以看作是对分类方法优劣的一种衡量,是某种意义下的目标函数。

由易经推出的遗传密码表不仅整体上表现出十分严整的顺序,从0至15与16至31氨基酸的排列(Phe,Leu,Val,Ile,Ser,Pro,Ala,Thr,Cys,Arg,Gly,Ser,Tyr,His,Asp,Asn)具有严格的周期性,从32至47和48至63而且还发现原密码表的缺陷,对于高等生物密码变异情况,全都可以给出解释。

3　神经网络方法

[3]

由于神经网络具有运用已知认识新信息,解决新问题,学习新方法,预见新趋势,创造新思维的能力,所以我们将神经网络处理问题的方法介入进来,处理模式分类的问题。神经网络的主要特点有:高度的并行性;高度的非线性全局作用;良好的容错性与联想记忆功能。十分强的自适应,自学习功能。

—66—特征提取方法如下:

方法1,基于字母出现的频率。

不同段的DNA中,每个碱基出现的概率并不相同,从生物理论中,我们知道,编码蛋白质的DNA中G、C含量偏高,而非编码蛋白质的DNA中A、T含量偏高。因此,A、G、T、C的频率中会含有很多的信息。

方法2,基于字母出现的周期性。

一个序列所含的信息远不止每个字母出现的频率,还有字母前后若干个字母的相关联性,字母在序列中出现的规律性。

方法3,基于序列熵值。

把一串DNA序列看成一个信息流,这与生物学的基础知识是相应的,关于A、B的分类,可以考虑其单位序列所含信

息量(即熵)的多少。从直观上来看,我们可以认为,重复得越多,信息量越少。

4.2　提取A、B两类的特征

经过计算,我们提取A、B两类的统计特征,具体方法如下:

特征1:单个字符出现的频率。

对1—20每个人工序列,我们统计出单个字符A、T、C、G出现的频率Pi,Pi=

Ti

,i=A,T,C,G

S-M+1

S为序列长度,M为字符长度(这里,M=1),Ti为每个

序列中i出现的次数。表2给出了A、T、C、G的频率统计,由统计的数字可以看出,A组的碱基构成与B组的碱基构成有较大的不同。A组的G含量较高,B组的T含量较高。

表2　A、T、C、G的频率统计

P/%ATCG

130141740

227151641

32762245

442291118

523112342

635131340

735191036

828191637

921152143

1018142741

113550510

123350315

1325521013

143050812

15296506

16364689

1735262514

182950129

192256157

202056176

　　特征2:特征三字符串出现的频率。

通过对序列1—20种A、T、C、G四字母的不同组合(如三三组合)出现频率的分析,充分统计并分析序列1—20种三字符串出现的规律能较为全面地认识序列中的局部相关性及A、B两类的特征差异并具有实际意义。因此,只对序列1—20种的三字符串进行统计分析,找出特征三字符串。以下是以提取特征三字符串为例介绍统计算法:

第一步　确定各字符串的优先权重

三字符串共有64种可能排列方式,对这些三字符串进行初次排列,确定优先权重。

以A类序列1为例,aggcacggaa......gcttgg.

①指针指向第一个字符a,向后数两个字符,第一个出现的三字符串agg,记录agg.

②指针向后移一个字符,第二个出现的三字符串ggc。③以此类推,记录到该序列中最后一个三字符串(tgg)(特别地,如果相邻两个字符串完全相同,只记录一次)。

同理可得序列2—10种所有出现的三字符串,最后把A类中所有这些三字符串按其出现频率大小进行排序,出现频率多的字符串优先权重就大。

第二步　选出特征字符串,对字符串进行二次排序,找出特征字符串。

仍以A类序列1为例:aggcacggaa......gcttgg.

①先考虑前5个字符,aggca,其中包括了3个三字符串:agg,ggc,gca按第一步所得的三字符串优先权重的大小,确定这3个字符串中有一个为特征字符串(如果ggc在前10个序列中出现的频率比agg和gca大,那么在本例中就选,ggc,

而不考虑第一个字符a)。

②再把指针移至特征字符串后的第一个字符(本例中移向a)重复①操作。以此类推,直至找出A类序列1—10种所有特征字符串。

我们采用分类统计的方法进行排序,B类的操作方法同A类。

第三步　把A、B两类的所有特征字符串进行排序,计算出每个特征字符串在两类序列(1—20)中出现的总次数。如果小于5次,认为此字符串不能体现A、B两类的特征差异,不予考虑。这样,统计出1—20中出现频率较大的特征三字符串(共21种),他们在每个序列中出现的频率为:Pi=Ti

(M=3),i是某三字符串。

S-M+1

4.3　网络输入与输出变量的选取及处理

选取网络的输入变量时,如输入变量过少,会引起建模不充分,过多的输入变量会降低网络的学习速度,延长收敛时间,使模型的输入输出关系过于复杂。结合本题的实际情况,我们提出两套输入变量选取方案:

方案1,输入每个序列中单字符出现的频率(共4个输入变量);

方案2,输入每个序列中特征三字符串出现的频率(共21个输入变量)。

规定:A类序列的期望输出值为—1,B类为1,这样,通过观察BP网络的输出值,可以直观地判断未知序列的类别。4.4　BP网络的结构与参数

BP网络的结构与参数决定着网络学习的效果和分类识

—67—别的精度。其中,输入、输出节点数由实际问题决定,本题中输出节点为1个。需要选择的是网络的激发函数,隐层数及各层隐节点数。

对方案1、2,各构造网络1、2与之相对应。对于这两个网络,均选用三层BP网络,各层激发函数均为双曲线正切函数(函数值在-1～+1之间变化)。

力,为分类提供了一种新方法;

②传统的分类方法是一种模型驱动方法,大部分统计模型基于线性回归,而神经网络用数据驱动方式来解决分类问题,它通过样本学习逼近实际系统模型的能力很强;

③由于BP网络的信息分布性,各输入变量对输出变量的影响在对样本学习时已自动记下,并由整个网络的内部表达而表现出来,从而省略了通常建模前所需的对各变量的相关分析;

④BP网络有更多的可调变量(各权值、阀值),故网络可以以更复杂的方式逼近系统的外部特征。BP的模型的不足之处在于存储于各权上的知识人们无法理解,所建立的模型难以用解析方式表达出来。参考文献:

[1]　李银山,王拉娣,张建明,白育坤.数学建模案例分析[M].海洋

出版社,1999.

[2]　王文清.生命科学[M].北京工业大学出版社,1998.

[3]　丛爽.面向MATLAB工具箱的神经网络理论与应用[M].中国科

学技术大学出版社,1998.[4]　李银山,白育

,卢准炜,张镇锁.风险投资的多目标优化仿真

模型[J].计算机仿真,1999,16(4).

[5]　李银山,杨海涛,商霖.自动化车床管理的仿真及优化设计[J].

2001,18(5):49-51.

5　结果及分析

5.1　对人工序列21～40的分类

我们应用MATLAB软件包中的神经网络工具(BP网络)对未知序列进行分类,我们发现:若以高于0.9和低于-0.9作为分类标准,两个BP网络的命中率相同,但输出函数值不等,网络2的输出值与期望值更接近。这种情况出现的原因是:

①网络1中输入变量较网络2少,在样本集个数相同的情况下,建模不够充分;

②单字符的形式较三字符串的组合形式少,因此,采用特征三字符串能更好地体现序列中片段的相关性。

经过反复训练、检验、分类,我们发现:网络2较网络1学习速度快,对未知序列区分的精度更高,因此,认为网络2更优。在这里,采用网络2的分类结果。

A类:22,23,25,27,29,34,35,36,37,39;B类:21,24,26,28,30,31,32,33,38,40。5.2　对182个自然序列分类

我们把21～40已明确分类的序列加入到样本中,重新对网络2进行训练,直至达到误差10然序列的分类结果(略)。

-5

作者简介

1961—),男(汉族),山西平遥人,副教授,李银山(

博士,已发表论文40余篇,专著一本,研究方向:非线性振动,结构优化设计,转子动力学。

,可以得到182个自

6　结论

　　①基因特征这种非线性系统很难用数学方程表达出来,而且可利用的样本有限以至于传统的分类识别方法显得无效,神经网络从其良好的学习功能和很强的非线性计算能

性动力学。

杨春燕(1977—),女(汉族),河南驻马店人,助理经

济师,学士,研究方向:计算机仿真。

张　伟(1960—),男(汉族),天津市人,教授,博士,研究方向:非线

TheNeuralNetworkMethodofClassificationsforDNASequences

LIYin-shan

1,2

,YANGChun-yan,ZHANGWei

34

(1.SchoolofConstructionalEngineering,TianjinUniversity,Tianjin300072,China;2.InstituteofAppliedMechanics,TaiyuanUniversityofTechnology,Taiyuan030024,China;

3.GuangdongBranchCompany,ChinesePinganInsuranceCompany,Guangzhou510090,China;4.SchoolofMechanicalEngineering,BeijingPolytechnicUniversity,Beijing100022,China)

ABSTRACT:ThispaperpresentsamethodapplyingartificialneuralnetworktoDNAclusteringproblem.FirstweusetheprobabilitystatisticsmethodtoextractthecharactersfromtheartificialDNAsequenceswhosecategoriesareknown.Thuswecangetthecharactervectorsofthe

DNAsequencesandinputthemassamplesintoBPneuronNNforlearning.WeemploytheBP(backpropagation)algorithmtotrainNNbyuseoftheNeuralNetworkToolboxinMATLABsoftwarepackage.Inthispaper,twothree-storyNNarecreatedtoinputtheextractedDNAchar-actervectorsassamplesintothem.Afterthetraining,charactersareextractedfromthe20unclassifiedartificialsequencesamplesand182nat-uralsequencesamplestoformthecharactervectorsasinputofthetwoNNforclustering.Theresultsshows:theclusteringmethodpresentedinthispapercanclassifytheDNAsequencesinquitehighaccuracyandprecision.ItisquitefeasibletoapplytheartificialneuralnetworktoDNAsequenceclustering.KEYWORDS:Classifications;Neuralnetwork;Geneticcode

—68—