基于特征向量的宏基因组测序序列分类算法研究-计算机应用技术专业论文.docx

研究生优秀毕业论文 万方数据 万方数据 中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名： j氐遮 签字日期： 印i!)_r孑厂 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入《中 国学位论文全文数据库》等有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内 容相一致。 必威体育官网网址的学位论文在解密后也遵守此规定。 | 甩公开 口必威体育官网网址(——年) 作者签名： ：暨墅1氐 导师签名： 主拿童 签字日期： 2蕾j寸．丁．2y 签字目期：2竺!查!生：婴 万方数据 万方数据 摘要摘要 摘要 摘要 宏基因组测序序列分类问题是宏基因组学研究的一个重点问题。用实验方 法进行分类代价高且速度慢，故利用分类算法进行分类的计算手段成为了一种 趋势。主流的分类算法有基于比对的和基于结构的两类方法，前者需要和己知 基因组进行比对，后者只需要特征向量信息即可。然而后者在低分类层次上的 分类精度仅为60％左右，并且在大规模数据集上的时间开销也太大。基于结构 的分类算法又有有监督和无监督之划分，我们研究基于结构的有监督分类算法。 本文设计针对宏基因组数据的特征向量提取方法，提出面向多物种、低分类层 次的高精度快速宏基因组分类算法。主要工作包括： 1．宏基因组数据的特征向量提取方法 针对宏基因组测序序列的结构特点，结合马尔可夫模型的概率转移矩阵性 质，提出了一种基于马尔可夫模型的特征提取方法，得到了关于测序序列的特 征向量集，验证了新提取的特征向量在不同的测序物种之间的区分特性，应用 基于互信息选择的降维方法对特征向量进行降维处理。将新提出的方法和基于 k-mer频率信息的特征提取方法应用到LIBSVM分类算法中，进行分类性能比 较。实验结果表明，LIBSVM算法使用新方法产生的特征向量比使用基于k-mer 频率信息产生的特征向量在分类精度上高出2％～3％，且分类运行时间也提高了 4～5倍。 2．基于特征向量的SVM分类算法MarkovBinning 首先，对己知物种的特征向量集进行预处理，过滤掉噪声数据。我们定义 了一种新的相似性度量方法KLDist距离，计算出中心特征向量进行噪声数据过 滤，将过滤后的特征向量集作为SVM算法的初始训练集。为了加快训练过程， 采用变步长的网格有哪些信誉好的足球投注网站法，改进了关于惩罚系数C和核函数参数，，的最优参数 对(C，y)的寻优方法。最后，使用提出的MarkovBinning算法对测序序列进行分 类。实验结果表明，与TACOA算法、AbundanceBin算法和MetaCluster算法相 比，我们的算法在分类精度上平均高出10％，且算法运行时间明显减少。 关键词：测序序列特征向量马尔可夫模型降维参数优化SVM算法 摘要 II AbstractABSTRACT Abstract ABSTRACT Metagenomic sequence binning is a fundamental question for metagenomic studies．The experimental methods require hi曲operating cost and slow speed for classify massive sequences．Therefore，computing methods which use binning algorithms have been a new trend for binning these sequences．Main binning algorithms may be classified as alignment-based or composition-based methods． Since the former needs the whole sequence information of known genome for alignment，the latter only needs feature vector information．However,existing composition—based method