DNA序列分类

作者：陈杰，刘予杰，叶本利 指导老师：汪泗水 王振羽 队号：15

摘要

本文对DNA序列分类问题进行了讨论。

首先，通过对20个已知类别的人工制造的序列进行特征提取，我们提出了几种不同分类方法，并分别建立了数学模型，用C程序、Matlab程序实现。

然后，我们将那20个已知类别的序列回带到各个模型中进行检验，并以此作为判断各分类方法好坏的标准。

接着，综合权衡各个模型优缺点，有针对性地作一些调整，从而提高分类的准确率。

最后，我们用调整后的模型对未知类别的20个人工制造的序列以及182个自然序列进行分类。

用上述方法对未知的自然序列N1～N182进行分类，得到的结果见附表。 我们的模型分别为：

1、欧式空间模型：将A，T，C，G四个字母在序列中出现的概率组成一个四维的空间向量。求出待测序列的空间向量与A、B两组平均空间向量夹角的余弦值，余弦值越大则说明待测序列与该组序列越接近。

2、特征密码子模型：从A、B两组中分别找出能够区分A、B两组的四个三字母组成的特征密码子。将这八个特征密码子出现的概率构成一个八维的向量空间。比较待测序列的向量与A、B的向量的距离。距离越接近则说明待测序列与该组序列越接近。

3、时间序列模型：考虑A，T，C，G四个字母在样本中出现的周期。求出四个字母出现周期的方差，找出可以区分A、B两组的方差比。求出待测序列的这个比值并与A、B序列的平均比值进行对比，的出待测序列的分类。

4、相似度模型：将待测序列与A、B两序列一一对比，得出待测序列与A、B的最大相关程度，比较这两个数值得出待测序列的分类。

各模型的详细情况及应用见正文。

综合上述方法，我们对未知的20组人工序列进行了分类，得到的结果是： A组：22，23，25，27，29，34，35，36，37

B组：21，24，26，28，30，31，32，33，38，39，40

关键词：序列，碱基，密码子，相似度。

1

一、问题重述

2000年6月，人类基因组计划中DNA全序列草图完成，预计2001年可以完成精确的全序列图，此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的“天书”。这本大自然写成的“天书”是由4个字符A，T，C，G按一定顺序排成的长约30亿的序列，其中没有“断句”也没有标点符号，除了这4个字符表示4种碱基以外，人们对它包含的“内容”知之甚少，难以读懂。破译这部世界上最巨量信息的“天书”是二十一世纪最重要的任务之一。在这个目标中，研究DNA全序列具有什么结构，由这4个字符排成的看似随机的序列中隐藏着什么规律，又是解读这部天书的基础，是生物信息学（Bioinformatics）最重要的课题之一。

虽然人类对这部“天书”知之甚少，但也发现了DNA序列中的一些规律性和结构。例如，在全序列中有一些是用于编码蛋白质的序列片段，即由这4个字符组成的种不同的3字符串，其中大多数用于编码构成蛋白质的20种氨基酸。又例如，在不用于编码蛋白质的序列片段中，A和T的含量特别多些，于是以某些碱基特别丰富作为特征去研究DNA序列的结构也取得了一些结果。此外，利用统计的方法还发现序列的某些片段之间具有相关性，等等。这些发现让人们相信，DNA序列中存在着局部的和全局性的结构，充分发掘序列的结构对理解DNA全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某些细节，突出特征，然后将其表示成适当的数学对象。这种被称为粗粒化和模型化的方法往往有助于研究规律性和结构。

作为研究DNA序列的结构的尝试，提出以下对序列集合进行分类的问题： 1）有20个已知类别的人工制造的序列，其中序列标号1—10 为A类，11-20为B类。请从中提取特征，构造分类方法，并用这些已知类别的序列，衡量你的方法是否足够好。

2）用你认为满意的方法，对另外20个未标明类别的人工序列（标号21—40）进行分类。

3）资料中给出了182个自然DNA序列，它们都较长。用你的分类方法对它们进行分类，像2）一样地给出分类结果。

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

