1、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，
2、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 种氨基酸。又例如，在不用于编码蛋白质的
3、序列片段中，A 和 T 的含量特别多些，于是以某些碱基特别丰富作为特征去研究 DNA 序列的结构也取得了一些结果。此外，利用统计的方法还发现序列的某些片段之间具有相关性，等等。这些发现让人们相信，DNA 序列中存在着局部的和全局性的结构，充分发掘序列的结构对理解 DNA全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某些细节，突出特征，然后将其表示成适当的数学对象。 作为研究 DNA 序列的结构的尝试，提出以下对序列集合进行分类的问题： 1）请从 20 个已知类别的人工制造的序列（其中序列标号 110 为 A 类，11-20为 B 类）中提取特征，构造分类方法，并用这些已知类别的
4、序列，衡量你的方法是否足够好。然后用你认为满意的方法，对另外 20 个未标明类别的人工序列（标号2140）进行分类，把结果用序号（按从小到大的顺序）标明它们的类别（无法分类的不写入）2） 同样方法对 182 个自然 DNA 序列(它们都较长)进行分类，像 1）一样地给出分类结果。二.模型的合理假设1 各序列中 DNA 碱基三联组（即 3 字符串）的起始位置和基因表达不影响分类的结果。2 64 种 3 字符串压缩为 20 组后不影响分类的结果。3 较长的 182 个自然序列与已知类别的20 个样本序列具有共同的特征。三.模型建立与求解研究 DNA 序列具有什么结构，其A，T， C，G4 个碱基排
5、成的看似随机的序列中隐藏着什么规律，是解读人类基因组计划中 DNA 全序列草图的基础，也是生物信息学（Bioinformaties）最重要的课题之一。题目给出了 20 个已知为两个类别的人工制造的 DNA 序列，要求我们从中提取特征，构造分类方法，从而对 20 个未标明类别的人工 DNA 序列和 182 个自然 DNA 序列进行分类。这是模式识别中的“有人管理分类”问题，即事先规定了分类的标准和种类的数目，通过大批已知样本的信息处理找出规律，再用计算机预报未知。给出的已知类别的样本称为学习样本。对于此类问题，我们通过建立分类数学模型（这包括形成和提取特征以及制定分类决策） 、考查分类模型的效率
6、、预报未知这几个步骤来进行。一 特征的形成和提取为了有效地实现分类识别，首先要根据被识别的对象产生一组基本特征，并对基本特征进行变换，得到最能反映分类本质的特征。这就是特征形成和提取的过程。在列举了尽可能完备的特征参数集之后，就要借助于数学的方法，使特征参数的数目（在保证分类良好的前提下）减到最小。这是因为：1.多余的特征参数不但没有多少好处，而且会带来噪音，干扰分类和数学模型的建立。2.为了保证样本数和特征参数个数的比值足够大，而又不必要用太多的样本，最好使特征参数的个数降至最少。模式识别计算一般要求样本数至少为变量数的 3 倍，否则结果不够可靠。本问题的学习样本数为 20 个，故特征参数的
7、个数以68 个为宜。我们通过研究 4 个字符 A,T,C,G 在 DNA序列中的排列、组合特性，主要是研究字符和字符串的排列在序列中出现的频率，从中提取 DNA 序列的结构特征参数。（一）特征的形成分别列举一个字符，2 个字符，3 个字符的排列在序列中出现的频率，构成基本特征集。i. 1 个字符的出现频率表 1 列出了 20 个样本中 A，T，C，G这 4 个字符出现的频率。由于在不用于编码蛋白质的序列片段中，A 和 T 的含量特别多些，因此我们将 A 和 T 是否特别丰富作为一个特征。在表一中，列出了 A 和 T出现的频率之和。(程序见附录一)表 1A C T G A+T1. 29.73 1
8、7.12 13.51 39.64 43.242. 27.03 16.22 15.32 41.44 42.343. 27.03 21.62 6.31 45.05 33.334. 42.34 10.81 28.83 18.02 71.175. 23.42 23.42 10.81 42.34 34.236. 35.14 12.61 12.61 39.64 47.757. 35.14 9.91 18.92 36.04 54.058. 27.93 16.22 18.92 36.94 46.859. 20.72 20.72 15.32 43.24 36.0410. 18.18 27.27 13.64 40
9、.91 31.8211. 35.45 4.55 50.00 10.00 85.4512. 32.73 2.73 50.00 14.55 82.7313. 25.45 10.00 51.82 12.73 77.2714. 30.00 8.18 50.00 11.82 80.0015. 29.09 .00 64.55 6.36 93.6416. 36.36 8.18 46.36 9.09 82.7317. 35.45 24.55 26.36 13.64 61.8218. 29.09 11.82 50.00 9.09 79.0919. 21.82 14.55 56.36 7.27 78.1820.
10、20.00 17.27 56.36 6.36 76.3622 字符串的排列出现的频率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 GG1. 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.922. 9.91 7
11、.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.623. 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.424. 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.505. 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.626. 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.827. 15.32 1.80 10.81 7.21 4.50 2.70 6.31 5.41 .90 1.80 .90 6.31 13.51 .90 4.50
