《DNA序列分类2000年竞赛题》由会员分享，可在线阅读，更多相关《DNA序列分类2000年竞赛题（22页珍藏版）》请在金锄头文库上搜索。
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，1
2、19，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 类，1120 为 B类）中提取特征，构造分类方法，并用这些已知类别的序列，衡量你的方法是否
4、足够好然后用你认为满意的方法，对另外 20 个未标明类别的人工序列（标号 2140）进行分类，把结果用序号（按从小到大的顺序）标明他们的类别（无法分类的不写入） 2）同样方法对 182 个自然 DNA 序列(他们都较长) 进行分类，像 1）一样地给出分类结果二、模型的合理假设1 各序列中 DNA 碱基三联组（即 3 字符串）的起始位置和基因表达不影响分类的结果2 64 种 3 字符串压缩为 20 组后不影响分类的结果3 较长的 182 个自然序列与已知类别的 20 个样本序列具有共同的特征三、模型建立与求解研究 DNA 序列具有什么结构，其 A，T，C ，G 4 个碱基排成的看似随机的序列中隐
5、藏着什么规律，是解读人类基因组计划中 DNA 全序列草图的基础，也是生物信息学（Bioinformatcs ）最重要的课题之一题目给出了 20 个已知为两个类别的人工制造的 DNA 序列，要求我们从中提取特征，构造分类方法，从而对 20 个未标明类别的人工 DNA 序列和 182 个自然 DNA 序列进行分类这是模式识别中的“有人管理分类”问题，即事先规定了分类的标准和种类的数目，通过大批已知样本的信息处理找出规律，再用计算机预报未知给出的已知类别的样本称为学习样本对于此类问题，我们通过建立分类数学模型（这包括形成和提取特征以及制定分类决策） 、考查分类模型的效率、预报未知这几个步骤来进行（一
6、）特征的形成和提取为了有效地实现分类识别，首先要根据被识别的对象产生一组基本特征，并对基本特征进行变换，得到最能反映分类本质的特征这就是特征形成和提取的过程在列举了尽可能完备的特征参数集之后，就要借助于数学的方法，使特征参数的数目（在保证分类良好的前提下）减到最小这是因为：1.多余的特征参数不但没有多少好处，而且会带来噪音，干扰分类和数学模型的建立2.为了保证样本数和特征参数个数的比值足够大，而又不必要用太多的样本，最好使特征参数的个数降至最少模式识别计算一般要求样本数至少为变量数的3 倍，否则结果不够可靠本问题的学习样本数为 20 个，故特征参数的个数以 68 个为宜我们通过研究 4 个字符
7、 A,T,C,G 在 DNA 序列中的排列、组合特性，主要是研究字符和字符串的排列在序列中出现的频率，从中提取 DNA 序列的结构特征参数1特征的形成分别列举一个字符，2 个字符，3 个字符的排列在序列中出现的频率，构成基本特征集（1）1 个字符的出现频率表 1 列出了 20 个样本中 A， T，C，G 这 4 个字符出现的频率由于在不用于编码蛋白质的序列片段中，A 和 T 的含量特别多些，因此我们将 A 和 T 是否特别丰富作为一个特征在表 1 中，列出了 A 和 T 出现的频率之和( 程序见附录一 )表 1A C T G A+T1. 29.73 17.12 13.51 39.64 43.2
8、4 2. 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.91 31.8211. 35.45 4
9、.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. 20.00 17.27 56.36 6.
10、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 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.21 3.60 5.41 2.70
11、 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 2
12、1.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 16.228. 8.11 3.60 6.31 9.91 5.41 3.60 2.70 7.21 2.70 3.60 1.80 8.11 10.81 1.80 7.2116.22 9. 9.01 .90 4.50 6.31 .00 3.60 7.21 4.50 3.60 2
13、.70 2.70 11.71 7.21 3.60 13.5118.0210. 6.36 3.64 1.82 6.36 1.82 5.45 2.73 3.64 5.45 3.64 4.55 13.64 4.55 3.64 13.64 18.1811. 15.45 2.73 14.55 2.73 16.36 .91 1.82 30.00 .91 .91 .91 1.82 2.73 4.55 .00 2.7312. 13.64 .91 10.91 6.36 15.45 1.82 1.82 30.91 .91 .91 .00 .91 2.73 7.27 .00 4.5513. 6.36 4.55 10.00 4.55 12.73 1.82 2.73 34.55 2.73 2.73 1.82 1.8 2 3.64 4.55 1.82 2.7314. 8.18 .91 12.73 7.27 13.64 6.36 1.82 28.18 2.73 4.55 .00 .91 5.45 4.55 .91 .9115.13.64 .00 12.73 1.82 13.64 .00 2.73 48.18 .00 .00 .00 .00 1.82 3.64 .00 .9116. 1
