DNA序列分类模型
重庆市数学建模竞赛一等奖
王 勇, 莫志锋, 秦力顼(1999级自动化学院)
[摘要]
本文根据题中所给两个已知类别的DNA序列进行结构特征分析，从中提取信息和构造分类模型，对未知类别的DNA序列进行分类。我们构造了三个分类模型，它们分别是：特征密码子概率分布判别模型、图论最小生成树模型和向量空间直观判别模型。后两种分类结果几乎一致，判别率在90%左右，误判率控制在（0.05-0.1）范围。
问题一结果为： 模型一的结果：
A类有7个：22，23，27，29，34，35，37；
B类有10个：21，24，26，28，30，31，32，33，38，40； 不能判断的有3个：25，36，39； 模型三的结果：
A类有10种：22，23，25，27，29，34，35，36，37，39； B类有10种：21，24，26，28，30，31，32，33，38，40；
问题二结果为： 模型二的结果：
A类有108个，B类有74个。具体情况见文中答案。 模型三的结果：
A类有120个，B类有62个。具体情况见文中答案。
我们还对三种分类方法进行了类比，认为模型二、三方法新颖独特，结果稳定，它们是一种较好的分类方法。并且对各种计算结果进行误差分析和检验等工作。
13
一、 问题的重述
本问题为一个DNA序列分类问题。假定已知两组人工已分类的DNA序列（20个已知类别的人工制造的序列），其中序列标号1—10 为A类，11-20为B类。要求我们从已经分类了的DNA序列片段中提取共同特征构造分类方法，并评价所用分类方法的好坏，从而构造或选择一种较好的分类方法。测试对象是20个未标明类别的人工序列（标号21—40）和182个自然DNA序列。
二、模型的假设及符号说明
1、名词解释：
碱基： 在生物学中，用A，T，C，G四个字符代表组成DNA序列的四种碱基；
密码子：在遗传学中每三个碱基的组合被称为一个密码子，可以编码一个氨基酸，共有64个，还可以由密码子组成20个氨基酸。
特征密码子：若A类中某个密码子出现的概率pA与B类中同一个密码子出现的概率pB之差的绝对值大于0.05，并且，pA > pB，定义该密码子为A类特征密码子。同理，可定义B类特征密码子。
2、模型假设：
① 所给的DNA序列片段中没有断句和标点符号。对密码子的计数没有固定的起点 和终点。
② 假定各密码子近似呈现正态统计规律。
③ DNA序列的某些片段之间具有一定的相关性。
④ DNA序列不构成环状，划分密码子时，碱基剩余个数小于3时舍去不考虑。
3、符号说明：
pi(k)------------------- 表示第k种密码子在第i个序列片段中出现的频率；
Hi---------------------- A类特征密码子； Ri---------------------- B类特征密码子； Pi(H)--------------------最适A类密码子的概率； Pi(R)---------------------最适B类密码子的概率；
?-------------------------误判率；
W(i)---------------------空间向量夹角余弦之差；
13
三、模型的分析和建立
1、A、B两类的DNA序列特征提取
（1） 碱基含量分析
对A，B两类中的碱基a，t，c，g出现的频率进行了统计，其分布状况如下： A类：t，c 的总含量在25 ~ 41%左右，a，g 的总含量在59 ~ 75%左右； B类：t，c 的总含量在50 ~ 74%左右，a，g 的总含量在26 ~ 49%左右； 以上的碱基含量分布作为已知DNA序列的第一特征。由此，我们可以根据碱基含量对未知类型的DNA序列片段进行粗略的分类：
问题（1）： A类:29, 34;
B类:21, 24, 26, 28, 31, 32, 33, 36, 38, 39, 40; 不能辨别类：22，23，25，27，30，35，37；
在此基础上再对A、B两类进行第二、第三特征提取。针对不能判别类型利用其他特征和分类方法进行鉴别。
（2）密码子的概率分布状况分析
由遗传学中的知识可知,任何基因都是由64种密码子构成,不同的DNA序列片段中各密码子出现的概率不同。以密码子出现的概率不同为出发点，我们分别对A、B两类中关于DNA序列中的64种密码子的平均频率进行了统计，并且分析了A、B两类的特征密码子。如下统计表1：
表1：64种密码子的平均概率分布表
序号 密码子 A(pA) B(pB) |pA-pB| 序号 密码子 A(pA) B(pB) |pA-pB| 1 AAA 0.045 0.0454 0.0004 33 CAA 0.0138 0.0065 0.0073 2 AAT 0.0156 0.0426 0.0270 34 CAT 0.0083 0.0083 0.0001 3 AAC 0.0193 0.0102 0.0091 35 CAC 0.0101 0.0037 0.0064 4 AAG 0.0257 0.0093 0.0164 36 CAG 0.0092 0.0037 0.0055 5 ATA 0.0156 0.0185 0.0029 37 CTA 0.0037 0.0111 0.0074 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
ATT ATC ATG ACA ACT ACC ACG AGA AGT AGC AGG TAA TAT TAC TAG 0.0165 0.0073 0.0156 0.0147 0.0064 0.0055 0.0285 0.0055 0.0028 0.0037 0.0597 0.0101 0.0128 0.0083 0.0073 0.0741 0.0157 0.0111 0.0083 0.0139 0.0056 0.0074 0.0130 0.0083 0.000 0.0093 0.0463 0.0574 0.0194 0.0130 0.0576* 0.0084 0.0045 0.0064 0.0075 0.0001 0.0211 0.0075 0.0056 0.0037 0.0504* 0.0362 0.0546* 0.0112 0.0056 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 CTT CTC CTG CCA CCT CCC CCG CGA CGT CGC CGG GAA GAT GAC GAG 0.0083 0.0241 0.0158 0.0037 0.0083 0.0047 0.0092 0.0046 0.0046 0.0064 0.0019 0.0046 0.0009 0.0083 0.0074 0.0009 0.0037 0.0028 0.0092 0.0019 0.0073 0.0046 0.0028 0.0018 0.0046 0.0056 0.0010 0.0092 0.0009 0.0083 0.0734 0.0056 0.0679* 0.0367 0.0120 0.0247 0.0138 0.0130 0.0008 0.0174 0.0019 0.0156 0.0294 0.0046 0.0248 13
DNA序列分类模型
