稀疏化图和无监督机器学习在宏基因组合并研究中的应用

图稀疏化和无监督机器学习用于宏基因组合并旅游大学博士学校-MIPTISLIFAT-塔基础和应用计算机科学实验室论文提交人：Shivani Shah支持日期：2019年3月20日获得学位：图尔大学博士学科/专业：计算机科学论文指导人：Venturini Gilles教授，图尔大学报告员：LEBBAH Mustapha巴黎第13大学HDR高级讲师TOUZET Hélène，CNRS Villeneuve-d 'Ascq评审团研究总监里尔大学Bouali Fatma教授LARGERON Christine Saint-Étienne LEBBAH Mustapha让·莫内大学教授巴黎第13大学HDR副教授Jacques-Henri CEA SaclayTOUZET Hélène，CNRS Villeneuve-d 'Ascq研究总监Venturini Gilles教授，图尔大学3确认书这篇论文是在许多个人的支持下成为可能的我有机会感谢你们中的一个。首先，我想提到我的主管：雅克-亨利·苏布莱蒙蒂尔、吉勒·文图里尼和法特玛·布阿里。谢谢你接受我的论文并向我介绍研究的世界。你已经塑造了我未来研究的方式，从提出想法到批判性地分析结果。你对寻找具有挑战性的研究问题的解决方案的不懈热情和面对困难时保持乐观的态度将永远激励着我。但最重要的是，感谢你在我交付成果的每一次落后中对我的耐心。感谢Christine LARGERON女士、Mustapha LEBBAH先生和Hélène TOUZET女士同意成为我的评审团成员。我希望阅读手稿不会打扰你太多，是一个愉快的阅读经验。下一个我想感谢CEA的部门主管。也是女士们的头，安东尼·拉鲁和洛琳·阿拉诺。谢谢你接受我在实验室做博士学位，也谢谢你给我额外的两个月来完成我的论文。我还要感谢Stephane Gazut向我介绍了宏基因组学的主题，并允许我的论文成为该项目的一部分。我特别感谢实验室和大学的秘书处，特别是Florence Chedaute和Isabelle Foulon。你的指导通过各种步骤是非常有帮助的，给了我有限的语言技能在法语。和实验室里的每一个人一起工作是我的荣幸。有机会讨论各种想法，并感谢你忍受我，而分享集群!我也想对实验室里所有与我分享这段旅程的其他博士生表示感谢。和中午吃午餐的人分享我所有的午餐面包让我的日子过得更好。谢谢你在世界上每一个可能的话题上的谈话，咖啡烘焙和足球晚会。这些记忆将永远伴随着我。我想提一下那些每天都在忍受的人。首先，我要提到我的办公室伙伴安德烈。我很高兴能和你共用一间办公室，喝茶，讨论想法。特别提到桑德拉，你一直是我的朋友，在这段旅程中，教了我很多关于一切。感谢Meritxell，感谢您在这三年中不断的支持和指导。然后我想提一下我的犯罪搭档文森特。谢谢你讨论从元基因组学到音乐的想法，和我一起解决研究问题，帮助我避免公共交通。带-4已知的基因如果没有你的支持，就不可能完成这份手稿。我还想提一下实验室里一直和我在一起的其他人，他们是Marisnel、Arnaud、Regis、Joelle和Oudom。实验室外有几个人以不同的方式为本文做出了贡献。谢谢你Akhil同意我做研究。我还要特别感谢Ashish，他一直是我的兄弟，一直在那里。也感谢阿什温，激励我，让我检查我的工作服。我还要感谢Nita Didi、Rita Didi和Kirtan爵士，感谢他们一直对我保持信心。我感谢巴黎的BAPS团队，和你们在一起帮助我把这座城市变成了我的家。现在，我非常感谢我的家人：妈妈，爸爸和Kajol。感谢你们从一开始就专注于我们的教育，强调它的价值，并为我们提供舒适的生活。因为你，我一开始就有能力攻读博士学位。如果不提到我的上师，H.D.H. Pramukh Swami Maharaj和H.D.H. MahantSwami Maharaj，我的确认将是不完整的你激励我做这个博士学位，通过不同阶段的信件支持我，你教给我的价值观将使我在生活中朝着正确的方向前进。最后，我想向那些为我的旅程做出贡献的人道歉，但我可能没有在这里提到。谢谢你。5已知的基因已知的基因67摘要宏基因组学是生物学的一个领域，涉及直接在其自然环境中研究微生物群落的基因组内容。本论文中使用的宏基因组学数据对应于产生短DNA片段（读数）的测序技术。这些片段来自样品中存在的所有物种的基因组， 在此合并任务中，必须形成组（称为bins），以便每组由来自相同物种（或属）的读取组成传统的方法包括在较大的序列上进行该步骤，称为重叠群，其来自应用于读取的合并的问题之一特别与数据集的大尺寸有关。应用于读取的传统方法会使执行任务时所需的因此，有必要开发新的可扩展的合并方法。在本文中，我们通过提出一种可扩展的合并方法来解决这个问题。我们将我们的工作定位在基于组合的组合方法（使用短k-mer）和完全无监督的环境中。为了降低合并任务的复杂性，提出了用于预先过滤数据之间的关联的方法。该方法的开发分两个阶段进行。 首先，在较小的宏基因组数据集（由几千个点组成）上对该方法进行评估。在第二步中，我们建议本文有三大贡献。首先，我们提出了一组不同的算法，用于通过这些接近度图是为了捕捉阅读之间最相关的关系而构建的。合并任务。然后，我们在这些图上使用社区检测算法来识别感兴趣的阅读组。在三个宏基因组数据集上使用几种邻近图和社区检测算法进行了探索性研究作为这项研究的结果，摘要8我们提出了一种名为ProxiClust的流水线方法，它将kNN类型图的构造与用于社区检测的Louvain算法相耦合其次，为了我们介绍了两种从哈希表构造邻近图的策略：1）微簇图和2）近似kNN图。在大型MC数据集上测试并讨论了这些图的性能和局限性。在此基础上，我们选择了互kNN图作为最适合大数据集的接近还使用来自国际CAMI挑战的宏基因组参考序列数据对该提议进行了评估和最后，我们研究了构建更高质量哈希表的替代哈希方法。L’approche de hachagedépendante des don- nées这些散列方法已经在可用的大量读取数据上进行了评估和讨论。关键词：元基因组数据分析，合成结合，聚类，近似聚类，邻近图，社区检测，K最近邻图（KNN），鲁汶算法，局部敏感散列（LSH），模拟散列LSH，迭代量化散列（ITQ），近似最近邻图（AKNN），微聚类图，相互KNN，MC数据集，CAMI9摘要摘要1011摘要宏基因组学（英语：Metagenomics）是生物学中直接研究自然环境中微生物群落的基因组含量的领域。宏基因组数据是通过测序技术生成的，该技术从环境样本中鉴定基因组。生成的数据由DNA的短片段（称为读数）组成，这些片段来源于样品中存在的所有物种的基因组。数据集的大小范围从数千到数百万次读取。宏基因组学数据分析的步骤之一在合并组中，将形成这样的组，即每个组由可能起源于同一物种或物种科的读取组成。在宏基因组学文献中，它基本上被视为一项聚类任务。合并的挑战之一是由于数据集的大规模该方法超过了执行任务所需的计算资源需要开发可扩展到大型数据集的合并方法。在本论文中，我们通过提出一种可扩展的方法来执行合并来解决这个问题。我们将我们的工作定位在基于合成的合并方法（使用短kmers）和完全无监督的环境中。为了降低合并任务的复杂性，提出了在聚类之前执行数据稀疏化的方法。该方法的开发分两个阶段进行。首先，在较小的宏基因组数据集（由几千个点组成）上评估了该想法。在第二步中，我们建议使用基于相似性的索引方法（LSH方法）将这种方法扩展到大型数据集（由数百万个点组成）。论文有三大贡献。首先，我们提出了在聚类之前使用邻近图执行数据稀疏化的概念。邻近图建立在数据上，以捕获与聚类相关的数据点之间的成对关系然后，我们在这些图上使用社区检测算法来从数据中识别聚类。在三个宏基因组数据集上使用多个邻近图和社区检测算法进行了一项探索性研究。在此基础上，我们提出了一种名为ProxiClust的方法，结合KNN图和Louvain社区检测来执行合并。第二，为了将这种方法扩展到更大的数据集，管道中的距离矩阵被用从Sim-hashLSH方法构建的哈希表替换。我们介绍了两种从散列表中构建邻近图的策略：1）微簇图和2）Ap-近似k最近邻图。这些图的性能已在大型MC数据集上进行了评估。这些图形的性能和局限性摘要12库萨。还对这些数据集进行了基线评估，以确定其聚类难度。在此基础上，我们提出了Mutual-KNN图作为大型数据集的合适邻近图该提议也在CAMI基准宏基因组数据集上进行了评估最后，我们研究了构建更高质量哈希表的替代哈希方法已经包括了ITQ的数据相关散列方法和Sim-hash的正交版本引入了两种新的数据相关散列方法ITQ-SH和ITQ-OrthSH所有散列方法都经过了评估，但它们是否能够以高准确度和回忆对MC数据集进行散列。和引入Mutual-KNN作为适当的邻近图导致了管道中的首先，由于Mutual-KNN图中的组件数量很高，因此生成了大量的聚类因此，为了获得适当数量的集群，需要制定一项战略，以合并类似的集群。还需要设计一种从散列表构建Mutual-KNN图的方法。这将完成大型数据集的ProxiClust管道。关键词：元基因组数据分析、合成结合、聚类、ProxiClust、邻近图、社区检测、K最近邻图（KNN）、Lou- vain算法、局部敏感散列（LSH）、模拟散列LSH、迭代量化散列（ITQ）、近似最近邻图（AKNN）、微簇图、相互KNN、MC数据集、CAMI13摘要摘要1415>XXXKX X奏效>符号数据集RN×dN数据集的大小X数据集的数据矩阵x在数据点，x Xxi数据点x的第i个点x的d点的D距离矩阵C由聚类算法提供的聚类G是无向图V图GV中的节点图Geij顶点vi和vj之间的边，属于E C图GkKNN和相互KNN图中的邻居数k′是K-均值和K-中观的聚类数的输入参数K是一公里的给定C图的Qε-NN图的ε参数网络相似性，亲和传播的优化函数亲和传播识别的样本集H计算数据的二进制码的散列函数族y通过散列数据点获得的二进制码的向量形式x b 二进制码的长度yG散列法生成的投影矩阵Y二进制码的矩阵，YRb×Nbsizep哈希表中存储桶p的大小（点数）CTMAX建筑用微团簇的最大数量微团簇图nBuckets哈希表中已填充桶的数量sBuckets哈希表中已填充桶的数量enc（·）Pr将输入值输出到1或0sgn（·） P r将输入值输出到1或-1sim（·，·）P r rr函数定义空间中两点之间的相似性。dh（·，·）计算两个二进制代码之间的Hamming空间距离的函数XS符号1617内容。表24列表图27列表1导言291.1元基因组学导论1.2合并的挑战1.3论文贡献321.4论文大纲34I最新技术水平352聚类和宏基因组合并的最新技术2.1聚类方法372.1.1基本符号和定义372.1.2分区算法382.1.3亲和性传播392.1.4分层聚类422.2距离测量432.2.1欧几里得442.2.2余弦442.2.3斯皮尔曼Footrule距离442.2.4总变化距离442.3评估措施452.4宏基因组学术语462.5宏基因组结合的聚类2.5.1概述502.5.2MyCC 502.5.3LSH-SNN 53符号182.5.4Metacluster5.0 542.6数据集及其属性 . . . . . . . . . . . . . . . . . . . . . . . . . ...552.6.1真实数据集。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...552.6.2合成数据集。 . . . . . . . . . . . . . . . . . . . . . . . . . . . ...562.7问题陈述和提案大纲。 . . . . . . . . . . . . ...57二ProxiClust管道593ProxiClust描述61接近图和社区检测。 . . . . . . . . . . . . . . . ...613.1.1基本符号和定义 . . . . . . . . . . . . . . . . . . . ...613.1.2要考虑的邻近图。 . . . . . . . . . . . . . . . . . . . . ...611.3 MST. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...623.1.4 KNN图。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .623.1.5 ε图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...633.1.6相对近邻图。 . . . . . . . . . . . . . . . . . . ...633.1.7社区检测。 . . . . . . . . . . . . . . . . . . . . . . . . ...633.1.8鲁汶社区检测。 . . . . . . . . . . . . . . . . . . . ...643.1.9快速贪婪。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...653.1.10 标签传播 . . . . . . . . . . . . . . . . . . . . . . . . . . . ...663.1.11信息地图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...673.1.12 陷阱。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...683.2流水线。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...703.2.1总体描述。 . . . . . . . . . . . . . . . . . . . . . . . . . . ...703.3属性和期望 . . . . . . . . . . . . . . . . . . . . . . . . . . ...703.4评价标准 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...724第一个管道754.1实验细节 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...754.2图形。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...764.2.1实验目的。 . . . . . . . . . . . . . . . . . . . . . ...764.2.2协议 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...764.2.3结果与图形。 . . . . . . . . . . . . . . . . . . . . . . . . . ...784.2.4讨论和结论。 . . . . . . . . . . . . . . . . . . . . . ...804.3社区检测 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...804.3.1实验目的。 . . . . . . . . . . . . . . . . . . . . . ...804.3.2协议 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...81内容194.3.3结果。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...814.3.4讨论和结论。 . . . . . . . . . . . . . . . . . . . . . ...824.4距离选择。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...864.4.1实验的目的。 . . . . . . . . . . . . . . . . . . . . . ...864.4.2协议 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...864.4.3不同距离的结果 . . . . . . . . . . . . . . . . . . . . ...874.4.4讨论和结论。 . . . . . . . . . . . . . . . . . . . . . ...874.5K-mer 选择 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...884.5.1实验的目的。 . . . . . . . . . . . . . . . . . . . . . ...884.5.2协议 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...884.5.3结果。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...884.5.4讨论和结论。 . . . . . . . . . . . . . . . . . . . . . ...894.6与最新技术水平的比较评估894.6.1实验的目的4.6.2第89号议定书4.6.3采用最先进方法的结果4.6.4讨论和结论904.7结论91III用于大型数据集的ProxiClust 935大型数据集的方法5.1导言955.2哈希方法975.2.1符号和通用哈希框架975.2.2模拟哈希：基于随机超平面的方法985.3从Sim-hashLSH 995.4微团簇图1015.4.1概述1015.4.2微团簇图上的ProxiClust5.4.3使用散列构建微集群的策略5.4.4K-微团簇方法1035.4.5微团簇方法1045.5近似K最近邻图（AKNN）1055.5.1使用AKNN 105的动机5.5.2AKNN 105的建造5.6结论107内容206大型数据集1096.1 MC数据集上哈希的评估。 . . . . . . . . . . . . . . . . . . ...1096.1.1实验目的。 . . . . . . . . . . . . . . . . . . . . . ...1096.1.2协议 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...1106.1.3结果。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...1126.1.4讨论和结论。 . . . . . . . . . . . . . . . . . . . . . ...112K-微团簇方法-标准与分层。 . . . . . . . . . . . . . ...1136.2.1实验目的。 . . . . . . . . . . . . . . . . . . . . . ...1136.2.2协议 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...1136.2.3结果。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...1146.2.4讨论和结论。 . . . . . . . . . . . . . . . . . . . . . ...1156.3 K-微团簇与1-微团簇方法 . . . . . . . . . . . . . . . . ...1166.3.1实验目的。 . . . . . . . . . . . . . . . . . . . . . ...1166.3.2协议 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...1166.3.3结果。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...1176.3.4讨论和结论。 . . . . . . . . . . . . . . . . . . . . . ...1176.4 CTMAX上的分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...1196.4.1实验目的。 . . . . . . . . . . . . . . . . . . . . . ...1196.4.2协议 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...1196.4.3结果。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...1206.4.4微团簇图结论 . . . . . . . . . . . . . . . . . ...1216.5近似K近邻图上的可缩放ProxiClust . . . . ...1226.5.1实验目的。 . . . . . . . . . . . . . . . . . . . . . ...1226.5.2协议 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...1226.5.3结果。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...1236.5.4 AKNN的结论。 . . . . . . . . . . . . . . . . . . . . . . . . ...1256.6基线评估和边缘修剪 . . . . . . . . . . . . . . . . . . . .1266.6.1实验目的。 . . . . . . . . . . . . . . . . . . . . . ...1266.6.2协议 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...1266.6.3结果。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...1296.6.4边缘修剪和聚类困难的结论。 . . . . . . ...1296.7结论。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...1307替代散列方法1317.1导言1317.2散列方法1317.2.1正交Sim-hash 1327.2.2 ITQ 133