二、基本假设

1、假设题目所给出的未知类别的序列与已知类别的20个序列之间有一定的相关性，即通过对已知的A、B类别分别进行特征的提取，能把未知的序列也归为此已知的两类。

2

2、假设给出的各序列中的密码子之间成正态统计规律。

3、假设所有给出的序列只是整个DNA序列中的一部分，即给出的各序列没有起点和终点。

三、符号说明

符号 PAi PBi， PXi，

意 义

由A类10组序列的碱基组成的向量(i=1,2,...10) 由B类10组序列的碱基组成的向量(i=11,12,...20) 未知各序列的碱基组成的向量(i=21,22,...40) 碱基出现的间隔组成的有限数列的方差 A类中某个密码子出现的概率 B类中某个密码子出现的概率

已知为A类的第i组第j个字符(i=1,2,...10) 已知为B类的第i组第j个字符(i=11,12,...20)

所给的未知类别人工序列的第i组第j个字符(i=21,22,...40) 序列A与序列B的相似度

待测序列与序列A和序列B的相似度的比值

表一

δ

pA pB Aij Bij

Xij S(A,B)

M

四、模型建立与求解

一、欧式空间模型：

所有DNA序列都是由4个字符A，T，C，G按一定顺序排成，每个字母在A、B两类中出现的概率都有或大或小的差异。因此，我们统计出了已知类别的20

3

个人工序列中单个字母在各序列中出现的概率，结果如下：

A0.70.60.50.40.30.20.10actg系列1系列2系列3系列4系列5系列6系列7系列8系列9系列10

B0.70.60.50.40.30.20.10actg系列1系列2系列3系列4系列5系列6系列7系列8系列9系列10

图一

由上面两张图表的对比，我们可以看出：A类中C、G碱基的含量明显比B类中高，而B类中A、T碱基的含量明显比A类中高。但是，这两种碱基含量分布范围在A、B两类中有交叉，因此，若直接以此作为分类标准，分类的准确率不够高。

为了做定量的判断，我们引入四维向量空间，用序列中四个碱基的频率作为此空间的一个向量。由A类，B类和20个已知类别的人工序列可确定出20个向量，具体数值如下：

A 由Ａ序列生成的向量 Ｂ由Ｂ序列生成的向量

1 (0.297297,0.171171,0.135135,0.396396)11(0.354545,0.045455,0.500000,0.100000)2 (0.270270,0.162162,0.153153,0.414414)12(0.327273,0.027273,0.500000,0.145455)3 (0.270270,0.216216,0.063063,0.450450)13(0.327273,0.027273,0.500000,0.145455)4 (0.423423,0.108108,0.288288,0.180180)14(0.300000,0.081818,0.500000,0.118182)5 (0.234234,0.234234,0.108108,0.423423)15(0.290909,0.000000,0.5455,0.063636)6 (0.351351,0.126126,0.126126,0.396396)16(0.363636,0.081818,0.463636,0.090909)7 (0.351351,0.099099,0.11,0.360360)17(0.354545,0.245455,0.263636,0.1363)8 (0.279279,0.162162,0.11,0.369369)18(0.290909,0.118182,0.500000,0.090909)9 (0.207207,0.207207,0.153153,0.432432)19(0.218182,0.145455,0.563636,0.072727)10 (0.181818,0.272727,0.1363,0.409091)20(0.200000,0.063636,0.063636,0.063636)

表二

4

由上面的表格，我们还可以得到由A类序列和B类序列的各碱基出现的概率的平均值组成的向量：

PA =（0.28665，0.175921，0.154177，0.383251）， PB =(0.2954544,0.0909092，0.4518181,0.1009091)。

我们认为这两个向量分别代表了A序列和B序列的特征。

由这两个向量我们一样可以看出，A类中的C，G类碱基含量比较高，B类中的A，T类碱基含量比较高。

定义两向量的乘积：

（a,b,c,d）*(e,f,g,h)=ae+bf+cg+dh；

