DNA序列的分类问题.doc

DNA序列的分类问题摘要本文给出了关于对DNA序列集合如何进行分类问题的解决方案。主要使用了Matlab软件对问题进行建模及运算，运用了聚类分析及判别分析的方法对数据进行处理。在对原始数据的处理和转换方面，使用了C#编写了相关代码，程序完成的主要任务是提取A、T、C、G在各个DNA序列集合中分别出现的频率，然后将这四个频率值作为每个DNA序列集合的特征向量，在Matlab中对其进行聚类分析，并利用分类结果，对未分类的DNA序列集合进行分类预测。1引言 随着人类社会信息和知识总量的不断膨胀，如何有效地管理和利用这些信息成为人们越来越关注的问题。快速增长的海量数据，它们存放在大型和大量的数据存储库中。如果没有强有力的工具，那么这些收集在大型数据存储库中的数据就会变成“数据坟墓”，从而出现数据丰富、信息贫乏的现象，而这些数据也难以被有效地利用并为人们的决策提供强有力的支持。数据挖掘技术正是在这种扩大的数据和贫乏的信息之间架起的一座桥梁，它的主要工作就是利用数据挖掘工具进行数据分析，发现重要的数据模式，对商务策略、知识库、科学和医学研究做出巨大贡献。1 聚类分析是数据挖掘领域里经常使用的基本方法之一，它是将数据对象分成类或簇的过程，使得同一个簇的对象之间具有很高的相似度，而不同簇中的对象高度相异。相异度根据描述对象的属性值评估，通常使用距离变量。2在本文中，主要使用聚类分析对DNA序列进行分类。1. 1需要解决的问题2000年6月，人类基因组计划中DNA全序列草图完成，2002年完成精确地全序列图。而DNA序列是由A、T、C、G四个字符按一定顺序排成的长约30亿的序列。但人们除了知道这四个字符表示四种碱基之外，对DNA序列所包含的其他信息却几乎一无所知。因此，充分发掘DNA序列的结构对于理解DNA全序列有着十分重要的意义。该项目现有20个已知类别的人工制造DNA序列，其中序列标号110 为A类，11-20为B类。现在需要从中提取特征，构造分类方法，可以利用这些已知类别的序列，衡量所使用的分类方法是否足够好。然后用该方法，对另外20个未标明类别的人工序列进行分类预测。2. 2数据集本项目所采用的数据集来自于2000年网易杯全国大学生数学建模竞赛题目，题目中给出了20个已知类别的人工制造DNA序列，前10个为A类，后10个为B类。并且给出了20个未知分类的人工序列进行分类预测。数据文件见附录art-model-data.txt3. 3 对数据的预处理由于原始数据均为一连串的A、T、C、G的字符组合，要对其进行数据挖掘，就需要对原始数据进行预处理，即查看其中是否存在异常值、错误值和空缺等情况，并对上述情况进行相应的处理。14数字特征的提取通过编写C+程序，来得到每一条DNA中所包含的A、T、C、G的碱基数量以及该DNA总的碱基数，从而得到每条DNA中A、T、C、G在序列中出现的频率及序列总长度，分别记为。程序代码如下：将40条DNA序列应用该程序进行处理，最终得到如下结果：序号ATCG总数1331519441112301718461113307245011144732122011152612264711163914144411173921114011183121184111192317234811110201530451111139555111101236553161101328571114110143355913110153271071101640519101101739292715110183255131011019246216811020226219711021314122191132230232526105231819263910224224722221152526232432105262544242111427242421351042830521718117291519224510130312726231073127402025112321936252911033303721231113424172437102353521223510336242232271053722212634104382651202011739292530221064023502320116其中，用红色标记出来的组，第22、32、37组均出现除A、T、C、G外的字符，这可能是由于数据录入时的人工失误造成。对于这三组数据，本文采用将错误字符忽略的办法，即DNA序列总数使用A、T、C、G四个字符出现的总数和，将错误字符的个数忽略。将上述表格在EXCEL中进行计算，求出每条DNA中A、T、C、G出现的概率，即得到下表：序号PAPTPCPG10.29730.13510.17120.396420.27030.15320.16220.414430.27030.06310.21620.450540.42340.28830.10810.180250.23420.10810.23420.423460.35140.12610.12610.396470.35140.18920.09910.360480.27930.18920.16220.369490.20720.15320.20720.4324100.18020.13510.27030.4054110.35450.50000.04550.1000120.32730.50000.02730.1455130.25450.51820.10000.1273140.30000.50000.08180.1182150.29090.64550.00000.0636160.36360.46360.08180.0909170.35450.26360.24550.1364180.29090.50000.11820.0909190.21820.56360.14550.0727200.20000.56360.17270.0636210.27430.36280.19470.1681220.28570.21900.23810.2476230.17650.18630.25490.3824240.19130.40870.19130.1913250.24760.21900.22860.3048260.21930.38600.21050.1842270.23080.23080.20190.3365280.25640.44440.14530.1538290.14850.18810.21780.4455300.28970.25230.24300.2150310.24110.35710.17860.2232320.17270.32730.22730.2636330.27030.33330.18920.2072340.23530.16670.23530.3627350.33980.20390.21360.3398360.22860.20950.30480.2571370.21150.20190.25000.3269380.22220.43590.17090.1709390.27360.23580.28300.2075400.19830.43100.19830.17242相关工作对40条DNA序列提取了数字特征之后，首先对前20条进行聚类，依据已有分类和聚类结果进行比较，检验聚类的准确率。然后利用该聚类结果，再对后面20条进行判别分析，预测其类别。2.1基于距离聚类的方法聚类的方法有很多种，比如基于划分的方法，基于层次的方法，基于密度的方法，基于网格的方法，基于模型的方法等等。本文采用基于距离聚类的方法对数据进行聚类分析。由于样本点数据集中的变量（即每条DNA中A、T、C、G出现的概率）为定距变量，因此，在该样本点的聚类分析中，本文采用定距变量之间的距离度量。分别使用欧式距离、标准化欧式距离、马氏距离、曼哈顿距离等距离来得到20个样本点之间的距离。而余弦距离和相似距离适合于定比变量，因此在这里不采用。2.2定义欧氏距离 假设有两个n维样本和，则它们的欧氏距离为： 欧氏距离是最常用的距离度量。2.3定义马氏距离假设共有n个指标，第i个指标共测得m个数据（要求mn）：则可以得到阶的数据矩阵，每一行是一个样本数据。阶数据矩阵X的阶协方差矩阵记作。两个n维样本和的马氏距离如下：马氏距离考虑了各个指标量纲的标准化，是对其他几种距离的改进。马氏距离不仅排除了量纲的影响，而且合理考虑了指标的相关性。2.4定义标准化欧氏距离假设有两个n维样本和，则它们的标准化欧氏距离为：其中，D表示n个样本的方差矩阵，,表示第j列的方差。2.5定义曼哈顿距离 假设有两个n维样本和，则它们的曼哈顿距离为： 曼哈顿距离也是一种常见的距离度量。2.6定义聚类方法常用的聚类方法主要有以下几种：最短距离法、最长距离法、中间距离法、重心法等。在本文中，在用上述四种距离得到样本点之间的距离后，采用最短距离法对样本点进行聚类，并创建聚类树。对用不同距离创建好的聚类，利用matlab中cophenet函数计算聚类树信息与原始数据的距离之间的相关性，这个值越大越好。最终选择该值最大的距离度量作为聚类的距离度量，并编写程序对样本进行聚类。 3项目实施 在对样本数据集进行预处理后，编写matlab程序对样本中的前20个DNA序列进行聚类分析。同时，还可以使用向量内积的方法以及神经网络的方法来对这20个样本进行分类。本文将给出三种方法的分类结果，来进行比较。3.1使用聚类的方法 在Matlab中编写如下代码： 对20个样本数据分别用四种距离进行聚类，得到四种距离的聚类树信息与原始数据的距离之间的相关性如下： t1 = 0.8632 t2 = 0.8605t3 = 0.8922t4 = 0.8358由上可知，t3最大，所以，我们采用马哈尔距离进行聚类。采用马哈尔距离进行聚类，得到如下结果：b = 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2从结果来看，第一类只有一个，与实际相差太大，故采用欧式距离进行聚类。结果如下：b = 1 1 1 2 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2可见，用欧式距离进行聚类，与原始分类契合度较好。在Matlab中再对其进行判别分析，代码如下：得第21-40序列分类如下：class = 2 1 1 2 1 2 1 2 1 2 2 1 2 1 2