类似的图形聚类算法可用于理解执行大部分生命功能的蛋白质

您是否知道用于分析社交网络用户之间关系或排名网页的工具对于理解大型科学数据也非常有价值?在像Facebook这样的社交网络上，每个用户(个人或组织)都被表示为一个节点，它们之间的连接(关系和交互)被称为边缘。通过分析这些联系，研究人员可以了解很多关于每个用户的兴趣，爱好，购物习惯，朋友等。

在生物学中，类似的图形聚类算法可用于理解执行大部分生命功能的蛋白质。据估计，仅人体就含有约100,000种不同的蛋白质类型，当这些微生物相互作用时，几乎所有的生物学任务 - 从消化到免疫 - 都会发生。更好地了解这些网络可以帮助研究人员确定药物的有效性或确定各种疾病的潜在治疗方法。

如今，先进的高通量技术使研究人员能够在一系列环境条件下同时捕获数亿种蛋白质，基因和其他细胞成分。然后将聚类算法应用于这些数据集，以识别可能指向结构和功能相似性的模式和关系。尽管这些技术已被广泛使用了十多年，但它们无法跟上下一代测序仪和微阵列产生的大量生物数据。事实上，现有的算法很少能够聚类包含数百万个节点(蛋白质)和边缘(连接)的生物网络。

这就是能源部(DOE)劳伦斯伯克利国家实验室(伯克利实验室)和联合基因组研究所(JGI)的一组研究人员采用现代生物学中最流行的聚类方法之一 - 马尔可夫聚类(MCL)算法 - 以及将其修改为在分布式内存超级计算机上快速，高效和大规模运行。在一个测试案例中，他们的高性能算法 - 称为HipMCL--实现了以前不可能的壮举：在国家能源研究中使用大约140,000个处理器核心，在几个小时内聚集一个包含大约7000万个节点和680亿个边缘的大型生物网络科学计算中心(NERSC)Cori超级计算机。最近发表在“ 核酸研究 ”杂志上的一篇描述这项工作的论文。

“HipMCL的真正好处在于它能够聚集大规模的生物网络，这些生物网络无法与现有的MCL软件聚类，从而使我们能够识别和表征微生物群落中存在的新功能空间，”负责JGI的Nikos Kyrpides说道。微生物数据科学工作和原核生物超级计划是本文的共同作者。“而且我们可以做到这一点，而不会牺牲原始方法的任何敏感性或准确性，这始终是这类扩展工作中的最大挑战。”

“随着我们的数据增长，我们将工具转移到高性能计算环境变得更加迫切，”他补充道。“如果你问我蛋白质空间有多大?事实上，我们并不知道，因为直到现在我们还没有计算工具来有效地聚集我们所有的基因组数据并探测功能性暗物质。 “

除了数据收集技术的进步之外，研究人员越来越多地选择在社区数据库中共享他们的数据，例如综合微生物基因组和微生物组(IMG / M)系统，该系统是通过JGI和伯克利实验室的科学家之间数十年的合作开发的。计算研究部(CRD)。但是，通过允许用户进行比较分析并根据其宏基因组序列探索微生物群落的功能，IMG / M等社区工具也会导致技术数据爆炸。

随机游走如何导致计算瓶颈

为了掌握这些数据，研究人员依靠聚类分析或聚类。这基本上是对对象进行分组的任务，以便同一组(群集)中的项目与其他群集中的项目更相似。十多年来，计算生物学家一直青睐MCL通过相似性和相互作用聚类蛋白质。

“MCL在计算生物学家中很受欢迎的原因之一是它相对无参数;用户无需设置大量参数即可获得准确的结果，并且对于数据的小变化非常稳定。这是这很重要，因为您可能需要重新定义数据点之间的相似性，或者您可能需要纠正数据中的轻微测量错误。在这些情况下，您不希望您的修改将分析从10个集群更改为1,000个集群，“ CRD科学家AydinBuluç是该论文的共同作者之一。

但是，他补充说，计算生物学社区正面临计算瓶颈，因为该工具主要运行在单个计算机节点上，执行计算成本高并且占用大量内存 - 所有这些都限制了此算法可以聚集的数据量。