由此，我们可以求此四维空间中任意两向量的夹角：

⎛P1*P2⎞−1

,Pcos

=2⎜⎟; 1

⎝||P1||*||P2||⎠

我们认为，如果两向量的夹角越小，说明这两个向量的相关程度就越高。由此，我们给出了区分A类和B类序列的一个准则，用数学模型表述为：如果

大于，I=21，22，……，40，那么Pxi就属于B类，否

则的话，Pxi就属于A类。

通过编写MATLAB程序验证，将此方法用于已知类别的20组人工序列，得到以下结果：

编号 与A余弦 与B余弦 类别 编号 与A余弦与B余弦 类别 1 0.2881 0.2045 A 11 0.225 0.3449 B 2 0.2884 0.2056 A 12 0.2314 0.3398 B 3 0.2979 0.1735 A 13 0.2192 0.3313 B 4 0.2539 0.2834 B 14 0.2228 0.3339 B 5 0.2873 0.1821 A 15 0.2073 0.384 B 6 0.2943 0.2123 A 16 0.225 0.3335 B 7 0.2854 0.2347 A 17 0.2377 0.2599 B 8 0.2793 0.22 A 18 0.2161 0.3318 B 9 0.2852 0.1929 A 19 0.2029 0.3397 B 10 0.2779 0.1814 A 20 0.102 0.1029 B

表三

由表格数据可知：除对A中的4号序列不能作出正确判断外，对其余序列都是适用的，正确率达到95%。

最后我们用此法对未知类别的20组序列作出判断，结果为：

5

编号 与A余弦 与B余弦 类别编号与A余弦 与B余弦 类别 21 0.2333 22 0.2561 23 0.2707 24 0.2298 25 0.2618 26 0.23 27 0.2662 28 0.2265 29 0.2806 30 0.2471

0.2797 0.231 0.1981 0.283 0.2237 0.2769 0.2248 0.3053 0.1936 0.2434

B A A B A B A B A B

31 0.2411 32 0.2424 33 0.2416 34 0.2736 35 0.2688 36 0.25 37 0.2638 38 0.2265 39 0.2441 40 0.2242

0.2713 0.2503 0.2686 0.2028 0.2175 0.2159 0.2123 0.2954 0.2341 0.2888

B B B A A A A B A B

表四

二、特征密码子模型

用同样的方法，我们对已知类别的20个人工序列中双字母的16种组合、三字母的种组合出现的概率分别作了统计。我们发现，某些三字母组合在A、B两类中的出现概率有较好的区分度。因此，我们定义这些特殊组合为特征密码子，具体叙述如下：

如果将四个碱基中的三个组成一个密码子，那么一共有种情况。在研究A、B两组的各序列中的各密码子出现的概率差的时候，我们发现，在A类和B类中有能够代表自己特性的一些密码子，我们就定义这些密码子为特征密码子。

特征密码子：若A类中某个密码子出现的概率pA与B类中同一个密码子出现的概率pB之差的绝对值大于0.05，并且，pA>pB，定义该密码子为A类特征密码子。

同理，可定义B类特征密码子。

根据定义，我们在所有密码子出现概率统计表中查找到： A类序列的特征密码子：GGA，CGG，GGC，AGG； B类序列的特征密码子：TTA，TTT，ATT，TAT。

这8个特征密码子在A、B中出现的概率以及概率差值见下表： 密码子 ATT AGG CGG TTA TTT GGA GGC TAT pA 0.024788 0.0597 0.0734 0.0138 0.0156 0.0854 0.0634 0.0128 pB pA−pB 0.098148 0.07336 0.0093 0.0504 0.0056 0.0679 0.0972 0.0835 0.1787 0.1631 0.0083 0.0770 0.0046 0.0587 0.0574 0.0446 表五 由特征密码子的分析可知，任意给定一个DNA序列，我们可以通过计算特征

6

