第31卷第1期2001年1月
数学的实践与认识
M A TH EM A T I CS I N PRA CT I CE AND TH EO R Y
V o l131 N o11
Jan.2001
D NA序列的分类模型
汤诗杰, 周 亮, 王晓玲
指导老师: 孙广中
(中国科技大学,合肥 230026)
编者按: 本文提出了DNA序列分类的三种模型,其一,基于A、G、T、C四种碱基出现的频率;其二利用了
同一碱基在序列中的间隔,这一信息是单纯考虑频率所不能包含的;在第三种模型中,作者把DNA序列视
为一个信息流,考虑每增加一个字符所带来的信息增量.尽管文中信息量的定义方式仍可讨论,但本文思想新颖活跃,有其独特之处.本文最后的分类方法,是以上三种的综合使用.
摘要: 本文针对DNA序列分类这个实际问题,提出了相应的数学模型.为了很好的体现DNA序列的局
部性和全局性的特征,我们给出了衡量分类方法优劣的标准,即在满足一定限制条件的情况下,是否能充分反映序列的各方面特性.
依据我们提出的判别标准,单一标准的分类是无法满足要求的.我们的方法是侧重点不同的三种方法的综合集成.这三种方法分别体现了序列中元素出现的概率,序列中元素出现的周期性,序列所带有的信息含量.利用这个方法,完成了对未知类型的人工序列及自然序列的分类工作.最后,对分类模型的优缺点进行了分析,并就模型的推广作了讨论.
1 问题的提出(略)
2 问题的分析
这是一个比较典型的分类问题,为了表述的严格和方便,我们用数学的方法来重述这个问题.已知字母序列S1,S2,S3……S40,S i=x1x2x3…x n i,其中x j∈{a,t,c,g};有字符序列集合A,B,满足A∩B=<,并当1ΦiΦ10时,S i∈A;当11ΦiΦ20时,S i∈B.现要求考虑当21ΦiΦ40时,S i与集合A及集合B的关系.
在这里,问题的关键就是要从已知的分好类的20个字母序列中提取用于分类的特征.知道了这些特征,我们就可以比较容易的对那些未标明类型的序列进行分类.下面我们将首先对用于分类的标准问题进行必要的讨论.
3 分类的标准及评价
首先,我们提取的特征应该满足以下两个条件:
(1)所取特征必须可以标志A组和B组.也就是说,我们利用这些特征应该可以很好的区分已经标示分类的20个序列.这是比较显然的一个理由.
(2)所取特征必须是有一定的实际意义的.这一点是决不能被忽视的.比如,如果不考虑模型的实际意义,我们就可以以序列的开头字母为分类标准:已知在B类中的十个序列都是以g t开始的,而已知在A类中10个序列没有以g t开始的,甚至以g开始的都没有.显然这是满足上面的第一个条件的.如果仅因此就认为这种特征是主要的,并简单的利用这个特征将所有待分类的序列分成两类,显然是不甚合理的.
对于这样的一个复杂的分类问题,需要考虑的因素很多,也是就说,可供我们使用的分类特征有许多.如何从众多的因素中提取分类的主要因素,是我们处理这个问题的困难之处.上面的第一个条件是我们的分类方法所必须满足的,可以看作是个限制条件;而第二个条件是我们在设计分类方法时必须考虑到的,可以看作是对分类方法优劣的一种衡量,是某种意义下的目标函数.
4 模型的建立及分析
由上面的分析可知,由于DNA 序列本身的复杂性,我们很难在不知道确切的分类标准的情况下,使用单一的方法来处理这个分类问题.由于,DNA 序列同时具有局部性和全局性的特征,我们尝试综合使用几种设计思想不同的方法来处理这个问题,以使该分类方法具有好的分类性能和相当的健壮性.
下面我们先从不同的角度出发,提出三种侧重点不同的分类方法,第一种从频率角度出发,第二种从字母出现的周期性的角度出发,第三种从序列所带的某方面的信息量出发,并给出它们单独使用时的分类结果.我们认为,这三方面综合考虑,可以较好的体现出序列各个方面的特征,最后,从这三种方法出发,得到一个综合系统的分类方法,并利用它得到了最终的182个序列的分类结果.
方法1 基于字母出现频率
不同段的DNA 中,每个碱基出现的概率并不相同,从生物理论中,我们知道,编码蛋白质的DNA 中G 、C 含量偏高,而非编码蛋白质的DNA 中A 、T 含量偏高.因此,A 、G 、T 、C 的频率中会含有很多的信息,下面给出A 、B 组的频率统计
.见表1,表2(略).由统计的数字可以看出,A 组的碱基构成与B 组的碱基构成有较大的不同.A 组的G 含量较高,B 组的T 含量较高.为做定量化的分析,引入数学中的内积概念,即将A 、T 、G 、C 的频率分别作为四维向量的四个分量(P A ,P G ,P T ,P C ),现在我们得到两组向量A i 、B i (i =1,2,3……10),然后将未知的序列21～40作为一个新的向量C ,要将它归入A 组或B 组,我们可以尝试在H ilbert 空间中将向量归一化后求C 与A 组和B 组的平均距离.记C 、A i 、B i
为归一化后的向量.为此,我们计算内积和∑10
i =1
C A i 与∑10
i =1
C B i ,其中内积定义为欧氏度
量引导出的内积(c 1,c 2,c 3,c 4).(a 1,a 2,a 3,a 4)=c 1a 1+c 2a 2+c 3a 3+c 4a 4.即
内积=
(P A ,P G ,P T ,P C )A (P A ,P G ,P T ,P C )未知
A 未知
内积小的两个序列,我们可以认为它们的相关性小,而内积大的序列,我们就认为其相
关性大.因此,如果∑10
i =1
C .A i >
∑10
i =1
C .B
i
,则认为C 应归入A 类,否则认为它应归入B 类.
计算结果如表3所示
由此,我们找到了区分C 组的一种方法,这种比较∑10
i =1
C A i 和∑10
i =1
C B i 的方法,我们可
以归纳为一个目标函数F 1(l ),即
F 1(l )=
∑10
i =1
C A
i
∑10
i =1
C B
i
02数 学 的 实 践 与 认 识31卷
表3
未知的序号与A 组的内积与B 组的内积属于的类别未知的序号与A 组的内积与B 组的内积属于的类别
10.8157810.938814B 110.8522310.920957B 20.9269220.803952A 120.8669760.853967A 30.9397270.656827A 130.8609550.917122B 40.7885240.937135B 140.9616890.67678A 50.9481940.772073A 150.9603220.739089A 60.8012010.930121B 160.9042820.747578A 70.9530190.76695A 170.9447240.723664A 80.7460710.968035B 180.758620.954652B 90.9310070.613193A 190.8856310.811837A 10
0.897774
0.844082
A
20
0.75584
0.941
B
方法一讨论 这种方法是从概率统计的角度分析问题,通过对每个字母出现频率的计算,找出A ,B 两类DNA 链中的频率特性,建立四维向量空间,然后对待求分类的序列统计频率,与已知分类的向量进行内积运算,找出量化的关联性,从而将其分类.但这种方法也有其局限性,在统计字母出现的频率时,忽略了字母所在位置以及各个字母之间的相互关系,造成用这种方法对已知分类的序列进行检验时,个别频率特性不明显的序列不太容易分类.所以,这种方法虽然有其科学性,但还不够完善,不能完全体现序列的所有特征.方法二 基于字母出现周期性
在以上进行了基于字母出现频率的分类之后,我们认为,一个序列所含的信息远不止每个字母出现的频率,还有字母出现和它前后若干个字母的相关联性,字母在序列中出现的规律性等等.前一个问题我们留到下面讨论,现在我们想办法处理后一个问题.
对于某单个字母,以a 为例,假设它在序列中第t 1,t 2,……,t k +1,个位置出现,我们试图找出这些数字之间的关联.首先,可以认识到考查t i 的分布及绝对值是意义不大的,因为序列是一大段DNA 中的一个片断,片断的起始段不同会导致t i 的不同.于是为了抵消ti 的线性位移,考虑下面一组值
s i =t i +1-t i i =1,2,…,k 即字母a 出现的间距.
可以看出,序列s 1,s 2,……,s n 的大小包含的信息是a 的“稠密度”,也可看成一个与频率有关的量,前面已经处理过.所以我们可以考虑序列s 1,s 2,……,s n 的波动幅度,幅度越小,说明s i (i =1,2,……,k )的值越趋于统一,即a 的出现周期性越大.而表征波动幅度的量在统计中是中心矩.现求s i 的二阶中心矩,即方差.
V ar a (s 1,s 2,……,s n )=
1n -l
∑n
i =l
(s
i
-s )2
,s =
∑n
i =l
s
i
n
同理,可以求出V ar g 、V ar t 、V ar c .
由所得数据知,对V ar g 与V ar t ,上述方法对A 、B 组的区分率很高,就有良好的可分辨性.为了强调这种特征的显著性,我们用F 2=V ar g V ar t 作为这种方法的目标函数
.由图1可以看出点与原点连线的斜率在A 组中和B 组中有显著差别,根据这个特征,A 组和B 组可以很好地区分开来,并且较好地弥补了方法一中的不全面之处.
方法二讨论 这种方法是从序列中相邻相同字母之间的距离即字母出现的周期性着手
1
21期汤诗杰等:DNA 序列的分类模型
图1
分析的
.它统计了每个字母在序列中两次出现的间隔,并且用方差度量这种间隔的波动大小,由此找到了一个能较好区分A ,B 组的目标函数,综合地考虑了序列全局和局部的性质.
方法3 基于序列熵值
我们可以把一串DNA 序列看成一个信息流,这与生物学的基础知识是相应的.关于
A 、
B 的分类,可以考虑其单位序列所含信息量(即熵)的多少.从直观上来看,我们可以认为,重复得越多,信息量越少..这是我们通过观察A 、B 组的特点而归纳出的方法
.设序列为L =(a 1,a 2,a 3,……,a n );前m 个字符所带的信息量为f m (l ),记
g m (l )=f m (l )-f m -1(l ),
即g m (l )为加上第m 个字母之后所增加的信息量.然后,由g m (l )=f m (l )-f m -1(l ),得
f n (l )=
∑
n
i =1
g i (1),则f n (l )为整个序列所带的信息量.F 3(l )=
f n (1)
1
即为单位长度所带的
信息量.现在的问题就归结为如何找出一个合适的g m (l ).
我们有理由认为:g 具有以下性质:
性质1:g m (l )>0.即任意加上一个字符,它或多或少带有一定信息量;
性质2:第m 个字符(或者是以它结尾的较短序列)与前面的序列(信息流)重复得越多,g m (l )的值必然越小;
性质3:第m 个字符(或者是以它结尾的较短序列)如果和与它靠得越近的重复,g m (l )的值越小;和与它离得越远的重复,g m (l )的值越大;
性质4:f 0(l )=0.
对此,我们可以构造如下函数:
22数 学 的 实 践 与 认 识31卷
g m (l )=
b
b +t 1Ρ1+t 2Ρ2+……+t p Ρp
其中b 为防止分母为零而设的一个小正数;
Ρi =∑m
i =1
a t ?it
;
?it =
1 0
以第m -t 个字符结尾的i 字串且与以第t 个字符结尾的i 字串完全相同 否则
a 为一个小于1的数,其存在体现了g 的性质3,即如果越近的位置出现重复,认为字串信息量越少,反之较多.
Ρi 的表达式中,t 表示两个相同字串之间的距离,i 表示字串长度,这个表达式定量的给出距离和信息量之间的关系.
又由于长度不同的字串重复对信息量的影响是不同的,所以必须在Ρi 前乘上一个权值
t i ,由概率统计的知识可知,这种影响是呈指数上升的,则可选择一适当的常数c >1,使得t i
=c i -1,这个表达式定量的给出长度和信息量之间的关系.
可以认为,字串长度太大的重复非常少见,则可将p 取为某一固定的正数.那么,给出
a 、
b 、
c 、p 四个参数,就可以把f
n
严格确定下来.通过反复上机搜索,我们认为,取p =6,即
只检查长度为1到6的字串即可.
另外,取a =01392,b =011,c =3可以将A 、B 组F 3(l )值分得较开,并可以用来处理未知数据.
方法三讨论 这种方法从序列的信息量(熵)入手,认为当序列中有大量的重复元素时,信息量就会比重复少的序列所含有的信息少.所以,其侧重点是是序列前后的重复性,也就是序列元素的相关性.从所给的A ,B 两类中可以很清楚地看到B 中序列重复量大,所含的信息明显少于A 组,而这个特征就被我们定义的熵函数凸显出来.将DNA 序列看成一个信息流的方法由于其在实际问题中的广泛背景,将会是一个很有价值的想法,统计学和信息论的一套非常成熟的强大工具也会在DNA 研究中发挥巨大的作用.
综合模型的建立
以上我们分别用三种方法得出了分类方案,这三种方案分别基于三种不同的方面对问题进行分析.第一种方法主要考虑的是单个字母出现的频率;第二种方法主要考虑每个字母的出现是否具有周期性;而第三种方法则考虑的是每条DNA 所蕴含的信息量.我们将这三种方法对A 、B 组自身进行了检验,都得到了较令人满意的结果,但因为每个模型都只突出考虑序列某一方面的特征,所以,总有一些不尽如人意的地方,于是,我们认为应该把三种方法综合起来考虑,使序列各方面的特征都能得到体现,以使分类更加科学.
下面就是我们将几种方法综合考虑得到最后结果.
以上我们用三种方法得到了三个目标函数:F 1(l ),F 2(l ),F 3(l ),这三个目标函数可以作为分类的判别标准.将它们看成定义在序列空间L ={l l 是由a ,g ,t ,c 四个字母组成的序列}上,作用于实轴上的函数.现在,我们必须找到一个函数F ,使得F 可以体现序列的各个特征.
由于F 1(l ),F 2(l ),F 3(l )的值域范围差别很大,为了有效的比较这三个函数,我们必须将它们归一化,将Νi =f i (l )(i =1,2,3,以下同)看成一定义在L 空间上的随机变量,A ,B 为L 的子集,则将f i 归一化得
3
21期汤诗杰等:DNA 序列的分类模型
g i=Νi-EΝi
V arΝi
(1)
而现有样本点f i(11),f i(12),……,f i(120)利用距估计方法估计得:
EΝi=1
n
∑n
j=1
f i(l i)
V arΝi=
1
n-1
∑n
j=1
(f i(l i)-ES i)2
代入(1)即得g i
现估计g i投射L的点到实轴上后,g i(A)和g i(B)的分界点x i,其中
g i(A)={g(a) a∈A}
g i(B)={g(b) b∈B}
以g1为例,A的10个样本点和B的10个样本点不能被一个分界点分开,有极大似然估计的思想,分界点应该把尽可能多的点分开,即
x i∈(-0.276758,0.482296)
由于g i(l)的分布未知,故只能假设其满足较均匀的分布,则A,B的分界点的最好估计
为E g i (A)+E g i(B)
2
,而E g i(A)+E g i(B)的矩估计为∑
20
i=1
g(l i)=0(由g的定义).恰好
0∈(-01276758,01482296),则x1=0是分界点的最佳估计.
同理,x2=0,x3=0分界是g2,g3对应分界点的最佳估计.
令F=a1g1+a2g2+a3g3,则其分界点为x=a1×0+a2×0+a3×0=0
由F的构造方法知,F作用到A样本上大于零,作用到B样本上小于零.我们确定适当的权值,以此作为A,B的分类法即可.根据不同的实际情况,可以相应调节这三个权值,以体现分类中的不同因素所在的比重.在下面的计算中,我们简单的取a1=1,a2=-1,a3= 015.得到的结果如表4,表5所示:
表4
序号目标函数值序号目标函数值序号目标函数值序号目标函数值
A 组
11.80288
21.75894
32.5887
40.27582
52.1781
A
组
61.75355
71.25115
81.41371
91.9011
101.97282
B
组
11-1.38528
12-1.22372
13-0.940004
14-0.93612
15-2.27465
B
组
16-2.60295
17-0.0165438
18-1.31022
19-2.6043
20-3.603
表5
序号目标函数值类别序号目标函数值类别
21-1.96454B31-1.06638B
220.873279A32-0.668504B
232.32887A33-0.877053B
24-1.48005B342.60904A
251.21328A351.69535A
26-1.184B361.22298A
271.22569A371.83991A
28-3.71616B38-3.01466B
292.69272A390.499763A
300.550393A40-2.77993B
42数 学 的 实 践 与 认 识31卷
由以上数据可以看出,我们构造的目标函数具有较好的区分度.对于A 组,目标函数值都大于零;而对B 组,目标函数值都小于零.也就是说,用这种方法,对A 、B 组样本的区分率已达到了100%.正如前面所说,这种方法综合了序列中的许多信息.因此,我们完全可以采用这个标准来区分C 组.表5是对C 组区分的结果.对20个未标明分类的人工序列的分类结果为:
A 类:22,23,25,27,29,30,34,35,36,37,39
B 类:21,24,26,28,31,32,33,38,40
同样的,我们利用这种方法对所给的182个自然序列进行了分类,结果如下所示(略).
5 模型的评价及推广
在我们的模型基础上提出的分类方法可以很好的验证已知的20个序列,并且很好的完成了对未知类型序列的分类.我们认为这种模型,同时考虑了序列中元素的局部性质和序列的全局性质,具有相当的实际背景.当我们知道分类标准的更多信息时,我们可以很方便的调整模型中的参数,使之符合新的情况,具有很好的自学习性.但这个模型比较复杂,在实际计算中参数选择需要花费大量计算时间进行搜索.
我们在模型中使用的基于信息流的方法中,如果选取更为合适的熵函数,一定可以使它更加符合实际情况;在三种方法综合的时候,所取的权值也是可以采用更为有效的方法选取,如应用层次分析法;还可以选取其他分类方法加入.这些都是本模型可以改进的地方.
参考文献:
[1] 姜启源.数学模型(第二版).高等教育出版社,19921[2] 刘郁强等1序列空间方法1广东科技出版社,19961[3] 刘祖洞1遗传学(第二版1高等教育出版社,19911
[4] 姜 丹,钱玉美1信息理论与编码1中国科学技术大学出版社,19921[5] 王玲玲等1常用统计方法1华东师范大学出版社,19941[6] 陆 璇1应用统计1清华大学出版社,19991
The Classif ied M odel for D NA Sequences
TAN G Sh i 2jie , ZHOU L iang , W AN G X iao 2ling
(U niversity of Science and T echno logy of Ch ina ,H efei 230026)
Abstract : C lassifying the DNA sequences is a p ractice p roblem in bi o logy .
In th is paper ,a
m athem atics model is established fo r the classifying of DNA sequences
.Since there are bo th locality and globality in the DNA sequences ,w e discuss the criteri on about w hether the classified m ethod is good o r no t .T hat is w hether the m ethod bases on all p roperties that the DNA sequences have .
So a classified m ethod w ith a single standard is no t enough fo r the p roblem .H ere is a synthesis m ethod on th ree different classified w ays
.T he th ree w ays base on varied p roperty that DNA sequences have .T he first is the frequency of occurrences of the elem ent in the DNA
5
21期汤诗杰等:DNA 序列的分类模型
sequences.T he second is the peri odic p roperty of the DNA sequences.T he th ird is that amount
of info r m ati on 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
generalizati on 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 ropagati on 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两类序列的统计特征,然后运用神经网络中的B P网络对未知序列进行了分类识别.
2 模型建立的理论依据
神经网络是近年来发展的一种大规模并行分布处理的非线性系统[1],其主要特点有:
1)能以任意精度逼近任意给定连续的非线性函数;
2)对复杂不确定问题具有自适应和自学习能力;
3)具有较强的容错能力和信息综合能力,能同时处理定量和定性的信息,能很好地协调多种输入信息的关系.
传统的分类识别方法,对于一般非线性系统的识别很困难,而神经网络却为此提供了一
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的中心为坐标原点建立三维直角坐
2000年全国大学生数学建模竞赛A题DNA序列分类 2000年6月，人类基因组计划中DNA全序列草图完成，预计2001年可以完成精确的全序列图，此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的“天书”。这本大自然写成的“天书”是由4个字符A，T，C，G按一定顺序排成的长约30亿的序列，其中没有“断句”也没有标点符号，除了这4个字符表示4种碱基以外，人们对它包含的“内容”知之甚少，难以读懂。破译这部世界上最巨量信息的“天书”是二十一世纪最重要的任务之一。在这个目标中，研究DNA全序列具有什么结构，由这4个字符排成的看似随机的序列中隐藏着什么规律，又是解读这部天书的基础，是生物信息学（Bioinformatics）最重要的课题之一。 虽然人类对这部“天书”知之甚少，但也发现了DNA序列中的一些规律性和结构。例如，在全序列中有一些是用于编码蛋白质的序列片段，即由这4个字符组成的64种不同的3 字符串，其中大多数用于编码构成蛋白质的20种氨基酸。又例如，在不用于编码蛋白质的序列片段中，A和T的含量特别多些，于是以某些碱基特别丰富作为特征去研究DNA序列的结构也取得了一些结果。此外，利用统计的方法还发现序列的某些片段之间具有相关性，等等。这些发现让人们相信，DNA序列中存在着局部的和全局性的结构，充分发掘序列的结构对理解DNA全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某些细节，突出特征，然后将其表示成适当的数学对象。这种被称为粗粒化和模型化的方法往往有助于研究规律性和结构。 作为研究DNA序列的结构的尝试，提出以下对序列集合进行分类的问题： 1）下面有20个已知类别的人工制造的序列（见下页），其中序列标号1—10 为A类，1 1-20为B类。请从中提取特征，构造分类方法，并用这些已知类别的序列，衡量你的方法是否足够好。然后用你认为满意的方法，对另外20个未标明类别的人工序列（标号21—4 0）进行分类，把结果用序号（按从小到大的顺序）标明它们的类别（无法分类的不写入）： A类__________ ；B类_______________ 。 请详细描述你的方法，给出计算程序。如果你部分地使用了现成的分类方法，也要将方法名称准确注明。 这40个序列也放在如下地址的网页上，用数据文件Art-model-data 标识，供下载： 网易网址：https://www.doczj.com/doc/423302736.html, 教育频道在线试题； 教育网： https://www.doczj.com/doc/423302736.html, New mcm2000 教育网： https://www.doczj.com/doc/423302736.html,/mcm 2）在同样网址的数据文件Nat-model-data 中给出了182个自然DNA序列，它们都较长。用你的分类方法对它们进行分类，像1）一样地给出分类结果。 提示：衡量分类方法优劣的标准是分类的正确率，构造分类方法有许多途径，例如提取序列
DNA序列分类模型DNA序列分类模型
毕业设计（论文）原创性声明和使用授权说明 原创性声明 本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。 作者签名：日期： 指导教师签名：日期： 使用授权说明 本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。 作者签名：日期：
学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 涉密论文按学校规定处理。 作者签名：日期：年月日 导师签名：日期：年月日
收稿日期:2002203210 作者简介:刘志(1965— )男,山东东平人,空军工程大学工程师文章编号:100123857(2002)Sup.20114203 D NA 序列的一种分类方法 刘 志 (空军工程大学导弹学院,陕西西安713800) 摘 要:基于小波变换和相关技术,提出了一种DNA 序列的分类方法.首先将DNA 序列转换成数字序列,然后对此序列进行Matlab 快速分解,计算未知类别序列与已知类别序列的相关系数,由此判定序列的类别.结果表明,该方法是切实可行的. 关键词:DNA 序列;相关技术;小波变换 中图分类号:O357 文献标识码:A 2000年6月,人类基因组计划中DNA 全部草图完成,预计2002年可以完成精确的全序列图,此后人类将拥有一本记录着自己生老病死及遗传进化的全部信息的“天书”.这本大自然写成的“天书”是由4个字符A ,T ,C ,G 按一定的顺序排成的长约30亿的序列,其中没有“断句”也没有“标点符号”,除了这4个字符表示4种碱基以外,人们对它包含的“内容”知之甚少,难以读懂.破译这部世界上最巨量信息的天书是21世纪最重要的任务之一.虽然人类对这部天书知之甚少,但也发现了DNA 序列中的一些规律和结构.例如,在全序列中有一些是用于,即由这4个字符组成的64种不同的3字符串,其中大多数用于编码构成蛋白质的20种氨基酸.此外,利用统计的方法还发现序列的某些片段之间具有相关性,等等.本文利用小波变换和相关技术,提出了一种DNA 序列的分类方法. 1 Matlab 快速算法 信号的小波分析相当于对信号加上一个可调的时—频窗.Matlab 根据多分辨分析的观点,利用共轭正交镜像滤波器,给出了离散小波变换的金字塔算法,使信号快速分解和重构得以实现.在Matlab 算法基础上,进一步对高频信号进行分解,将信号分解到不同的频带上,滤波时根据需要,选取所需频带内的信号进行重构,就可以完成信号的多通带滤波.小波变换不改变信号所引起的小波变换系数的极值点的位置,而噪声所引起的小波变换系数的极值点主要表现在第一、二尺度上,且随着尺度增大,小波系数的极值点越来越少.由第三级小波变换系数重构的信号的自相关函数的极大值的位置和原函数的自相关函数的极大值的位置完全相同,这是本文所提方案的依据.由第三级小波变换系数重构的信号的自相关函数图形比较光滑,而且,没有影响自相关函数的极大值的位置.此结论对信号检测非常有用. 根据多分辨分析理论,在二进正交小波基下,Matlab 快速算法[1]为 A k j f =∑n ∈Z h (n -2k )A n j -1f , j =1,2,…,J .第30卷 专 辑 陕西师范大学学报(自然科学版)Vol.30 Sup. 2002年5月Journal of Shaanxi Normal University (Natural Science Edition )May.2002
基因识别问题及其算法实现 一、背景介绍 DNA 是生物遗传信息的载体，其化学名称为脱氧核糖核酸（Deoxyribonucleic acid ，缩写为DNA ）。DNA 分子是一种长链聚合物，DNA 序列由腺嘌呤（Adenine, A ），鸟嘌呤（Guanine, G ），胞嘧啶（Cytosine, C ），胸腺嘧啶（Thymine, T ）这四种核苷酸（nucleotide ）符号按一定的顺序连接而成。其中带有遗传讯息的DNA 片段称为基因（Gene ）（见图1第一行）。其他的DNA 序列片段，有些直接以自身构造发挥作用，有些则参与调控遗传讯息的表现。 在真核生物的DNA 序列中，基因通常被划分为许多间隔的片段（见图1第二行），其中编码蛋白质的部分，即编码序列（Coding Sequence ）片段，称为外显子（Exon ），不编码的部分称为内含子（Intron ）。外显子在DNA 序列剪接（Splicing ）后仍然会被保存下来，并可在 图1真核生物DNA 序列（基因序列）结构示意图 蛋白质合成过程中被转录（transcription ）、复制（replication ）而合成为蛋白质（见图2）。DNA 序列通过遗传编码来储存信息，指导蛋白质的合成，把遗传信息准确无误地传递到蛋白质（protein ）上去并实现各种生命功能。 DNA 序列 外显子(Exon ) 内含子(Intron)
DNA序列 剪接、转录、复制 蛋白质序列 图2蛋白质结构示意图 对大量、复杂的基因序列的分析，传统生物学解决问题的方式是基于分子实验的方法，其代价高昂。诺贝尔奖获得者W.吉尔伯特（Walter Gilbert，1932—；【美】，第一个制备出混合脱氧核糖核酸的科学家）1991年曾经指出：“现在，基于全部基因序列都将知晓，并以电子可操作的方式驻留在数据库中，新的生物学研究模式的出发点应是理论的。一个科学家将从理论推测出发，然后再回到实验中去，追踪或验证这些理论假设。” 随着世界人类基因组工程计划的顺利完成，通过物理或数学的方法从大量的DNA序列中获取丰富的生物信息，对生物学、医学、药学等诸多方面都具有重要的理论意义和实际价值，也是目前生物信息学领域的一个研究热点。 二、数字序列映射与频谱3-周期性： 对给定的DNA序列，怎么去识别出其中的编码序列（即外显子），也称为基因预测，是一个尚未完全解决的问题，也是当前生物信息学的一个最基础、最首要的问题。 基因预测问题的一类方法是基于统计学的[1]。很多国际生物数据网站上也有“基因识别”的算法。比如知名的数据网站https://www.doczj.com/doc/423302736.html,/GENSCAN.html提供的基因识别软件GENSCAN（由斯坦福大学研究人员研发的、可免费使用的基因预测软件）,主要就是基于隐马尔科夫链（HMM）方法。但是，它预测人的基因组中有45000个基因，相当于现在普遍认可数目的两倍。另外，统计预测方法通常需要将编码序列信息已知的DNA序列作为训练数据
数理学院专业实践报告题目： 专业 学生姓名 班级学号 指导教师(签字) 指导教师职称 实习单位 负责人签字 日期
1．2000 年6月，人类基因组计划中DNA 全序列草图完成，预计2001 年可以完成精确的全序列图，此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的“天书”。这本大自然写成的“天书”是由4 个字符A，T，C，G 按一定顺序排成的长约30 亿的序列，其中没有“断句”也没有标点符号，除了这4 个字符表示4 种碱基以外，人们对它包含的“内容”知之甚少，难以读懂。破译这部世界上最巨量信息的“天书”是二十一世纪最重要的任务之一。在这个目标中，研究DNA 全序列具有什么结构，由这4 个字符排成的看似随机的序列中隐藏着什么规律，又是解读这部天书的基础，是生物信息学（Bioinformatics）最重要的课题之一。虽然人类对这部“天书”知之甚少，但也发现了DNA 序列中的一些规律性和结构。例如，在全序列中有一些是用于编码蛋白质的序列片段，即由这4 个字符组成的64 种不同的3 字符串，其中大多数用于编码构成蛋白质的20 种氨基酸。又例如，在不用于编码蛋白质的序列片段中，A 和T 的含量特别多些，于是以某些碱基特别丰富作为特征去研究DNA 序列的结构也取得了 一些结果。此外，利用统计的方法还发现序列的某些片段之间具有相关性，等等。这些发现让人们相信，DNA 序列中存在着局部的和全局性的结构，充分发掘序列的结构对理解DNA 全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某些细节，突出特征，然后将其表示成适当的数学对象。这种被称为粗粒化和模型化的方法往往有助于研究规律性和结构。作为研究 DNA 序列的结构的尝试，提出以下对序列集合进行分类的问题：
DNA序列分类模型 陈荣生张海军张旭东指导教师：数模组 海军航空工程学院 摘要本文讨论了在给定A类和B类各10个DNA序列的情况下，如何找出判断DNA 序列类型的方法，并具体分析了DNA序列的局部特征，最后将总体特征与局部特征综合考虑。 文中我们先根据给出的已知类型的20组DNA序列，考虑了四个碱基及其组合形式出现的频率，以此为研究对象进行深入研究，并建立了两个数学模型，即信息熵模型和Z曲线模型，最后还给出了模型的改进方向。 本文采取的用Z曲线来研究DNA序列的方法很有意义。 一、问题的重述 2000年6月，人类基因组计划中DNA全序列草图完成，预计2001年可以完成精确的全序列图，DNA全序列是由4个字符A，T，C，G按一定顺序排成的长约30亿的序列，其中没有“断句”也没有标点符号。人们发现了DNA序列中的一些规律性和结构。例如，在全序列中有一些是用于编码蛋白质的序列片段，即由这4个字符组成的64种不同的3字符串，其中大多数用于编码构成蛋白质的20种氨基酸。又例如，在不用于编码蛋白质的序列片段中，A 和T的含量特别多些，于是以某些碱基特别丰富作为特征去研究DNA序列的结构也取得了一些结果。此外，利用统计的方法还发现序列的某些片段之间具有相关性，等等。这些发现让人们相信，DNA序列中存在着局部的和全局性的结构，充分发掘序列的结构对理解DNA全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某些细节，突出特征，然后将其表示成适当的数学对象。这种被称为粗粒化和模型化的方法往往有助于研究规律性和结构。 作为研究DNA序列的结构的尝试，提出以下对序列集合进行分类的问题： 1）下面有20个已知类别的人工制造的序列，其中序列标号1—10 为A类，11-20为B 类。请从中提取特征，构造分类方法，并用这些已知类别的序列，衡量你的方法是否足够好。然后用你认为满意的方法，对另外20个未标明类别的人工序列（标号21—40）进行分类，把结果用序号（按从小到大的顺序）标明它们的类别（无法分类的不写入）： A类； B类。 请详细描述你的方法，给出计算程序。如果你部分地使用了现成的分类方法，也要将方法名称准确注明。 2），用你的分类方法对182个自然DNA序列进行分类，像1）一样地给出分类结果。二、问题的分析 为了找出分类方法，我们可以省略细节，突出特征，以某 种碱基出现的频率或以两种甚至三种碱基的组合出现的频率， 或者以几种碱基出现的频率之和为依据来考虑。现分别就A、 B两组DNA序列针对以下20个方面做一些简单分析： 1)A出现的频率； 2)C出现的频率； 3)G出现的频率； 4)T出现的频率；
DNA序列分类 2000年6月，人类基因组计划中DNA全序列草图完成，预计2001年可以完成精确的全序列图，此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的“天书”。这本大自然写成的“天书”是由4个字符A，T，C，G按一定顺序排成的长约30亿的序列，其中没有“断句”也没有标点符号，除了这4个字符表示4种碱基以外，人们对它包含的“内容”知之甚少，难以读懂。破译这部世界上最巨量信息的“天书”是二十一世纪最重要的任务之一。在这个目标中，研究DNA全序列具有什么结构，由这4个字符排成的看似随机的序列中隐藏着什么规律，又是解读这部天书的基础，是生物信息学（Bioinformatics）最重要的课题之一。 虽然人类对这部“天书”知之甚少，但也发现了DNA序列中的一些规律性和结构。例如，在全序列中有一些是用于编码蛋白质的序列片段，即由这4个字符组成的64种不同的3字符串，其中大多数用于编码构成蛋白质的20种氨基酸。又例如，在不用于编码蛋白质的序列片段中，A和T的含量特别多些，于是以某些碱基特别丰富作为特征去研究DNA序列的结构也取得了一些结果。此外，利用统计的方法还发现序列的某些片段之间具有相关性，等等。这些发现让人们相信，DNA序列中存在着局部的和全局性的结构，充分发掘序列的结构对理解DNA全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某些细节，突出特征，然后将其表示成适当的数学对象。这种被称为粗粒化和模型化的方法往往有助于研究规律性和结构。 作为研究DNA序列的结构的尝试，提出以下对序列集合进行分类的问题： 1）下面有20个已知类别的人工制造的序列（见下页），其中序列标号1—10 为A类，11-20为B类。请从中提取特征，构造分类方法，并用这些已知类别的序列，衡量你的方法是否足够好。然后用你认为满意的方法，对另外20个未标明类别的人工序列（标号21—40）进行分类，把结果用序号（按从小到大的顺序）标明它们的类别（无法分类的不写入）：A类；B类。 请详细描述你的方法，给出计算程序。如果你部分地使用了现成的分类方法，也要将方法名称准确注明。 2）在同样网址的数据文件Nat-model-data 中给出了182个自然DNA序列，它们都较长。用你的分类方法对它们进行分类，像1）一样地给出分类结果。 提示：衡量分类方法优劣的标准是分类的正确率，构造分类方法有许多途径，例如提取序列的某些特征，给出它们的数学表示：几何空间或向量空间的元素等，然后再选择或构造适合这种数学表示的分类方法；又例如构造概率统计模型，然后用统计方法分类等。 Art-model-data 1.aggcacggaaaaacgggaataacggaggaggacttggcacggcattacacggaggacgaggtaaaggaggcttgtctacggc cggaagtgaagggggatatgaccgcttgg 2.cggaggacaaacgggatggcggtattggaggtggcggactgttcggggaattattcggtttaaacgggacaaggaaggcggctg gaacaaccggacggtggcagcaaagga 3.gggacggatacggattctggccacggacggaaaggaggacacggcggacatacacggcggcaacggacggaacggaggaa ggagggcggcaatcggtacggaggcggcgga 4.atggataacggaaacaaaccagacaaacttcggtagaaatacagaagcttagatgcatatgttttttaaataaaatttgtattattatggt atcataaaaaaaggttgcga 5.cggctggcggacaacggactggcggattccaaaaacggaggaggcggacggaggctacaccaccgtttcggcggaaaggcg gagggctggcaggaggctcattacggggag 6.atggaaaattttcggaaaggcggcaggcaggaggcaaaggcggaaaggaaggaaacggcggatatttcggaagtggatattag gagggcggaataaaggaacggcggcaca
历年全国数学建模试题及解法归纳 赛题解法 93A非线性交调的频率设计拟合、规划 93B足球队排名图论、层次分析、整数规划94A逢山开路图论、插值、动态规划 94B锁具装箱问题图论、组合数学 95A飞行管理问题非线性规划、线性规划 95B天车与冶炼炉的作业调度动态规划、排队论、图论96A最优捕鱼策略微分方程、优化 96B节水洗衣机非线性规划 97A零件的参数设计非线性规划 97B截断切割的最优排列随机模拟、图论 98A一类投资组合问题多目标优化、非线性规划98B灾情巡视的最佳路线图论、组合优化 99A自动化车床管理随机优化、计算机模拟 99B钻井布局0-1规划、图论 00A DNA序列分类模式识别、Fisher判别、人工 神经网络 00B钢管订购和运输组合优化、运输问题 01A血管三维重建曲线拟合、曲面重建
赛题解法 01B 公交车调度问题多目标规划 02A车灯线光源的优化非线性规划 02B彩票问题单目标决策 03A SARS的传播微分方程、差分方程 03B 露天矿生产的车辆安排整数规划、运输问题 04A奥运会临时超市网点设计统计分析、数据处理、优化04B电力市场的输电阻塞管理数据拟合、优化 05A长江水质的评价和预测预测评价、数据处理 05B DVD在线租赁随机规划、整数规划 06A出版社书号问题整数规划、数据处理、优化06B Hiv病毒问题线性规划、回归分析 07A 人口问题微分方程、数据处理、优化07B 公交车问题多目标规划、动态规划、图 论、0-1规划 08A 照相机问题非线性方程组、优化 08B 大学学费问题数据收集和处理、统计分 析、回归分析 2009年A题制动器试验台的控制方法分析工程控制 2009年B题眼科病床的合理安排排队论，优化，仿真，综 合评价 2009年C题卫星监控几何问题，搜集数据
关于DNA序列分类问题的模型 冯涛;康吉;吉雯;韩小军;贺明峰 【期刊名称】《数学的实践与认识》 【年(卷),期】2001(031)001 【摘要】This paper presents a method applying artificial neural network (NN) to DNA clustering problem. First we use the probability statistics method to extract the characters from the 20 artificial DNA sequences whose categories are known. Thus we can get the character vectors of the DNA sequences and input them as samples into BP neuron NN for learning. Weemploy the BP (back propagation) algorithm to train NN by use of the Neural Network Toolbox in MATLAB software package. In this paper, two three-story NN are created to input the extracted DNA character vectors as samples into them. After the training, characters are extracted from the 20 unclassified artificial sequence samples and 182 natural sequence samples to form the character vectors as input of the two NN for clustering. The results shows: the clustering method presented in this paper can classify the DNA sequences in quite high accuracy and precision. It is quite feasible to apply the artificial neural network to DNA sequence clustering.%本文提出了一种将人工神经元网络用于DNA分类的方法. 作者首先应用概率统计的方法对20个已知类别的人工DNA序列进行特征提取，形成DNA序列的特征向量，并将之作为样本输入BP神经网络进行学习. 作者应用了MATLAB软件包中的Neural Network
ＤＮＡ序列的分类与判别分析 摘要: 本文对DNA 序列分类问题进行了讨论.。从“不同序列中碱基含量不同”入手,建立了欧氏距离判别模型、马氏距离判别模型以及Fisher准则判定模型。接着,本文对三种分类算法进行了对比, 对算法的稳定性进行了讨论。 关键词:DNA分类;欧氏距离;马氏距离;Fisher判别; DNA sequence classification and discriminant analysis MA Fuyu School of Management and Economics, China University of Geosciences, P.R.China, 430074 Abstract: In this paper, the classification of DNA sequences are discussed. From the “content of different base sequence in a different” approach, the establishment of a discriminant model of Euclidean distance, Mahalanobis distance, as well as Fisher discriminant model to determine the model guidelines. Then, this paper three classification algorithms were compared, the stability of the algorithm are discussed. Keywords: DNA taxonomy; Euclidean distance; Mahalanobis distance; Fisher Discriminant 1、问题的重述 2000年6月,人类基因组计划中DNA全序列草图完成,预计2001年可以完成精确的全序列图,此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的“天书”。这本大自然写成的“天书”是由4个字符A,T,C,G按一定顺序排成的长约30亿的序列,其中没有“断句”也没有标点符号,除了这4个字符表示4种碱基以外,人们对它包含的“内容”知之甚少,难以读懂。破译这部世界上最巨量信息的“天书”是二十一世纪最重要的任务之一。在这个目标中,研究DNA全序列具有什么结构,由这4个字符排成的看似随机的序列中隐藏着什么规律,又是解读这部天书的基础,是生物信息学(Bioinformatics)最重要的课题之一。 虽然人类对这部“天书”知之甚少,但也发现了DNA序列中的一些规律性和结构。例如,在全序列中有一些是用于编码蛋白质的序列片段,即由这4个字符组成的64种不同的3字符串,其中大多数用于编码构成蛋白质的20种氨基酸。又例如,在不用于编码蛋白质的序列片段中,A和T的含量特别多些,于是以某些碱基特别丰富作为特征去研究DNA序列的结构也取得了一些结果。此外,利用统计的方法还发现序列的某些片段之间具有相关性,等等。这些发现让人们相信,DNA序列中存在着局部的和全局性的结构,充分发掘序列的结构对理解DNA全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某些细节,突出特征,然后将其表示成适当的数学对象。这种被称为粗粒化和模型化的方法往往有助于
DNA序列分类
实验目的 学习利用MATLAB提取DNA序列特征建立向量的方法，掌握利用FCM命令进行DNA 分类的方法，学会做出分类图形直接给出分类结果的MATLAB编程。 知识扩展 DNA序列分类 DNA(Deoxyribonucleic acid)，中文译名为脱氧核苷酸，是染色体的主要化学成分，同时也是基因组成的，有时被称为“遗传微粒”。DNA是一种分子，可组成遗传指令，以引导生物发育与生命机能运作。主要功能是长期性的资讯储存，可比喻为“蓝图”或“食谱”。DNA分子是由两条核苷酸链以互补配对原则所构成的双螺旋结构的分子化合物。其中两条DNA链中对应的碱基A-T以双键形式连接，C-G以三键形式连接，糖-磷酸-糖形成的主链在螺旋外侧，配对碱基在螺旋内侧。 FCM算法中样本点隶属于某一类的程度是用隶属度来反映的，不同的样本点以不同的隶属度属于每一类；但是算法中的概率约束∑uij=1使得样本的典型性反映
不出来，不适用于有噪音，样本分布不均衡，存在两个或者两个以上样本分别距两个类的距离相等的样本等等。 欧氏距离（ Euclidean distance）也称欧几里得距离，它是一个通常采用的距离定义，它是在m维空间中两个点之间的真实距离。 公式 在二维和三维空间中的欧式距离的就是两点之间的距离，二维的公式是 d = sqrt((x1-x2)^+(y1-y2)^) 三维的公式是 d=sqrt(x1-x2)^+(y1-y2)^+(z1-z2)^) 推广到n维空间，欧式距离的公式是 d=sqrt( ∑(xi1-xi2)^ ) 这里i=1,2..n xi1表示第一个点的第i维坐标,xi2表示第二个点的第i维坐标 n维欧氏空间是一个点集,它的每个点可以表示为(x(1),x(2),...x(n)),其中x(i)(i=1,2...n)是实数,称为x的第i个坐标,两个点x和y=(y(1),y(2)...y(n))之间的距离d(x,y)定义为上面的公式. 欧氏距离判别准则如下： 若dA
题目 DNA 序列 摘要 本文主要研究DNA 序列的结构问题，通过建立相应的数学模型，对DNA 序列中所隐藏的规律进行研究和分析，给出了解决问题的最优方案，并且对模型进行了评价和推广。 对于问题一，为了挖掘DNA 序列的特征将其分为A 类和B 类，以20种基本氨基酸为目标，利用Matlab 软件编程得出每一行每一种氨基酸出现的概率；再运用主成分分析法进行降维，利用SPSS 软件进行数据处理得到矩阵；然后再将模糊聚类问题转化为如下优化问题： 211 1 min (,)(()) ..1(1,2, 6) 01 n c q ik ik k i c ik i ik J U V u d s t u k u ======≤≤∑∑∑ 用模糊聚类分析方法来获取样本与聚类中心的加权距离最小的最佳分类，使其分 题一相同的方法进行分类，分类结果见问题二的求解。 总的来说，本模型在未知数据特征的情况下很好的将数据进行分类，成功地解决了此次数学建模的DNA 序列问题，是聚类分析问题的一个有效而且具有较强实用性的方法。 关键词：主成分分析 模糊聚类分析 Matlab 软件 Spss 软件
一、问题重述 1.1背景分析 随着DNA测序时代的到来，越来越多生物的全基因组序列正逐渐展现于人们的眼前。如何从中挖掘有用的信息成为对当今生物学乃至整个科学领域的一个挑战。本文主要致力于对DNA序列结构以及序列中所隐藏规律的研究。 1.2问题重述 2000年6月，人类基因组计划中DNA全序列草图完成，预计2001年可以完成精确的全序列图，此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的“天书”。这本大自然写成的“天书”是由4个字符A，T，C，G按一定顺序排成的长约30亿的序列，其中没有“断句”也没有标点符号，除了这4个字符表示4种碱基以外，人们对它包含的“内容”知之甚少，难以读懂。破译这部世界上最巨量信息的“天书”是二十一世纪最重要的任务之一。在这个目标中，研究DNA全序列具有什么结构，由这4个字符排成的看似随机的序列中隐藏着什么规律，又是解读这部天书的基础，是生物信息学（Bioinformatics）最重要的课题之一。 虽然人类对这部“天书”知之甚少，但也发现了DNA序列中的一些规律性和结构。例如，在全序列中有一些是用于编码蛋白质的序列片段，即由这4个字符组成的64种不同的3字符串，其中大多数用于编码构成蛋白质的20种氨基酸。又例如，在不用于编码蛋白质的序列片段中，A和T的含量特别多些，于是以某些碱基特别丰富作为特征去研究DNA序列的结构也取得了一些结果。此外，利用统计的方法还发现序列的某些片段之间具有相关性，等等。这些发现让人们相信，DNA序列中存在着局部的和全局性的结构，充分发掘序列的结构对理解DNA全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某些细节，突出特征，然后将其表示成适当的数学对象。这种被称为粗粒化和模型化的方法往往有助于研究规律性和结构。 作为研究DNA序列的结构的尝试，提出以下对序列集合进行分类的问题：问题一：下面有20个已知类别的人工制造的序列（见附录），其中序列标号1—10 为A类，11-20为B类。请从中提取特征，构造分类方法，并用这些已知类别的序列，衡量你的方法是否足够好。然后用你认为满意的方法，对另外20个未标明类别的人工序列（标号21—40）进行分类，把结果用序号（按从小到大的顺序）标明它们的类别（无法分类的不写入）： A类； B类。 请详细描述你的方法，给出计算程序。如果你部分地使用了现成的分类方法，也要将方法名称准确注明。
第31卷第1期2001年1月 数学的实践与认识 M A TH EM A T I CS I N PRA CT I CE AND TH EO R Y V o l131 N o11 Jan.2001 D NA序列的分类模型 汤诗杰, 周 亮, 王晓玲 指导老师: 孙广中 (中国科技大学,合肥 230026) 编者按: 本文提出了DNA序列分类的三种模型,其一,基于A、G、T、C四种碱基出现的频率;其二利用了 同一碱基在序列中的间隔,这一信息是单纯考虑频率所不能包含的;在第三种模型中,作者把DNA序列视 为一个信息流,考虑每增加一个字符所带来的信息增量.尽管文中信息量的定义方式仍可讨论,但本文思想新颖活跃,有其独特之处.本文最后的分类方法,是以上三种的综合使用. 摘要: 本文针对DNA序列分类这个实际问题,提出了相应的数学模型.为了很好的体现DNA序列的局 部性和全局性的特征,我们给出了衡量分类方法优劣的标准,即在满足一定限制条件的情况下,是否能充分反映序列的各方面特性. 依据我们提出的判别标准,单一标准的分类是无法满足要求的.我们的方法是侧重点不同的三种方法的综合集成.这三种方法分别体现了序列中元素出现的概率,序列中元素出现的周期性,序列所带有的信息含量.利用这个方法,完成了对未知类型的人工序列及自然序列的分类工作.最后,对分类模型的优缺点进行了分析,并就模型的推广作了讨论. 1 问题的提出(略) 2 问题的分析 这是一个比较典型的分类问题,为了表述的严格和方便,我们用数学的方法来重述这个问题.已知字母序列S1,S2,S3……S40,S i=x1x2x3…x n i,其中x j∈{a,t,c,g};有字符序列集合A,B,满足A∩B=<,并当1ΦiΦ10时,S i∈A;当11ΦiΦ20时,S i∈B.现要求考虑当21ΦiΦ40时,S i与集合A及集合B的关系. 在这里,问题的关键就是要从已知的分好类的20个字母序列中提取用于分类的特征.知道了这些特征,我们就可以比较容易的对那些未标明类型的序列进行分类.下面我们将首先对用于分类的标准问题进行必要的讨论. 3 分类的标准及评价 首先,我们提取的特征应该满足以下两个条件: (1)所取特征必须可以标志A组和B组.也就是说,我们利用这些特征应该可以很好的区分已经标示分类的20个序列.这是比较显然的一个理由. (2)所取特征必须是有一定的实际意义的.这一点是决不能被忽视的.比如,如果不考虑模型的实际意义,我们就可以以序列的开头字母为分类标准:已知在B类中的十个序列都是以g t开始的,而已知在A类中10个序列没有以g t开始的,甚至以g开始的都没有.显然这是满足上面的第一个条件的.如果仅因此就认为这种特征是主要的,并简单的利用这个特征将所有待分类的序列分成两类,显然是不甚合理的.
2015年芜湖三校数学建模竞赛 题目 DNA序列问题模型 摘要 DNA 序列是由A，T，G，C 四个表示4 种碱基的字符组成的序列。本文研究DNA 序列的结构找出序列间的差异和对八个物种的DNA序列进行分类。 对于问题一首先对数据运用数理统计方法对数据进行计算，得到八个物种的DNA序列的碱基的丰度、碱基的重复出现情况、碱基之间的相邻情况、不同碱 基的丰度之比的四个特征，通过对这四个特征作出相应的散点图比较得出八个物种的DNA序列间的差异：Human 、Opossum、 Lemur 、Rat等4种DNA序列的长度相同，其他四种DNA序列的长度各不相同，每种DNA序列四种碱基的的 重复情况也各不相同；G碱基的丰度相对于本序列的其他碱基的丰度都要高，碱基A的丰度在各个序列中丰度差不多，其他三种碱基在序列中波动性较大，差异性较大；8种DNA序列中GG、GT的相邻的状况比较明显；各个DNA序列中碱基 丰度比 f、GT f、CT f含量差不多且都含量比较高；其中，DNA序列中TA f、CA f、 GC f含量差不多且都含量比较低。 GA 对于问题二我们首先通过对问题一散点图的分析选取以碱基的丰度和碱基间的丰度之比为分类的指标，构建为分类的特征向量，但这些特征向量之间存在着一定的相关性，我们运用R型聚类选择出相关性程度差的特征向量为Q型聚类的指标。通过Q型聚类我们将这8种DNA序列分为3种分类方式，通过利用means方法，检验各类别在所有变量上的差异，再利用单因素方差分析最终确定将8种DNA序列分为四类。分类结果如下： 第一类：Human 、Mouse； 第二类：Goat、Rabbit； 第三类：Opossum、 Lemur 、Rat ； 第四类：Gallus。 关键词：数理统计；R型聚类；Q型聚类；means法；单因素方差分析法 1 问题重述 DNA 序列是由A，T，G，C 四个表示4 种碱基的字符组成的序列。研究DNA 序列的结构及序列中隐藏的规律，成为生物信息学的重要研究课题。根据表 1 中八个物种的β-球蛋白基因的第一个外显子序列，请解决以下问题： 1.建立数学模型刻画序列间的差异； 2. 对表1中八个物种的DNA序列进行分类。 2 基本假设
华北科技学院 课程设计说明书 班级: 姓名: 学号：成绩：______ 设计题目: DNA序列分类模型 设计时间: 2013.7.8 至2013.7.12 指导教师: 评语:______________________________________ _______________________________________________ _______________________________________________ _______________________________________________ _______________________________________________ 评阅教师: _______________
目录 目录................................................................................................................................. I [摘要] ............................................................................................................................ II 一、问题重述 (1) 二、模型假设 (1) 三、特定符号的说明 (1) 四、模型的分析 (2) 1、针对题目给出A、B类DNA单链分子的特征提取 (2) 2. 将样品分为两类： (3) 五、模型的建立和求解 (4) 1. 模型一：欧式距离分类模型的建立和求解 (5) 2. 模型二：在距离判别分析时经常应用马氏距离 (5) 3. 模型三：运用贝叶斯判别法进行判别 (6) 六、模型的误差分析和检验 (7) 1.误差分析： (7) 2.检验： (7) 七、模型的改进与推广 (7) 1.模型的优缺点： (8) （1）优点： (8) （2）缺点： (8) 2.模型的推广： (8) 八、参考文献 (9) 九、附录 (10) 1.C++程序源码： (10) 2.Matlab程序源码 (12)
2000 年赛题 A 题 DNA 序列分类 2000 年6 月，人类基因组计划中DNA 全序列草图完成，预计2001 年可以完成精确的全序列图，此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的“天书”。这本大自然写成的“天书”是由4 个字符A，T，C，G 按一定顺序排成的长约30 亿的序列，其中没有“断句”也没有标点符号，除了这4 个字符表示4 种碱基以外，人们对它包含的“内容”知之甚少，难以读懂。破译这部世界上最巨量信息的“天书”是二十一世纪最重要的任务之一。在这个目标中，研究DNA 全序列具有什么结构，由这4 个字符排成的看似随机的序列中隐藏着什么规律，又是解读这部天书的基础，是生物信息学（Bioinformatics）最重要的课题之一。虽然人类对这部“天书”知之甚少，但也发现了DNA 序列中的一些规律性和结构。例如，在全序列中有一些是用于编码蛋白质的序列片段，即由这4 个字符组成的64 种不同的3 字符串，其中大多数用于编码构成蛋白质的20 种氨基酸。又例如，在不用于编码蛋白质的序列片段中，A和T 的含量特别多些，于是以某些碱基特别丰富作为特征去研究DNA 序列的结构也取得了一些结果。此外，利用统计的方法还发现序列的某些片段之间具有相关性，等等。这些发现让人们相信，DNA 序列中存在着局部的和全局性的结构，充分发掘序列的结构对理解DNA 全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某些细节，突出特征，然后将其表示成适当的数学对象。这种被称为粗粒化和模型化的方法往往有助于研究规律性和结构。 作为研究DNA 序列的结构的尝试，提出以下对序列集合进行分类的问题： 1）下面有20 个已知类别的人工制造的序列，其中序列标号1—10 为A 类，11-20 为B 类。请从中提取特征，构造分类方法，并用这些已知类别的序列，衡量你的方法是否足够好。然后用你认为满意的方法，对另外20 个未标明类别的人工序列（标号21—40）进行分类，把结果用序号（按从小到大的顺序）标明它们的类别（无法分类的不写入）： A 类； B 类。 请详细描述你的方法，给出计算程序。如果你部分地使用了现成的分类方法，也要将方法名称准确注明。 这40 个序列放在如下地址的网页上，用数据文件Art-model-data 标识，供下载： 网易网址：https://www.doczj.com/doc/423302736.html, 教育频道在线试题； 教育网：https://www.doczj.com/doc/423302736.html, News mcm2000 教育网： https://www.doczj.com/doc/423302736.html,/mcm [注] 目前这些网站上不一定还保存有该文件，这里将该文件的内容附于本题后。 2）在同样网址的数据文件Nat-model-data 中给出了182 个自然DNA 序列，它们都较长。用你的分类方法对它们进行分类，像1）一样地给出分类结果。 提示：衡量分类方法优劣的标准是分类的正确率，构造分类方法有许多途径，例如提取序列的某些特征，给出它们的数学表示：几何空间或向量空间的元素等，然后再选择或构造适合这 种数学表示的分类方法；又例如构造概率统计模型，然后用统计方法分类等。 （北京工业大学孟大志提供） [附]数据文件Art-model-data 的内容如下： 附录1：已知类别的序列（用于提取特征及检验方法） A 类10 个序列： >aggcacggaaaaacgggaataacggaggaggacttggcacggcattacacggaggacgaggtaaaggaggcttgtctac ggccggaagtgaagggggatatgaccgcttggaattgtctg