此分析中计算量和内存最密集的步骤之一是称为随机游走的过程。此技术可量化节点之间连接的强度，这对于分类和预测网络中的链接非常有用。在互联网搜索的情况下，这可能会帮助您在旧金山寻找便宜的酒店房间，享受春假，甚至可以告诉您预订的最佳时间。在生物学中，这样的工具可以帮助您识别帮助您的身体对抗流感病毒的蛋白质。

给定任意图形或网络，很难知道访问所有节点和链接的最有效方法。随机游走通过随机探索整个图形来获得足迹感; 它从节点开始，沿边缘任意移动到相邻节点。此过程一直持续到图形网络上的所有节点都已到达。因为在网络中的节点之间有许多不同的传播方式，所以该步骤重复多次。像MCL这样的算法将继续运行此随机游走过程，直到迭代之间不再存在显着差异。

在任何给定的网络中，您可能有一个连接到数百个节点的节点和另一个只有一个连接的节点。随机游走将捕获高度连接的节点，因为每次运行该过程时都会检测到不同的路径。利用该信息，该算法可以以确定的程度预测网络上的节点如何连接到另一个节点。在每个随机游走运行之间，算法在马尔可夫矩阵的列中标记其对图上的每个节点的预测 - 类似于分类帐 - 并且最后显示最终聚类。这听起来很简单，但对于具有数百万个节点和数十亿个边缘的蛋白质网络，这可能成为极其计算和内存密集的问题。借助HipMCL，伯克利实验室的计算机科学家们使用尖端的数学工具来克服这些局限。

“我们特别保持了MCL骨干的完整性，使得HipMCL成为原始MCL算法的大规模并行实现，”CRD的计算机科学家，该论文的第一作者Ariful Azad说。

Azad指出，虽然之前曾尝试将MCL算法并行化以在单个GPU上运行，但由于GPU上的内存限制，该工具仍然只能聚集相对较小的网络。

“通过HipMCL，我们基本上可以重新编写MCL算法，在数千个处理器上并行运行，并将其设置为利用所有计算节点中可用的聚合内存，”他补充道。“HipMCL前所未有的可扩展性来自于使用最先进的稀疏矩阵操作算法。”

根据Buluç，从图的许多节点同时执行随机游走最好使用稀疏矩阵矩阵乘法计算，这是最近发布的GraphBLAS标准中最基本的操作之一。Buluç和Azad为GraphBLAS的稀疏矩阵矩阵乘法开发了一些最具可扩展性的并行算法，并修改了其最先进的HipMCL算法之一。

“这里的关键是在并行性和内存消耗之间取得适当的平衡.HipMCL在分配给它的可用内存的情况下动态提取尽可能多的并行性，”Buluç说。

HipMCL：大规模聚类

除了数学创新之外，HipMCL的另一个优势是它能够在任何系统上无缝运行，包括笔记本电脑，工作站和大型超级计算机。研究人员通过使用C ++开发工具并使用标准MPI和OpenMP库来实现这一目标。

“我们在NERSC的Intel Haswell，Ivy Bridge和Knights Landing处理器上广泛测试了HipMCL，在所有处理器上使用了多达2,000个节点和50万个线程，在所有这些运行中，HipMCL成功地聚集了包含数千到数十亿边缘的网络， “Buluç说。“我们发现它可以用来运行的处理器数量没有障碍，并且发现它可以比原始MCL 算法快1000倍。”

“正如IMG和IMG / M系统已用于微生物组基因组学一样，HipMCL将成为大数据计算生物学的真正转型，”Kyrpides说。“这一成就证明了伯克利实验室跨学科合作的好处。作为生物学家，我们了解科学，但能够与计算机科学家合作能够帮助我们解决局限并推动我们前进，这是非常宝贵的。”

他们的下一步是继续为未来的exascale系统重新设计HipMCL和其他计算生物学工具，这些工具将能够计算每秒钟数的计算。这将是至关重要的，因为基因组学数据继续以令人难以置信的速度增长 - 每五到六个月翻一番。这将作为DOE Exascale Computing Project的Exagraph联合设计中心的一部分完成。