密码子出现概率的大小来进行分类。在A和B类中，提取八个特征密码子：GGA，CGG，GGC，AGG，TTA，TTT，ATT，TAT，按A、B类中每一行DNA序列统计出它们的特征密码子概率，分别记为：（Pi1，Pi2,…,Pi8），(i=1,2,...10)和（Qi1，Qi2,…,Qi8），(i=11,12,...20)。他们的数值分别为： Ａ类的各序列的特征密码子：

P 1 2 3 4 5 6 7 8 9 10

ATT AGG

CGG TTA TTT GAA GGC

TAT 0.036 0.073 0.00.0090 0.009 0.055 0.1460 0.018 0.0 0.1 0 0.0910.0450.009 0.0450.018 0.045 0.1370.0730 0.0910 0.027 0.045 0.0910.0180.0090.1 0.045 0.009 0.0180.0360.0450.0180

0.0090.0090.1 0.027 0.091 0.0820.0090.0270.11 0.08 0.018 0.027 0.055 0.0550.0090.0180.11 0.0450.027 0.036 0.1 0 0.0450.0360.0180.0820.00.009 0.0180.0550.1

0 0.036 0.0730 0.018 0.0 0.0550.0090.0090.0460.0830 Ｂ类的各序列的特征密码子：

Q 1 2 3 4 5 6 7 8 9 10 ATT AGG CGG TTA TTT GAA GGC TAT 0.101 0.009 0 0.092 0.037 0 0.111 0.018 0 0.101 0 0.111 0 0.037 0 0.129 0 0.083 0.009 0 0 0.12 0.1750.0180 0.1380.1660.0090

0.074 0.027 0.046 0.083 0.037

0.12 0.2120.0090.0090.0 0.0830.3980 0

0.0090.1010.1570.0090

0.0830.1110.0090

0.0270.0180.0180.0090.0270.0 0.0180.1290.1570 0.0090.0

0.083 0.027

0.1110.1750.0090 0.00.2120.0090

0.12 0.009 0 0.092 0.009 0 表六

同模型一中一样，将各DNA序列中的特征密码子看作是一个八维的向量。 如果某未知序列与Ａ类有相同的特性，那么可以认为：此序列的特征密码子的向量与pA的“距离”是比较接近的；同样，如果某未知序列与Ｂ类有相同的特性，那么可以认为：此序列的特征密码子的向量与pB的“距离”比较接近。

记：

，B（pB）=（B(PA)i1,B(PA)i2,…B(PA)i8）。 A(pA)=（A(PA)i1,A(PA)i2,…A(PA)i8）那么对任意给出的未知类别的序列：

① 如果

7

∑(A(P)

j=1

8

Aij

−Xij)−∑(B(PA)ij−Xij)2>0.

2

j=1

8

则说明此序列的特征密码子向量较B的距离比较近，此序列归为B类；

②如果

2

(A(P)−X)−(B(P)−X)∑Aijij∑Aijij<0.

2

j=1

j=1

8

8

则说明此序列的特征密码子向量较A的距离比较近，此序列归为A类；

③ 如果

∑(A(P)

j=1

8

Aij

−Xij)−∑(B(PA)ij−Xij)2=0.

2

j=1

8

则无法用此法判断此序列属于哪一类。

用此分类方法对已知类别的20个人工序列进行分类，得到分类结果如下： 编号 与A距离 与B距离 类别 编号 与A距离 与B距离 类别 1 0.0282 0.1734 A 11 0.1936 0.0314 B 2 0.0337 0.1782 A 12 0.1902 0.05 B 3 0.094 0.2533 A 13 0.1932 0.03 B 4 0.1271 0.0825 B 14 0.1797 0.168 B 5 0.0453 0.2137 A 15 0.1802 0.0347 B 6 0.0463 0.2084 A 16 0.1779 0.0302 B 7 0.039 0.1739 A 17 0.1249 0.1053 B 8 0.0561 0.1698 A 18 0.2096 0.0494 B 9 0.0619 0.198 A 18 0.2033 0.0376 B 10 0.0499 0.1749 A 20 0.1587 0.0448 B

表七

