Discipline/ Spécialité : INFORMATIQUE0图尔大学0MIPTIS研究生院0图尔大学基础和应用计算机实验室（EA 6300）0论文提交日期：2019年3月20日0Shivani SHAH0学科/专业：计算机科学0以获得图尔大学博士学位0图尔大学博士学位：图形稀疏化和无监督机器学习在宏基因组分箱中的应用0论文指导：0VENTURINI Gilles教授，图尔大学0评阅人：LEBBAH Mustapha，巴黎第13大学高级讲师；TOUZETHélène，CNRS维勒纳夫-达斯克研究主任0评审委员会：0BOUALI Fatma，里尔大学教授；LARGERON Christine，圣艾蒂安大学教授；LEBBAHMustapha，巴黎第13大学高级讲师；SUBLEMONTIERJacques-Henri，CEA萨克莱工程师研究员；TOUZETHélène，CNRS维勒纳夫-达斯克研究主任；VENTURINI Gilles，图尔大学教授30致谢0这篇论文得以完成，离不开许多人的支持。在这里，我有机会感谢你们每一个人。0首先，我要感谢我的导师：Jacques-Henri SUBLEMONTIER，Gilles VENTURINI和FatmaBOUALI。感谢你们接受我进行这个论文的研究，并让我接触到研究的世界。你们塑造了我今后研究的方式，从提出想法到批判性地分析结果。你们对于解决具有挑战性的研究问题的不懈热情和在困难面前坚持的乐观态度将永远激励着我。但最重要的是，感谢你们每次我在提供结果方面落后时对我的耐心。0感谢Christine LARGERON女士、Mustapha LEBBAH先生和HélèneTOUZET女士同意成为我的评审委员会成员。希望阅读我的论文没有给你们带来太多困扰，而是一次愉快的阅读体验。0接下来，我要感谢CEA部门主任。还有LADIS主任Antony LARUE和LoreneALLANO。感谢你们接受我在实验室做博士学位，并为我完成论文提供了额外的两个月时间。我还要感谢StephaneGAZUT，他向我介绍了宏基因组学的课题，并允许我的论文成为该项目的一部分。0特别感谢实验室和大学的秘书处，尤其是Florence CHEDAUTE和IsabelleFOULON。由于我在法语方面的语言能力有限，你们在各个环节上的指导非常有帮助。同时，我很高兴能与实验室的每个人一起工作。有机会讨论各种想法，感谢你们在共享集群时对我的忍耐！我还要感谢与我一同走过这段旅程的实验室其他博士生们。0与午餐休息时间与MiddayEaters的分享使我的日子变得更好。感谢你们对世界上每一个可能的话题的对话，咖啡休息和足球晚上。这些回忆将永远留在我心中。0我要提到每天都在坚持的人。首先要提到我的办公室同事Andrey。与你共享办公室、喝茶和讨论想法是我的荣幸。特别要提到Sandra，你在这个旅程中一直是我的朋友，教会了我很多关于一切的事情。谢谢Meritxell，感谢你一直的支持和指导我度过这三年。然后我要提到我的犯罪搭档Vincent。感谢你与我讨论从宏基因组学到音乐的想法，与我一起解决研究问题，并帮助我避免使用公共交通工具。40致谢0没有你们的支持，我无法完成这篇论文。还要特别提到实验室中一直陪伴着我的其他人，包括Marisnel、Arnaud、Regis、Joelle和Oudom。0有几位实验室外的人以各种方式对这篇论文做出了贡献。感谢Akhil说服我从事研究。还要特别感谢Ashish，他一直像兄弟一样陪伴着我。还要感谢Ashwin，他激励我并监督我的工作习惯。还要感谢Nita姐姐、Rita姐姐和Kirtan先生，他们一直对我保持信任。感谢巴黎的BAPS团队，与你们在一起让我把这个城市当作我的家。0现在，我要向我的家人表示无尽的感激：妈妈、爸爸和Kajol。感谢你们从一开始就关注我们的教育，强调其价值，并为我们提供舒适的生活。因为有你们，我才能够首先攻读博士学位。没有提到我的Gurus，HDH Pramukh Swami Maharaj和HDH Mahant SwamiMaharaj，我的致谢将是不完整的。你们激励我攻读博士学位，通过信件在各个阶段支持我，你们所教导的价值观将引导我在生活中走向正确的方向。0最后，我要向那些对我的学术之旅做出贡献但我可能没有在这里提到的人道歉。谢谢你们。50致谢60致谢70摘要0元基因组学是生物学领域中研究微生物群落在其自然环境中的基因组内容的领域。本论文中使用的元基因组数据是由产生短DNA片段（reads）的测序技术产生的。这些片段来自样本中所有物种的基因组，其数量可以从几千到几百万不等。数据分析的一个关键步骤是reads的聚类，也称为binning。在这个聚类任务中，需要形成一些组（称为bins），使得每个组都由来自同一物种（或同一属）的reads组成。传统的方法是在较长的序列上进行这个步骤，这些序列称为contigs，它们是从预先组装的步骤中得到的，这样可以大大减少需要聚类的序列数量，但可能会产生所谓的嵌合序列。在对reads进行binning时，其中一个问题主要与数据集的庞大规模有关。传统的方法在reads上进行聚类会对计算资源造成很大负担。因此，有必要开发新的可扩展的binning方法。0在本论文中，我们提出了一种演化的方法来进行binning。我们将我们的工作定位在基于组成（使用短k-mer）的binning方法中，并在完全无监督的情况下进行。为了降低binning任务的复杂性，我们提出了预先过滤数据关联的方法。该方法的开发分为两个阶段。首先，我们在较小的元基因组数据集上评估了方法的性能（由几千个数据点组成）。然后，我们将该方法适应于更大的数据集（由数百万个数据点组成），并使用相似性敏感的索引方法（LSH）。本论文有三个主要贡献。0首先，我们提供了一系列多样的数据（reads）关联过滤算法，通过邻近图来捕捉reads之间最相关的关系，以进行binning任务。然后，我们利用这些图上的社区检测算法来识别感兴趣的reads组。我们在三个元基因组数据集上进行了探索性研究，使用了多个邻近图和社区检测算法。根据这些研究结果，80摘要0我们提出了一种名为ProxiClust的流水线方法，将kNN类型图的构建与Louvain社区检测算法相结合。0其次，为了解决可扩展性问题并处理更大的数据集，我们用基于相似性的敏感哈希表替换了流水线中使用的相似性矩阵，该哈希表是通过LSHSim-Hash方法构建的。我们提出了两种从哈希表构建接近度图的策略：1）微簇图和2）近似kNN图。这些图的性能和限制已在大型MC数据集上进行了评估和讨论。基于这项研究，我们认为相互kNN图是最适合大型数据集的接近度图。这个提议也在国际挑战赛CAMI的参考宏基因组序列数据上进行了评估和确认。0最后，我们研究了用于构建更高质量哈希表的替代哈希方法。我们引入并利用了依赖数据的哈希方法ITQ，并提出了两种变体：正交（ITQ-OrthSH）和非正交（ITQ-SH）。这些哈希方法已在现有的大规模读取数据上进行了评估和讨论。0关键词：宏基因组数据分析，组合分组，聚类，ProxiClust，接近度图，社区检测，K最近邻图（KNN），Louvain算法，局部敏感哈希（LSH），Sim-hashLSH，迭代量化哈希（ITQ），近似最近邻图（AKNN），微簇图，相互KNN，MC数据集，CAMI90摘要100摘要110摘要0宏基因组学是生物学领域中研究微生物群落基因组内容的学科，直接在其自然环境中进行研究。宏基因组数据是通过测序技术生成的，该技术可以从环境样本中识别基因组。生成的数据由DNA的短片段（称为reads）组成，这些片段来自样本中存在的所有物种的基因组。数据集的大小范围从数千到数百万个reads。宏基因组数据分析的一个步骤是对reads进行分组。分组是为了形成组（称为bins），每个组由可能来自同一物种或物种家族的reads组成。在宏基因组文献中，这基本上被视为聚类任务。分组中的一个挑战是由于数据集的大规模而产生的。该方法在执行任务时需要大量的计算资源。因此，需要开发可扩展到大型数据集的分组方法。0在本论文中，我们通过提出一种可扩展的方法来进行分组处理来解决这个问题。我们将我们的工作定位在基于组合的分组方法（使用短的kmer）和完全无监督的环境中。为了降低分组任务的复杂性，我们提出了在聚类之前对数据进行稀疏化的方法。该方法的开发分为两个步骤。首先，我们在较小的宏基因组数据集上评估了这个想法（由几千个点组成）。在第二步中，我们提议使用基于相似性索引方法（LSH方法）将这种方法扩展到更大的数据集（由数百万个点组成）。论文有三个主要贡献。0首先，我们提出了在聚类之前使用接近度图对数据进行稀疏化的想法。接近度图是在数据上构建的，以捕捉对聚类有关的数据点之间的成对关系。然后，我们利用这些图上的社区检测算法来识别数据中的聚类。我们在三个宏基因组数据集上进行了一项探索性研究，使用了几种接近度图和社区检测算法。基于这项研究，我们提出了一种名为ProxiClust的方法，使用KNN图和Louvain社区检测来进行分组处理。0最后，我们研究了构建质量更好的哈希表的替代哈希方法。我们包括了一种数据相关的哈希方法ITQ和Sim-hash的正交版本。我们引入了两种新的数据相关的哈希方法，命名为ITQ-SH和ITQ-OrthSH。所有哈希方法都已根据它们对具有高精度和召回率的MC数据集的哈希能力进行了评估。120摘要0其次，为了将这种方法扩展到更大的数据集，管道中的距离矩阵被Sim-hashLSH方法构建的哈希表所取代。我们引入了两种从哈希表构建接近性图的策略：1）微簇图和2）近似k最近邻图。这些图的性能已在大型MC数据集上进行了评估。这些图的性能和局限性进行了讨论。0关键词：宏基因组数据分析，组成分箱，聚类，ProxiClust，接近性图，社区检测，K最近邻图（KNN），Louvain算法，局部敏感哈希（LSH），Sim-hashLSH，迭代量化哈希（ITQ），近似最近邻图（AKNN），微簇图，Mutual-KNN，MC数据集，CAMI0将Mutual-KNN引入适当的接近性图导致了管道中的新挑战。首先，由于Mutual-KNN图中的组件数量较高，生成了大量的聚类。因此，为了获得适当数量的聚类，需要制定一种策略来合并相似的聚类。此外，需要设计一种从哈希表构建Mutual-KNN图的方法。这将完成大型数据集的ProxiClust管道。0摘要130摘要140X 数据集 X ∈ R N ×dA datasetRN×d150符号0N 数据集的大小 X X 数据集的数据矩阵 X x 数据点， x ∈ X x i 数据点的第 i 个特征 x d 数据点的维度 x D 数据点在 X中的距离矩阵 C X 由聚类算法提供的聚类 G 无向图 V 图 G 的顶点集 v i 图 G 中的节点 E 图 G 的边集 e ij 连接顶点 v i 和 v j的边，属于 E C 图 G 的社区划分 k KNN 和 Mutual-KNN 图中的邻居数 k ′ K-means 和 K-medoids 的聚类数输入参数 K kmer 的长度Q 图 G 的模块度 ε ε -NN 图的 epsilon 参数 S Net-similarity，Af�nity Propagation 的优化函数 K Af�nity Propagation确定的示例集合 H 用于计算数据的二进制编码的哈希函数族 y 通过哈希得到的数据点 x 的二进制编码的向量形式 b 二进制编码的长度 y通过哈希方法生成的投影矩阵 G 二进制编码的矩阵， Y ∈ R b × N0bsize p 桶 p 的大小（点的数量）来自哈希表 CTMAX 构建微簇图的最大微簇数 nBuckets哈希表中填充的桶数 sBuckets 哈希表中填充的桶数 enc ( ∙ ) 将输入值投影到 1 或 0 的取整函数 sgn( ∙ ) 将输入值投影到 1 或 -1 的取整函数 sim ( ∙ , ∙ ) 表示空间中两个点之间的相似性的函数 d h ( ∙ , ∙) 计算二进制编码之间的汉明空间距离的函数160符号List of Figures271Introduction291.1Introduction to Metagenomics . . . . . . . . . . . . . . . . . . . . . . . . . .291.2Challenges in Binning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .321.3Contribution of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . .321.4Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34IState of the Art352State of the Art on Clustering and Metagenomic Binning372.1Clustering Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .372.1.1Basic Notations and Definitions . . . . . . . . . . . . . . . . . . . . .372.1.2Partitional Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . .382.1.3Affinity Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . .392.1.4Hierarchical clustering . . . . . . . . . . . . . . . . . . . . . . . . . .422.2Distance Measures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .432.2.1Euclidean. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .442.2.2Cosine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .442.2.3Spearman Footrule Distance. . . . . . . . . . . . . . . . . . . . . .442.2.4Total Variation Distance . . . . . . . . . . . . . . . . . . . . . . . . .442.3Evaluation Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .452.4Metagenomics Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . .462.5Clustering for Metagenomic Binning . . . . . . . . . . . . . . . . . . . . . .502.5.1Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .502.5.2MyCC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50170目录0表格列表 2402.5.3 LSH-SNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53CONTENTS2.6Datasets and their properties. . . . . . . . . . . . . . . . . . . . . . . . . .552.6.2Synthetic Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . .56IIProxiClust Pipeline593.1Proximity Graphs and Community Detection . . . . . . . . . . . . . . . . .613.1.2Proximity Graphs to consider . . . . . . . . . . . . . . . . . . . . . .613.1.4KNN Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .623.1.6Relative Neighbourhood Graph. . . . . . . . . . . . . . . . . . . .633.1.8Louvain Community Detection . . . . . . . . . . . . . . . . . . . . .643.1.10 Label Propagation. . . . . . . . . . . . . . . . . . . . . . . . . . . .663.1.11 Infomap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .673.1.12 Walktrap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .683.2Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .703.2.1Overall Description . . . . . . . . . . . . . . . . . . . . . . . . . . . .703.3Properties and expectations . . . . . . . . . . . . . . . . . . . . . . . . . . .703.4Evaluation Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .724Results with First pipeline754.1Experimental details. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .754.2Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .764.2.1Objective of the experiment . . . . . . . . . . . . . . . . . . . . . . .764.2.2Protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .764.2.3Results with graphs. . . . . . . . . . . . . . . . . . . . . . . . . . .784.2.4Discussions and conclusion . . . . . . . . . . . . . . . . . . . . . . .804.3Community Detection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .804.3.2Protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .811802.5.4 元簇 5.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5402.6.1 真实数据集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5502.7 问题陈述和命题概述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5703 ProxiClust描述 6103.1.1 基本符号和定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6103.1.3 最小生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6203.1.5 Epsilon图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6303.1.7 社区检测 . . . . . . . . . . . . . . . . . . . . . . . . . . . 6303.1.9 快速贪婪算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6504.3.1 实验目标 . . . . . . . . . . . . . . . . . . . . . . . 804.3.3Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .814.4Distance Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .864.4.2Protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .864.4.4Discussions and conclusion . . . . . . . . . . . . . . . . . . . . . . .874.5.1Objective of the experiment . . . . . . . . . . . . . . . . . . . . . . .884.5.3Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .884.6Comparative evaluation with state of the art. . . . . . . . . . . . . . . . .894.6.2Protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .894.6.4Discussions and conclusion . . . . . . . . . . . . . . . . . . . . . . .90IIIProxiClust for Large datasets935.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .955.2.1Notation and General Hashing framework . . . . . . . . . . . . . .975.2.2Sim-Hash: random hyperplane based approach . . . . . . . . . . .985.3Learning Proximity Graphs from Sim-hash LSH. . . . . . . . . . . . . . .995.4Microclusters graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1015.4.1Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1015.4.2ProxiClust on Microclusters graph . . . . . . . . . . . . . . . . . . .1015.4.3Strategies to build microclusters with hashing . . . . . . . . . . . .1015.4.4K-microcluster approach . . . . . . . . . . . . . . . . . . . . . . . . .1035.4.51-microcluster approach . . . . . . . . . . . . . . . . . . . . . . . . .1045.5Approximate K Nearest Neighbor Graph (AKNN) . . . . . . . . . . . . . .1055.5.1Motivation for using AKNN. . . . . . . . . . . . . . . . . . . . . .1055.5.2Construction of AKNN. . . . . . . . . . . . . . . . . . . . . . . . .1055.6Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .107190目录04.3.4 讨论和结论 . . . . . . . . . . . . . . . . . . . . . . . 8204.4.1 实验目标 . . . . . . . . . . . . . . . . . . . . . . . 8604.4.3 使用不同距离的结果 . . . . . . . . . . . . . . . . . . . . 8704.5 K-mer 选择 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8804.5.2 协议 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8804.5.4 讨论和结论 . . . . . . . . . . . . . . . . . . . . . . . 8904.6.1 实验目标 . . . . . . . . . . . . . . . . . . . . . . . 8904.6.3 使用最先进的方法的结果 . . . . . . . . . . . . . . . . . . 9004.7 结论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9105 处理大型数据集的方法 9505.2 哈希方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97CONTENTS6Results with Large datasets1096.1Evaluation of Hashing on MC Datasets. . . . . . . . . . . . . . . . . . . .1096.1.1Objective of the experiment . . . . . . . . . . . . . . . . . . . . . . .1096.1.2Protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1106.1.3Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1126.1.4Discussions and conclusion . . . . . . . . . . . . . . . . . . . . . . .1126.2K-microcluster approach - Standard vs. Stratified . . . . . . . . . . . . . . .1136.2.2Protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1136.2.4Discussions and conclusion . . . . . . . . . . . . . . . . . . . . . . .1156.3.1Objective of the experiment . . . . . . . . . . . . . . . . . . . . . . .1166.3.3Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1176.4Analysis on CTMAX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1196.4.2Protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1196.4.4Conclusion for Microclusters graph. . . . . . . . . . . . . . . . . .1216.5.1Objective of the experiment . . . . . . . . . . . . . . . . . . . . . . .1226.5.3Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1236.6Baseline evaluation and Edge Pruning . . . . . . . . . . . . . . . . . . . . .1266.6.1Objective of the experiment . . . . . . . . . . . . . . . . . . . . . . .1266.6.2Protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1266.6.3Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1296.6.4Conclusion for edge pruning and clustering difficulty . . . . . . . .1296.7Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1307Alternative Hashing Methods1317.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1317.2Hashing Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1317.2.1Orthogonal Sim-hash . . . . . . . . . . . . . . . . . . . . . . . . . . .1327.2.2ITQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1332006.2.1 实验目标 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11306.2.3 结果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11406.3 K-microcluster vs. 1-microcluster方法 . . . . . . . . . . . . . . . . . . 11606.3.2 协议 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11606.3.4 讨论和结论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11706.4.1 实验目标 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11906.4.3 结果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12006.5 在近似K最近邻图上的可扩展ProxiClust . . . . . . . 12206.5.2 协议 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12206.5.4 AKNN的结论 . . . . . . . . . . . . . . . . . . . . . . . . . . 125
