DNA序列分类模型.doc

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个。具体情况见文中答案。我们还对三种分类方法进行了类比，认为模型二、三方法新颖独特，结果稳定，它们是一种较好的分类方法。并且对各种计算结果进行误差分析和检验等工作。

问题的重述

本问题为一个DNA序列分类问题。假定已知两组人工已分类的DNA序列（20个已知类别的人工制造的序列），其中序列标号1—10为A类，11-20为B类。要求我们从已经分类了的DNA序列片段中提取共同特征构造分类方法，并评价所用分类方法的好坏，从而构造或选择一种较好的分类方法。测试对象是20个未标明类别的人工序列（标号21—40）和182个自然DNA序列。
二、模型的假设及符号说明
1、名词解释：
碱基：在生物学中，用A，T，C，G四个字符代表组成DNA序列的四种碱基；
密码子：在遗传学中每三个碱基的组合被称为一个密码子，可以编码一个氨基酸，共有64个，还可以由密码子组成20个氨基酸。
特征密码子：若类中某个密码子出现的概率pA与类中同一个密码子出现的概率pB之差的绝对值大于0.05，并且，pA>pB，定义该密码子为类特征密码子。同理，可定义B类特征密码子。
2、模型假设：
所给的DNA序列片段中没有断句和标点符号。对密码子的计数没有固定的起点
和终点。
假定各密码子近似呈现正态统计规律。
DNA序列的某些片段之间具有一定的相关性。
DNA序列不构成环状，划分密码子时，碱基剩余个数小于3时舍去不考虑。
3、符号说明：
-------------------表示第k种密码子在第i个序列片段中出现的频率；
----------------------类特征密码子；
----------------------类特征密码子；
--------------------最适A类密码子的概率；
---------------------最适B类密码子的概率；
-------------------------误判率；
---------------------空间向量夹角余弦之差；

三、模型的分析和建立
1、A、B两类的DNA序列特征提取
碱基含量分析
对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|1AAA0.0450.0450.000433CAA0.01380.00650.00732AAT0.01560.04260.027034CAT0.00830.00830.00013AAC0.01930.01020.009135CAC0.01010.00370.00644AAG0.02570.00930.016436CAG