由表格数据可知：除对A中的4号序列不能作出正确判断外，对其余序列都是适用的，正确率达到95%。

最后，用此法对未知类别的20个人工序列进行归类： 编号 与A距离 与B距离 类别 编号 与A距离 与B距离 类别 21 0.1262 0.1097 B 31 0.1598 0.0991 B 22 0.0953 0.01312 A 32 0.1168 0.109 B 23 0.083 0.147 A 33 0.1307 0.1101 B 24 0.1342 0.13 A 34 0.0858 0.1333 A 25 0.1146 0.1298 A 35 0.1059 0.1135 A 26 0.1608 0.0632 B 36 0.122 0.1034 B 27 0.0832 0.1236 A 37 0.1125 0.1034 B 28 0.199 0.0375 B 38 0.1658 0.0362 B 29 0.0802 0.15 A 39 0.1241 0.1329 A 30 0.1301 0.1166 B 40 0.14 0.0477 B

表八

三、时间序列模型

8

在考虑一个序列的时候，它代表的信息远不止各个组成元素出现的概率，我们还应该考虑每个字母出现的位置关系。

任取一个序列Δ为例：Δ={λ1λ2λ3…λnλn+1…}，如果只考虑每个元素λi出现的位置xi（i=1，2，3，……）的话，显然是不合理的。因为λi的位置与此序列的起始元素有关，而题中给出的只是DNA序列的一个片段，没有起点和终点。为了消除这个影响，我们考虑每个元素出现的间隔，也就是考虑考虑序列的周期性。如果记χi=xi-xj，那么对于每一个序列中的每一个碱基，我们都可以得到一个数列{χi}。

不难想象，对于一个越稳定的有限序列，每个元素出现的周期是越大的，为了描述这种稳定性，通常的做法是考虑每个碱基出现的间隔大小的方差，记为：

δ=

∑(χi=1

n

i

−χ)2

n

δ的大小反映了此序列的波动程度的大小。

通过对给出的40组人工序列的处理，我们可以得出每个序列中每个碱基出现的间隔大小的方差。对不同序列中的每个碱基出现间隔的方差进行分析，我们得出如下结论：

G碱基出现间隔的方差δg与T碱基出现间隔的方差δt之比，和G碱基出现间隔的方差δg与A碱基出现间隔的方差δa之比能较好的反映A、B序列的特征，但前者反映的特征更明显。

。 因此我们选取δg/δt作为分类参考量（具体关系见下表）A类 1 2 3 4 5 6 7 8 9 10

δt

28.22959 34.60938 269.88 17.85016 74.44628 172.8402 21.99 25.6875 25.90234 23.53061 δg 4.06273.5066683.19450223.390586.150.6154675.2544374.66 2.63467.702479

δg/δt

B类

δt

2.4444442.3487654.05995 2.4255821.6783682.2144 11.2533.6296311.11153 1.48831

δg 71.21 61.12 47.294 35.07639 104.88 258.321 60.7398 84.91357 142.1224 337.5833 δg/δt 29.1313726.0259711.79114.4610262.49458116.65515.39481123.39455127.862 226.8232

0.14391811 0.13021512 0.01183613 1.31038514 0.08314115 0.02670416 0.234717 0.18141118 0.10171619 0.19984520

表九

我们认为：

9

1若δ/δ<1,那么此组序列属于A类； ○tg

②若δg/δt=1，则用此种方法不能判断； ③若δg/δt>1,那么此组序列属于B类。

由上表可以看出，已知类别的20个人工序列中，只有 A中的4号序列反常，对其余序列都是适用的，正确率达到95%。

最后我们用此法对未知类别的20组序列作出判断，结果为：

编号 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

δt

4.9875 11.23141 32.61728 5.032137 12.86157 5.923201 16.97542 2.522108 28.16358 5.45562 5.873766 5.5063 3.750001 78.35938 11.5275 15.84127 23.5475 3.731601 10.31771 4.857143

δg

