2000网易杯全国大学生数学建模竞赛题目A题 DNA序列分类
2000年6月，人类基因组计划中DNA全序列草图完成，预计2001年可完成精确的全序列图，此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的\天书\。这本大自然写成的\天书\是由4个字符A，T，C，G按一定顺序排成的长约30亿的序列，其中没有\断句\也没有标点符号，除了这4个字符表示4种碱基以外，人们对它包含的\内容\知之甚少，难以读懂。破译这部世界上最巨量信息的\天书\是二十一世纪最重要的任务之一。在这个目标中，研究DNA全序列具有什么结构，由这4个字符排成的看似随机的序列中隐藏着什么规律，又是解读这部天书的基础，是生物信息学（Bioinformatics）最重要的课题之一。 虽然人类对这部\天书\知之甚少，但也发现了DNA序列中的一些规律性和结构。例如，在全序列中有一些是用于编码蛋白质的序列片段，即由这4个字符组成的64种不同的3字符串，其中大多数用于编码构成蛋白质的20种氨基础酸。又例如，在不用于编参与蛋白质的序列片段中，A和T的含量特别多些，于是以某些碱基特别丰富作为特征去研究DNA序列的结构也取得了一些结果。此外，利用统计的方法还发现序列的某些片段之间具有相关性，等等。这些发现让人们相信，DNA序列中存在着局部的和合局性的结构，充分发掘序列的结 构对理解DNA全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某些细节，突出特征，然后将其表示成适当的数学对象。这种被称为粗粒化和模型化的方法往往有助于研究规律性和结构。
作为研究DNA序列的结构尝试，提出以下对序列集合进丢失分类的问题： 下面有20个已知类别的人工制造的序列（见反面），其中序列标号1-10为A类，11-20为B类。请从中撮特征，构造分类方法，并用这些已知类别的序列，衡量你的方法是否足够好。然后用你认为满意的方法对别外存0个未标明类别的人工序列（标号21-40）进行分类把结果用序号（按从小到大的顺序）标明它们的类别（无法分类的不写入）：A类 ；B类 。
1）请详细描述你的方法，给出计算程序。如果你部分地使用了现成的分类方法也要将方法名称准确注明。
2）在同样网址的数据文件Nat-model-data中给出了182个自然DNA序列，它们都较长。用你的分类方法对它们进行分类，像1）一样地给出分类结果。提示：衡量分类方法优劣的标准是分类的正确率，构造分类方法有许多途径，例如提取序列的某些特征，给出它们的数学表示；几何空间或向量空间的元素等，然后再选择或构造适合这种数学表示的分类方法；又例如构造概率统计模型，然后再用统计方法分类等。
Art-model-data
1.aggcacggaaaaacgggaagaacggaggaggacttggcacggcagtacacggaggacgaggtaaaggag
gcgtgtctacggccggaagtgaagggggatatgaccgcttgg
2.cggaggacaaacgggatggcggtattggaggtggcggactgttcggggaattattcggtttaaacggga
caaggaaggcggctggaacaaccggacggtggcagcaaagga
3.gggacggatacggattctggccacggacggaaaggaggacacggcggacatacacggcggcaacggacg
gaacggaggaaggaggggcggcaatcggtacggaggcggcgga
4.atggataacggaaacaaaccagacaaacttcggtagaaatacagaagcttagatgcatatgttttttaa
ataaaatttgtattattatggtatcataaaaaaaggttgcga
5.cggctggcggacaacggactggcggattccaaaaacggaggaggcggacggaggctacaccaccgtttc
ggcggaaaggcggagggctggcaggaggctcattacggggag
6.atggaaaattttcggaaaggcggcaggcaggaggcaaaggcggaaaggaaggaaacggcggatatttcg
gaagtggatattaggagggcgggaataaaggaacggcggcaca
7.atgggattattgaatggcggaggaagatccggaataaaatatggcggaaagaacttgttttcggaaatg
gaaaaaggactaggaatcggcggcaggaaggatatggaggcg
8.atggccgatcggcttaggctggaaggaacaaataggcggaattaaggaaggcgttctcgcttttcgaca
aggaggcggaccataggaggcggattaggaacggttatgagg
9.atggcggaaaaaggaaatgtttggcatcggcgggctccggcaaactggaggttcggccatggaggcgaa
aatcgtgggcggcggcagcgctggccggagtttgaggagcgcg
10.tggccgcggaggggcccgtcgggcgcggatttctacaagggcttcctgttaaggaggtggcatccagg
cgtcgcacgctcggcgcggcaggaggcacgcgggaaaaaacg
11.gttagatttaacgttttttatggaatttatggaattataaatttaaaaatttatattttttaggtaag
taatccaacgtttttattactttttaaaattaaatattatt
12.gttaattactttatcatttaatttaggttttaattttaaaatttaatttaggtaagatgaatttggtt
tttttaaggtagttatttaattatcgttaaggaaagttaaa
13.gtattacaggcagaccttatttaggttattattattatttggattttttttttttttttttttaagtt
aaccgaattattttatttaaagacgttacttaatgtcaatgc
14.gttagtcttttttagattaaattattagattatgcagtttttttacataagaaaatttttttttcgga
agttcatattctaatctgtctttattaaatcttagaagtatta
15.gtattatatttttttatttttattattttagaatataatttgaggtatgtgtttaaaaaaaaaatttt
tttttttttttttttttttttttttttaaaatttataaatttaa
16.gttatttttaaattttaattttaattttaaaatacaaaatttttacttttctaaaattggtctctgga
tcgataatgtaaacttattgaatctatagaattacattattgat
17.gtatgtctatttcacggaagaatgcaccactatatgattgaaaattatctatggctaaaaaccctcag
taaaatcaatccctaaacccttaaaaaacggcggcctatccc
18.gttaattatttattccttacgggcaattaattatttattacggttttatttacaatttttttttttgt
cctatagagaaattacttacaaaacgttattttacatactt
19.gttacattatttattattatccgttatcgataattttttacctcttttttcgctgagtttttattctt
actttttttcttctttatataggatctcatttaatatcttaa
20.gtatttaactctctttactttttttttcactctctacattttcatcttctaaaactgtttgatttaaa
cttttgtttctttaaggattttttttacttatcctctgttat
21.tttagctcagtccagctagctagtttacaatttcgacaccagtttcgcaccatcttaaatttcgatcc
gtaccgtaatttagcttagatttggatttaaaggatttagattga
22.tttagtacagtagctcagtccaagaacgatgtttaccgtaacgtqacgtaccgtacgctaccgttacc
ggattccggaaagccgattaaggaccgatcgaaaggg
23.cgggcggatttaggccgacggggacccgggattcgggacccgaggaaattcccggattaaggtttagc
ttcccgggatttagggcccggatggctgggaccc
24.tttagctagctactttagctatttttagtagctagccagcctttaaggctagctttagctagcattgt
tctttattgggacccaagttcgacttttacgatttagttttgaccgt
25.gaccaaaggtgggctttagggacccgatgctttagtcgcagctggaccagttccccagggtattaggc
aaaagctgacgggcaattgcaatttaggcttaggcca
26.gatttactttagcatttttagctgacgttagcaagcattagctttagccaatttcgcatttgccagtt
tcgcagctcagttttaacgcgggatctttagcttcaagctttttac
27.ggattcggatttacccggggattggcggaacgggacctttaggtcgggacccattaggagtaaatgcc
aaaggacgctggtttagccagtccgttaaggcttag
28.tccttagatttcagttactatatttgacttacagtctttgagatttcccttacgattttgacttaaaa
tttagacgttagggcttatcagttatggattaatttagcttattttcga
29.ggccaattccggtaggaaggtgatggcccgggggttcccgggaggatttaggctgacgggccggccat
ttcggtttagggagggccgggacgcgttagggc
30.cgctaagcagctcaagctcagtcagtcacgtttgccaagtcagtaatttgccaaagttaaccgttagc
tgacgctgaacgctaaacagtattagctgatgactcgta
31.ttaaggacttaggctttagcagttactttagtttagttccaagctacgtttacgggaccagatgct
ag
ctagcaatttattatccgtattaggcttaccgtaggtttagcgt
32.gctaccgggcagtctttaacgtagctaccgtttagtttgggcccagccttgcggtgtttcggattaaa
ttcgttgtcagtcgctctrtgggtttagtcattcccaaaagg
33.cagttagctgaatcgtttagccatttgacgtaaacatgattttacgtacgtaaattttagccctgacg
tttagctaggaatttatgctgacgtagcgatcgactttagcac
34.cggttagggcaaaggttggatttcgacccagggggaaagcccgggacccgaaccccagggctttagcg
taggctgacgctaggcttaggttggaacccggaaa
35.gcggaagggcgtaggtttgggatgcttagccgtaggctagctttcgacacgatcgattcgcaccacag
gataaaagttaagggaccggtaagtcgcggtagcc
36.ctagctacgaacgctttaggcgcccccgggagtagtcgttaccgttagtatagcagtcgcagtcgcaa
ttcgcaaaagtccccagctttagccccagagtcgacg
37.gggatgctgacgctggttagctttaggcttagcgtagctttagggccccagtctgcaggaaatgccca
aaggaggcccaccgggtagatgccasagtgcaccgt
38.aacttttagggcatttccagttttacgggttattttcccagttaaactttgcaccattttacgtgtta
cgatttacgtataatttgaccttattttggacactttagtcgcggtagcc
39.ttagggccaagtcccgaggcaaggaattctgatccaagtccaatcacgtacagtccaagtcaccgttt
gcagctaccgtttaccgtacgttttggacactttagtttgggttac
40.ccattagggtttatttacctgtttattttttcccgagaccttaggtttaccgtactttttaacggttt
acctttgaaatttttggactagcttaccctggatttaacggccagttt