微生物组是指一个特定环境或生态系统中全部微生物及其遗传信息，微生物是生命发展过程中重要的生物资源，人的正常生命活动离不开微生物，微生物组研究得到学术界广泛关注。2007年，美国国家卫生研究院（NIT）启动人类微生物群系计划（HMP：Human Microbiome Project），2016年，美国宣布启动“国家微生物组计划”；2017年底，中国科学院启动微生物组计划；微生物组研究已成为各国科学家关注的研究热点。

近年来，利用新一代高通量测序技术，能在较短时间内产出大规模微生物组序列数据，数据量以超越摩尔定律的幅度飞速增长。国内外生物信息领域学者通过对微生物组序列大数据分析，旨在获取具有明确生物学意义的有价值信息。生命从何而来的问题一直困扰着全球的科学家，微生物组序列数据分析是进化分类学中重要的技术手段。多年来，国内外研究学者在微生物的进化分类领域进行了一系列深入研究。16S序列作为分子指标成为微生物进化分类的强有力工具，具备种类少，含量大，分子大小适中，稳定性高、多拷贝、多信息，长度适中的特征，在结构和功能上具有高度的保守性，故常用来标记生物进化距离和亲缘关系。目前美国卫生研究院已对2000种占真细菌总数的50%以上的真细菌的16S序列进行了测序，不同菌属的16S序列同源性为70%~95%，根据同源性则可基本判定真细菌是否为同一菌属。研究发现，由于所有种类细菌中至少有一个16S基因拷贝，且16S基因拷贝序列并一定完全相同，若不同细菌中有两个16S基因序列同源性不高于97%，则可判定他们属于不同的菌种。通过对16S序列的序列比对、同源性分析，可以计算不同菌属和菌种在遗传进化方面的距离，从而判定其遗传关系的远近，绘出进化树，从而达到对微生物进行分类的目的。由于不同区域具备不同的保守性，进化速率难以测定。利用16S序列数据集，进行进化分类分析一直是生物信息领域的难题。

微生物组16S序列数据集为大规模数据，且微生物组序列为非欧式高维空间数据，数据降维成为微生物组序列大数据分析的关键技术。现有的维数约简方法中，PCA、IPCA方法对具有线性结构的数据集处理效果很好，小波、傅里叶变换处理图像的结果也很好。然而这些方法皆忽略了数据的几何结构，缺乏几何上的直观解释。流形学习很好地解决了这个问题，得到学术界广泛关注。流形学习于2000年《Science》杂志提出，成为信息科学领域研究热点。近年来，许多国内外研究学者对流形学习展开了深入研究。

流形学习是数据挖掘、模式识别、生物信息学等领域内数据维度约减的重要方法。流形学习旨在挖掘高维数据中隐藏的保留原始数据的本质特性的低维复杂拓扑结构，从而达到数据维数约简的目的。现有的流形学习算法可大致分为两类：全局方法与局部方法。全局方法旨在保留数据全局的几何拓扑结构，著名的全局流形学习方法有：等距特征映射（ISOMAP，Isometric Feature Mapping）,拓扑约束等距嵌入（TCIE，Topologically Constrained Isometric Embedding）等；局部方法旨在保持数据局部的几何拓扑结构，主要的局部流形学习方法有：局部线性嵌入（LLE，locally linear embedding）,拉普拉斯本征映射（LE，Laplacian Eigenmaps）,保局投影(LPP, locality preserving projections), Hessian本征映射(HE, Hessian Eigenmaps)等。我国研究者在这一领域有着不可忽视的学术影响。其中，清华大学张长水课题组在谱聚类以及基于类标传播(LabelPropagation)的半监督流形学习领域颇有建树，南京大学周志华课题组提出了多流形谱聚类、多类标维数缩减等新研究方向，浙江大学蔡登、何晓飞课题组提出了在黎曼流形上建立高斯混合模型的流形聚类方法。这些方法以及目前国际学界普遍使用的其它主流方法，对本此毕业设计的研究都具有相当的借鉴意义。首先，基因测序的数据种类和数据量异常庞大，常以PB为单位保存，大规模样本的数据分析需要海量计算资源，计算成本高，收效慢。其次，基因组成的空间为非欧式空间，具有较高的全局本征维数，为降低数据量而采用常规的基于欧氏空间距离的抽样方法无法适用。此外，由于基因变异和物种进化的“长尾”分布现象，数据集中的稀有基因型对基因组学研究具有非常重要的意义，使用随机抽样将导致丧失非常重要的原始信息。应用研究能够有效处理大规模数据集，并准确保留其中的稀有类别信息的流形学习方法，将流形学习方法引入大规模基因测序数据分析，为大规模数据分析提供新途径。

2. 研究的基本内容与方案

本次毕业设计研究的基本内容包括两方面：一方面，通过对公开的微生物16S序列参考数据集进行流形建模，16S序列有高度保守区又有可变区，高度保守区反应了物种之间的亲缘关系，可变区反应了物种之间的差异。利用微生物16S序列不同区域数据集，进行聚类分析，再采用流形学习方法投影到低维空间，提取数据空间关键特征，从而分析微生物进化过程中16S序列不同区域的进化趋势差异和进化方向上的偏向。另一方面，利用人体多部位的微生物采样数据，应用到第一部分内容的流形模型，对人体多部位的微生物进行分类，发现微生物在人体多部位之间迁移的规律。

本次毕业设计的研究目标为：分析16S序列的不同区域的进化趋势差异和进化方向上的偏向;将人体多部位的微生物采样数据应用于流形模型，聚类分析各部位微生物物种，发现微生物在人体多部位之间迁移的规律。

本次毕业设计拟采用的技术方案为：使用常用的生物序列数据库，利用BLAST工具进行微生物基因序列比对，获得微生物基因序列的相似性，确定微生物之间的亲缘关系；结合USEARCH工具进行聚类分析；同时研究运用流形学习方法，构建流形学习模型，根据参考数据集训练模型，设计算法解决该模型，并分析算法稳定性与复杂度，不断改进算法以适应于实际需求。接着，对聚类结果进行降维处理，获取16S序列不同区域在密度等方面的明显差异。最后，将人体多部位的微生物采样数据应用到上述模型中，获取各部位微生物序列之间的相似性和差异性，从而获得微生物之间的亲缘关系。基于两微生物亲缘关系近则为同一来源的假设，针对个体不同部位的微生物亲缘关系，运用投票机制，判断人体中多部位中的微生物是否发生迁移，从而发现微生物在人体多部位之间的迁移规律。

[1] Tenenbaum JB, de Silva V and Langford JC. AGlobal Geometric Framework for Nonlinear Dimensionality Reduction. Science290(5500):2319-2323. 2000

[2] Roweis ST and Saul LK. NonlinearDimensionality Reduction by Locally Linear Embedding. Science 290(5500):2323-2326.2000

[3]Xingpeng Jiang, Xiaohua Hu, Tingting He. Time series analysis of microbiomedata regularized by local linear manifold. 2015IEEE International Conference on Bioinformatics and Biomedicine (BIBM), 11/2015