13.05247 3.284024 4.670359 7.39229 5.610822 7.3875 5.910902 15.53633 3.732955 2.126033 9.159722 9.167092 5.084711 3.823302 3.584775 3.486686 3.900826 17.51247 5.569161 19.40166

δg/δt

2.617037 0.292397 0.143187 1.469016 0.436247 1.247214 0.348203 6.160059 0.132545 0.3696 1.559429 1.623913 1.355923 0.048792 0.310976 0.220101 0.165658 4.693017 0.539767 3.99446

类别 B A A B A B A B B B B B B A A A A B A B

表十

这种方法的判断结果与模型一中一致。

四、相似度模型 为了能够更准确的分类我们引进了相似度，将待测序列与样本序列一一对比，比较其相似度来进行分类判断。 首先我们定义了一种运算符⊗，利用此运算符来计算两组序列的相似度。

10

⊗ A T C G A 1 0 0 0 T 0 1 0 0 C 0 0 1 0 G 0 0 0 1 表十一

若X=Y，则X⊗Y=1，否则X⊗Y=0;若X或Y 有即当X,Y∈{A,T,C,G}时，

一个不属于{A,T,C,G}这个集合时，X⊗Y=0。

然后我们定义了相似度的计算公式：

A⊗B=max{∑Am−j+i⊗Bi},j=1,2,...,m+n−1,i≤n,m−j+i≥1

i=1i≤j

其中，m ,n分别为序列A、B的长度。

下面我们来举一个例子介绍相似度运算的规则： 例如求序列A=acgc和B=ctcag的相似度。 1.A: a c g c

B: c t c a g

所以第一项为：S1=A4⊗B1=c ⊗ c = 1。 2.A: a c g c

B: c t c a g

所以第二项为：S2=A3⊗B1+A4⊗B2=g⊗c + c⊗t =0+0=0。 3.A: a c g c

B: c t c a g

所以第三项为：S3=A2⊗B1+A3⊗B2+A4⊗B3= c⊗c + g⊗t + c⊗c = 1 + 0 + 1 = 2. 依次类推：

S4=A1⊗B1+A2⊗B2+A3⊗B3+A4⊗B4= a⊗c + c⊗t + g⊗c+ c⊗a =0 S5=A1⊗B2+A2⊗B3+A3⊗B4+A4⊗B5=a⊗t + c⊗c + g⊗a+ c⊗g = 1 S6=A1⊗B3+A2⊗B4+A3⊗B5=a⊗c + c⊗a + g⊗g =1 S7=A1⊗B4+A2⊗B5=a⊗a + c⊗g =1 S8A1⊗B5=a ⊗ g =1.

所以可得到S(A,B)=A⊗B=max{Si}=S3=2，即A与B的相似度为2。 为了判定待测序列的分别，我们给出了下述定义。

11

定义：若X与A 的相关度大于X与B的相关度，则认为X属于A类，若X与B的相关度大于与A的相关度，则认为X属于B类，若X与A的相似度等于X与B的相似度，则认为X无法判断。

我们利用上述概念，构造了一个相关度分类的算法。

我们将待测的人工序列Xi,i=21,22,...,40以及自然序列Ni,i=1,2,...,182分别与A组A1~A10以及B组的B11~B21分别做相似度计算，得到SA1~SA10，以及SB11~SB20，求出待测序列Xi与A组的平均相似度：

SA=（SA1+SA2+……+SA10）/10 以及待测序列Xi与B组的平均相似度： SB=（SB11+SB12+……+SB20）/10。

并定义SA与SB为待测序列Xi与A组和B组的相似度。

记W=SA/SB

若W>1 ，则将X序列判为A类。 若W<1 ，则将X序列判为B类。 若W=1 ，则X无法判别。

将W作为衡量的标准，我们不难发现，当W 与1越接近的时候，则说明待测序列与A、B的相似程度越接近，越难区分待测序列属于A还是属于B，得到的结果也越不准确，当W与离1越远的时候，则分类也越准确。

利用上述方法，我们编写了C语言程序对学习样本A组A1~A10以及B组B11~B20进行分类得到：

