DNA序列分类
摘要本问题是一个“有人管理分类问题”。 首先分别列举出20个学习样本序列中1字符串、2字符串、3字符串出现的频率，构成含41个变量的基本特征集，接着用主成分分析法从中提取出4个特征。然后用Fisher线性判别法进行分类，得出了所求20个人工制造序列及182个自然序列的分类结果如下：
1） 20个人工序列：22, 23，25，27，29，34，35，36，37为A类，其余为B类。
2） 182个自然序列：1，4，8，10，27，29，32，41，43，48，54，63，70，72，75，
76，81，86，90，92，102，110，116，119，126，131，144，150，157，159，160，161，162，163，164，165，166，169，170，182为B类，其余为A类。 最后通过检验证明所用的分类数学模型效率较高。
一. 问 题 重 述
人类基因组计划中DNA全序列草图是由4个字符A，T，C，G按一定顺序排成的长约30亿的序列，其中没有“断句”也没有标点符号。虽然人类对它知之甚少，但也发现了其中的一些规律性和结构。例如，在全序列中有一些是用于编码蛋白质的序列片段，即由这4个字符组成的64种不同的3字符串，其中大多数用于编码构成蛋白质的20种氨基酸。又例如，在不用于编码蛋白质的序列片段中，A和T的含量特别多些，于是以某些碱基特别丰富作为特征去研究DNA序列的结构也取得了一些结果。此外，利用统计的方法还发现序列的某些片段之间具有相关性，等等。这些发现让人们相信，DNA序列中存在着局部的和全局性的结构，充分发掘序列的结构对理解DNA全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某些细节，突出特征，然后将其表示成适当的数学对象。
作为研究DNA序列的结构的尝试，提出以下对序列集合进行分类的问题：
1）请从20个已知类别的人工制造的序列（其中序列标号1—10 为A类，11-20为B类）中提取特征，构造分类方法，并用这些已知类别的序列，衡量你的方法是否足够好。然后用你认为满意的方法，对另外20个未标明类别的人工序列（标号21—40）进行分类，把结果用序号（按从小到大的顺序）标明它们的类别（无法分类的不写入）
2） 同样方法对182个自然DNA序列(它们都较长)进行分类，像1）一样地给出分类结果。
二.模型的合理假设
1． 各序列中DNA碱基三联组（即3字符串）的起始位置和基因表达不影响分类的结
果。
2． 64种3字符串压缩为20组后不影响分类的结果。
3． 较长的182个自然序列与已知类别的20个样本序列具有共同的特征。
1 / 24
三.模型建立与求解
研究DNA序列具有什么结构，其A，T，C，G4个碱基排成的看似随机的序列中隐藏着什么规律，是解读人类基因组计划中DNA全序列草图的基础，也是生物信息学（Bioinformaties）最重要的课题之一。
题目给出了20个已知为两个类别的人工制造的DNA序列，要求我们从中提取特征，构造分类方法，从而对20个未标明类别的人工DNA序列和182个自然DNA序列进行分类。这是模式识别中的“有人管理分类”问题，即事先规定了分类的标准和种类的数目，通过大批已知样本的信息处理找出规律，再用计算机预报未知。给出的已知类别的样本称为学习样本。对于此类问题，我们通过建立分类数学模型（这包括形成和提取特征以及制定分类决策）、考查分类模型的效率、预报未知这几个步骤来进行。
一．
特征的形成和提取
为了有效地实现分类识别，首先要根据被识别的对象产生一组基本特征，并对基本特征进行变换，得到最能反映分类本质的特征。这就是特征形成和提取的过程。在列举了尽可能完备的特征参数集之后，就要借助于数学的方法，使特征参数的数目（在保证分类良好的前提下）减到最小。这是因为：1.多余的特征参数不但没有多少好处，而且会带来噪音，干扰分类和数学模型的建立。2.为了保证样本数和特征参数个数的比值足够大，而又不必要用太多的样本，最好使特征参数的个数降至最少。模式识别计算一般要求样本数至少为变量数的3倍，否则结果不够可靠。本问题的学习样本数为20个，故特征参数的个数以6—8个为宜。
我们通过研究4个字符A,T,C,G在DNA序列中的排列、组合特性，主要是研究字符和字符串的排列在序列中出现的频率，从中提取DNA序列的结构特征参数。
（一）特征的形成
分别列举一个字符，2个字符，3个字符的排列在序列中出现的频率，构成基本特征集。
i. 1个字符的出现频率
表1列出了20个样本中A，T，C，G这4个字符出现的频率。由于在不用于编
码蛋白质的序列片段中，A和T的含量特别多些，因此我们将A和T是否特别丰富作为一个特征。在表一中，列出了A和T出现的频率之和。(程序见附录一)
表 1
A C T G A+T
1. 29.73 17.12 13.51 39.64 43.24
2 / 24
2. 27.03 16.22 15.32 41.44 42.34 3. 27.03 21.62 6.31 45.05 33.33 4. 42.34 10.81 28.83 18.02 71.17 5. 23.42 23.42 10.81 42.34 34.23 6. 35.14 12.61 12.61 39.64 47.75 7. 35.14 9.91 18.92 36.04 54.05
8. 27.93 16.22 18.92 36.94 46.85
9. 20.72 20.72 15.32 43.24 36.04
10.18.1827.27 13.64 40.91 31.82
11. 35.45 4.55 50.00 10.00 85.45
12. 32.73 2.73 50.00 14.55 82.73
13. 25.45 10.00 51.82 12.73 77.27 14. 30.00 8.18 50.00 11.82 80.00 15. 29.09 .00 64.55 6.36 93.64 16. 36.36 8.18 46.36 9.09 82.73 17. 35.45 24.55 26.36 13.64 61.82 18. 29.09 11.82 50.00 9.09 79.09
19. 21.82 14.55 56.36 7.27 78.18
20. 20.00 17.27 56.36 6.36 76.36
2．2字符串的排列出现的频率
A，T，C，G这4个字符组成了16种不同的2字符串。表2列出了20个样本中各2字符串出现的频率。（用“滚动”算法，如attcg有at,tt,tc,cg共4个2字符串）(程序与附录一类似)
表 2
AA AC AT AG TA TC TG TT CA CT CC CG GA GT GC GG
1. 9.01 9.01 3.60 8.11 4.50 .90 4.50 3.60 3.60 3.60 1.80 8.11 11.7 1 2.70 5.41 18.92 2. 9.91 7.21 3.60 5.41 2.70 1.80 5.41 5.41 4.50 1.80 .90 9.01 9.91 4.50 5.41 21.62 3. 5.41 11.71 3.60 5.41 2.70 1.80 .90 .90 5.41 .90 .90 14.41 13.51 .90 7.21 23.42 4. 18.92 5.41 11.71 5.41 10.81 1.80 5.41 10.81 5.41 1.80 .90 2.70 6.31 4.50 2.70 4.50 5. 6.31 8.11 1.80 7.21 1.80 2.70 2.70 3.60 5.41 4.50 2.70 10.81 9.91 .90 9.01 21.62 6. 15.32 2.70 6.31 9.91 3.60 1.80 1.80 5.41 4.50 .00 .00 8.11 10.81 .90 8.11 19.82
3 / 24
DNA序列分类(2000年竞赛题)
