2010研究生数学建模(A题)

全全国国第第七七届届研研究究生生数数学学建建模模竞竞赛赛题目基于SVM和LDA-GA的基因图谱信息提取方法的研究摘要：本文针对提取基因图谱信息的问题，运用浮动顺序搜索算法、RBF支持向量机和遗传线性判别算法（LDA-GA）等方法，在不处理噪声、降噪以及融入其他有价值的信息三种条件下分别建立能够有效提取样本基因图谱信息的模型，并利用样本数据针对每种条件下得到的基因“标签”的分类能力进行测试和分析。针对问题1，首先以Bhattacharyya距离为评价函数，对样本中2000个基因进行无关基因的剔除，得到388个信息基因；然后，在信息基因集合中，根据浮动顺序搜索算法搜索得到35个候选分类特征子集，为问题2中基因标签的筛选提供必要条件。针对问题2，根据样本数据，利用候选分类特征子集对RBF支持向量机进行训练，采用“留一法”和“独立测试实验”对所建支持向量机进行测试。通过对测试结果的分析与评价，筛选出具有最佳分类效果的特征子集，作为基因“标签”。通过实验得到的基因“标签”为7维向量。针对问题3，分析NT_I及NT_Ⅱ两类噪声，建立噪声模型并对样本数据进行降噪处理。运用处理后的样本数据，确定新的基因“标签”。实验结果表明，新的基因“标签”具有更高的分类精度。针对问题4，根据有助于诊断肿瘤的相关信息，利用LDA-GA方法对有价值的生理基因进行筛选得到最优生理基因向量，与候选分类子集组合形成广义候选分类子集，并通过支持向量机对其筛选，确定广义基因“标签”。实验结果表明，广义基因“标签”为4维向量，且具有更佳的分类效果。关键词：Bhattacharyya距离，浮动式顺序搜索算法，RBF支持向量机，NT_I及NT_Ⅱ噪声模型，LDA-GA算法参赛队号队员姓名参赛密码（由组委会填写）2一、问题重述癌症起源于正常组织在物理或化学致癌物的诱导下，基因组发生的突变。而基因在结构上发生碱基对的组成或排列顺序的改变，更改了基因原来的正常分布。因此，探讨基因分布的改变与癌症发生之间的关系具有深远的意义。DNA微阵列是指固定有称之为探针的核苷酸序列的固体基片或膜，它是能够快速、高效地检测DNA片段序列和基因表达水平的新技术。根据核苷酸分子在形成双链时所遵循的碱基互补原则，可以检测出样本中与探针阵列中互补的核苷酸片段，从而得到样本中关于基因表达的信息，即基因表达谱。随着大规模基因表达谱技术的发展，已经获得人类各组织的正常的基因表达谱，为各类病人的基因表达谱提供了参考基准。如果可以在分子水平上利用基因表达谱准确地辨别是否患有肿瘤，对诊断和治疗肿瘤具有重要意义。因为正常人和肿瘤患者均具有其基因的特征表达谱，所以从DNA微阵列测量的成千上万个基因中找出决定样本类别的一组基因“标签”，即“信息基因”，能够从分子水平上准确识别是否患有肿瘤，且为医学诊断、简化实验分析及抗癌药物研制提供便捷和帮助。然而，由于基因数目很大，在判断肿瘤基因标签的过程中，需要剔除掉大量“无关基因”，从而大大缩小需要搜索的致癌基因范围。事实上，在基因表达谱中，一些基因的表达水平在所有样本中都非常接近，可以认为这些基因与样本类别无关，没有对样本类型的判别提供有用信息，反而增加信息基因搜索的计算复杂度，所以首先必须对这些“无关基因”进行剔除，然后有效地提取基因图谱信息得到基因标签。此外，肿瘤是致癌基因、抑癌基因、促癌基因和蛋白质通过多种方式作用的结果，因此在确定肿瘤的基因标签时，应该设法充分利用其他有价值的信息，例如将与临床问题相关的主要生理学信息融合到基因分类研究中。因此，本文需要完成以下几个问题：1．由于基因表示之间存在着很强的相关性，所以对于某种特定的肿瘤，似乎会有大量的基因都与该肿瘤类型识别相关，但一般认为与一种肿瘤直接相关的突变基因数目很少。如何根据上述观点，利用附件中的数据，选择最好的分类因素；2．对于给定的结肠癌数据，如何从分类的角度确定相应的基因“标签”；3．基因表达谱中不可避免地含有噪声，对含有噪声的基因表达谱提取信息时会产生偏差。通过建立噪声模型，分析给定数据中的噪声能否对确定基因标签产生有利的影响；4．在肿瘤研究领域通常会已知若干个信息基因与某种癌症的关系密切，建立融入了肿瘤研究领域中有助于诊断肿瘤信息的确定基因“标签”的数学模型。3二、问题分析基因表达谱作为描绘特定细胞或组织在特定状态下的基因表达种类和丰度信息，能够提供丰富的信息进行正常和患有肿瘤两类样本的辨别，为医学诊断及抗癌药物研制便捷。目前，肿瘤分类领域的一个目标是采用尽可能少的信息基因以获得尽可能高的样本分类准确率，这是因为：(1)选择尽可能少的信息基因意味着尽可能多地去掉了包含在样本中的噪音；(2)意味着减少肿瘤诊断的成本；(3)分类准确率高的信息基因通常与肿瘤的发生发展存在紧密的联系。然而，仅仅采取一种基因选择方法很难选出满足条件的信息基因子集，因此需要进行两个阶段，即初选阶段和复选阶段。初选阶段利用适当的条件限制先从成千上万个基因中选出信息基因，从而大幅降低基因的搜索空间，然后进行复选得到能有效判别正常与患有肿瘤的基因标签。该题首先需要参赛者解决的问题是：根据DNA微阵列测定得到的基因表达谱，采用有效的算法，得到准确辨别正常和患有肿瘤的两类样本的基因标签，并对附件中提供的样本进行准确辨别。另外，基因表达谱中不可避免地含有噪声，会影响基因表达谱的提取，因此需要建立适当的噪声模型对基因标签筛选过程进行优化。最后，由于肿瘤是多种因素共同作用的结果，因此在确定肿瘤标签时，还要充分考虑其他有价值的信息。具体来说，需要考虑的问题如下：1．信息基因的初选---“无关基因”的剔除对于某特定组织的基因表达谱，含有数量庞大的基因，其中绝大部分的基因在正常和患有肿瘤两种状态下的基因表达水平具有相似性，无法对辨别作出贡献。这类基因被称为“无关基因”。对于问题1，首先需要选取一定标准，作为衡量某基因是否为“无关基因”的判断条件，然后对样本的基因表达谱进行筛选，剔除“无关基因”，并利用浮动顺序搜索算法得到候选分类特征子集。2．基因标签的选取与患有肿瘤相关的基因数目可能含有若干个，对于问题2，需要在问题1的处理结果组成的基因子集空间中，选取适当的算法，搜索得到能够准确判断正常或者患有肿瘤的基因标签。能够使用的算法包含：支持向量机、多指标评价模型等。为了得到更为准确的基因标签，避免某次搜索受样本噪声等问题的干扰，可以进行多次搜索，每次均将支持向量机和多指标评价模型相结合进行筛选，通过对结果的分析与评价，筛选出具有最佳分类效果的基因集合，即为基因“标签”。3．噪声模型的引入对于问题3，将噪声干扰考虑到基因表达谱的分析中，分析可能存在的各种噪声，如实验过程中的随机干扰等噪声，如果确定患有肿瘤的基因标签中某基因所占比率很小，那么在受到噪声干扰时则容易产生辨别偏差。而通过引入噪声模型排除或削弱该基因在辨别是否患有肿瘤的过程中的贡献，从而提高了分类的正确性，因此噪声模型的建立可能会对基因标签的确定产生有利的影响。4．在模型中融入肿瘤研究领域中有利信息在肿瘤的研究领域内，已经存在若干有利于构建更完善的确定基因标签的信息，对于问题4，通过完善上述数学模型，将这类信息融入到前面建立的模型中，增强基因标签判4断的准确性。通常我们会想到很多判别模型，比如：Fisher判别法、贝叶斯判别法、支持向量机判别法等模型，在对有助于诊断肿瘤的信息具体分析后，即可尝试建立相应的判别模型。三、模型假设假设一：样本中的数据真实，来源可靠，能够作为检验模型准确性的样本；假设二：样本具有普遍性，能够作为寻找基因“标签”的依据；假设三：样本数据里的噪声具有一般性。5四、符号说明符号含义指定的Bhattacharyya距离的阈值_maxiD有i个基因的特征子集中具有最大评价函数值的基因集合iJD有i个基因特征子集的Bhattacharyya距离,iKxx核函数)1(if分类准确度)2(if被选基因数目“留一法”权值iV基因表达水平iG基因i的表达向量VS协方差矩阵I染色体二进制向量实数向量BS类间散布矩阵WS类内散布矩阵6五、模型的建立与解答5.1问题15.1.1理论分析因为基因表示之间存在很强的相关性，所以对于某种特定的肿瘤，可能会有大量的基因都与该肿瘤类型识别相关。然而，在基因表达谱中，含有大量对样本类别的判别影响很小的基因。这些基因的表达水平在所有样本中都非常接近，不会为样本类型的判别提供有效的信息，反而会增加信息基因搜索的计算复杂度[1]。例如附件中给出的基因表达谱中，某些基因在健康状况正常和患有癌症两个类别里的分布，无论其均值还是方差均无明显差别，对样本类别的判定贡献很小。因此，需要剔除无关基因，缩小搜索的有效范围。作为对基因的初选过程，需要一种适用性强、判别效率较高且容易实现的算法。因此，选择以Bhattacharyya距离为评价函数及浮动顺序搜索算法作为问题1的解决方案。5.1.2基于Bhattacharyya距离和浮动顺序搜索算法的基因分类方法分类错误概率是模式识别中特征有效性的最佳度量，在降维空间中，特征选择的理想目标是达到分类错误概率最小，然而这点往往难于做到。因此，使得错误概率上界最小常常是一种合理的选择[7]。由Chernoff提出的错误概率上界是最小的，称为Chernoff上界。根据Chernoff上界[2,3]得到误差的上边界，即：11ijijPerrorPPpxpxdx（1）其中01，i和j为需要判别的类别，Perror为分类错误概率，积分部分覆盖所有特征空间，并可以等价为：1kijpxpxdxe（2）其中，111111ln22Tijijijijijk，i和j为相应的协方差。当0.5时，分类错误概率误差具有Bhattacharyya边界，并由此时k表达式化简得到基因的Bhattacharyya距离[2]，即：2212221212110.5ln422ijBk（3）上式的Bhattacharyya距离能够度量基因中含有的类别信息量，其由两部分组成，第一项表现了基因在两个类别中分布均值的差异对样本分类的作用；第二项体现了分布方7差的不同对样本分类的作用。这两部分具有相互促进的作用，即使基因在两类不同样本中分布的均值相同，只要分布的方差具有较大差异，仍然可以获得较大的Bhattacharyya距离值。而且，由式（3）可知，当某个基因的Bhattacharyya距离具有较大值时，ke项具有较小值，从而分类错误概率的上界具有较小值。从模式分类[2]的角度看，某个基因的Bhattacharyya距离越大，表示可以利用该基因的信息进行越好的分类。因此，利用Bhattacharyya距离作为衡量指标，能够较好地对样本中基因谱进行初选，剔除无关基因，得到对判别是否患有肿瘤具有帮助的信息基因集合。附件提供的基因表达谱中，共有62个样本，每个样本均含有2000个基因的表达数据。其中，22个样本被诊断为健康状况正常，40个样本被诊断为患有癌症。针对两类样本，对每个基因进行Bhattacharyya距离计算，并作出基因的Bhattacharyya距离分布的直方图，如图1所示。图1候选基因的Bhattacharyya距离分布直方图根据基因所含样本类别信息的多少，选取阈值并将基因分为“信息基因”和“无关基因”两类。设1S为信息基因集合，2S为无关基因集合，则“信息基因”与“无关基因”可以定义如下：12()SBssSBs其中s为基因，Bs为基因s的Bhattacharyya距离，为指定的Bhattacharyya距离的阈值。从图1可知，绝大部分基因的Bhattacharyya距离小于0.1。这些基因在样本中两个类别中的分布的均值和方差均无较大差异，因此可以作为无关基因被剔除。基因表达谱中