序号 相似度比 分组序号 相似度比分组 1 1.61 A 11 0.9243B 2 1.521036 A 12 0.930342B 3 1.8030 A 13 0.997468B 4 1.066327 A 14 0.794565B 5 1.698582 A 15 0.900474B 6 1.569579 A 16 0.96747 B 7 1.290055 A 17 0.970696B 8 1.470405 A 18 0.9207B 9 1.615917 A 19 0.922799B 10 1.654545 A 20 0.926342B

表十二

由我们计算的结果可以看到，对于样本的20组，我们可以将A、B两组完全的分开，准确率达到100%。

我们对未知类别的20组人工序列的X21~X40进行分类。得到结果如下：

12

序号 21 22 23 24 25 26 27 28 29 30 相似度比 0.788137 1.052286 1.288769 0.759161 1.10666 0.780984 1.120872 0.698493 1.361422 0.962138

分组 序号 B 31 A 32 A 33 B 34 A 35 B 36 A 37 B 38 A 39 B 40

表十三

相似度比0.8349870.9065240.8477151.2904621.17801 1.0974181.1814160.7157230.9886310.723558分组 B B B A A A A B B B

五、模型的评价

我们建立的四个模型各有优点与不足： 模型一整体上最简单，操作起来也很方便。但是，对于一个由四个字符组成的序列来说，只考虑单个字符的出现概率，损失了太多序列本身携带的信息，分类结果可信度不高。 模型二考虑到三个字符组合出现的频率，与模型一相比，损失的信息要少一些，可信度因此也相对高一些。就模型的整体结构来说，处理起来也不算复杂。 模型三在前两个模型的基础上又有所改进。前两个模型都只考虑了序列的局部结构，模型三中主要以序列的全局性特征作为分类标准，即：考虑到序列的长程相关性。虽然看上去分类结果与模型一基本一致，但可信度又有所提高。

模型四能较准确的对A、B两组进行分类，但是也有不足之处。由于样本数量太少，且样本的长度很段，所以当相似度接近比接近1时，容易产生错判。对于数据量远大于样本数量的自然序列进行分类，则错判的概率更大。所以我们需要对次模型进行改进。

若我们使用反馈式学习，对样本进行不断的分类，则我们可以得到更好的结果。

当我们对于自然序列进行分类的时候，我们将判为A类且相似度比最大的一组（即被判为A类且准确率最高的一组）加入A类的样本，若没有则保持A样本不变，同样我们将被判为B类且相似度比最小的一组加入B类的样本，若没有，保持B样本不变。

用新的样本对于其他各组再次进行判别，重复上述过程，对于待测组进行不断的分类，不断的扩充样本的规模，直到182组全部进入标准样本之中。

我们采用新的方法对待测的自然序列进行重新分类，我们得到了新的结果，且发现待测序列与A、B的相似度比明显离1更远。这说明我们的反馈算法确实有利于提高我们分类的准确性。

参考文献：

[1] 郑阿奇 主编 MATLAB实用教程（第二版），电子工业出版社，2007年8月。 [2] 谭浩强，C语言程序设计（第三版），清华大学出版社，2006年10月。

13

附表：

182个自然序列分类结果： 自然序列 1~10 B B B B 11~20 B B A A 21~30 A B B B 31~40 A A A B 41~50 A A B A

A A B A A

B A B A B

B B A B

无法判断

A A B A B

B A B A A

B A B B B 51~60 B 61~70 A 71~80 A 81~90 B 91~100 A 101~110 A 111~120 B 121~130 B 131~140 B 141~150 A 151~160 B 161~170 B 171~180 A 181~182 B

A B A B B A B B B B B B A B B B B B B B B B

B B B B B B B B A B B B B B B B A A B A A B B B B

B 无法判断A B B B B B

A

14

B B B A B A B

B 无法判断

B A B B A B B A A B A B B B B A B B

B

A A A A B A B A B B B A A B B B B B A B A B B B B B A

B

B A B A A B A B B B B B B B