HPC-CLUST:大型核苷酸序列集的分布式层次聚类

摘要

动机:核苷酸序列数据正在以越来越快的速度产生。通过相似性对这些序列进行聚类通常是分析的关键第一步，目的是减少冗余，定义基因家族或建议分类单位。精确的聚类算法，如层次聚类，在运行时间和内存使用方面的伸缩性相对较差，但是它们是可取的，因为在聚类期间采取的启发式捷径可能会在后面的分析步骤中产生意想不到的结果。

结果:在这里，我们介绍了HPC-CLUST，这是一种高度优化的软件管道，可以通过运行在分布式计算硬件上对大量预对齐的DNA序列进行聚类。它有效地分配内存和计算资源，在一个小集群上可以在几个小时内处理超过100万个序列。

可用性和实现:源代码和二进制文件可以在http://meringlab.org/software/hpc-clust/；该管道是用c++实现的，并使用消息传递接口(MPI)标准进行分布式计算。

联系人:mering@imls.uzh.ch

补充信息:补充数据可于生物信息学网上。

1介绍

层次聚类算法的时间复杂度是二次的或者更糟⁠，视乎所选的集群连接方法而定(戴和埃德尔斯布伦纳，1984年)．然而，hca有许多优势，使它们在生物学应用中具有吸引力:(i)它们是定义良好的，并且应该在不同的实现中可重复，(ii)它们只需要一个成对距离矩阵作为输入，(iii)它们是聚集的，这意味着一旦执行了完整的聚类运行，可以通过后处理快速提取处于任意相似阈值的聚类集。因此，HCAs在生物学中被广泛采用，从数据挖掘到序列分析到进化生物学。

除了通用的实现之外，还存在一些侧重于生物序列数据的层次聚类实现，它们利用了序列之间的距离可以相对便宜地计算的事实，即使是以一种短暂的方式。然而，现有的实现，如MOTHUR (城堡et al。, 2009年)， esprit (太阳et al。, 2009年)或RDP在线聚类(科尔et al。, 2009年)，它们都难以处理大量的序列集。鉴于这些性能限制，还实现了启发式优化，例如CD-HIT (Li和Godzik, 2006)及UCLUST (埃德加,2010)．

分层聚类首先分别考虑每个序列，并将最接近的两个序列合并到一个集群中。然后，通过加入最接近的序列和/或集群，迭代地形成更大的集群。具有多个序列的两个聚类之间的距离将取决于所选择的聚类链接。在单连杆中，它是两个最相似序列之间的相似度;在完全连锁中，两个最不相似的序列之间;在平均连杆中，所有成对相似度的平均值。后一种方法也被称为算术平均无加权对组法(UPGMA)，常用于系统发育引导树的构建。

在CD-HIT和UCLUST使用的方法类型中，每个输入序列都是按顺序考虑的，并且要么被添加到现有的集群(如果发现它满足集群阈值)，要么被用作启动新集群的种子。尽管这种方法非常有效，但它可能会导致一些不希望看到的特性(太阳et al。, 2012年):(i)它将创建具有比所选聚类阈值更不相似的序列的聚类;(ii)可能会出现在现有聚类附近创建新的聚类，但距离仅略长于聚类阈值;此时，靠近两个聚类的任何新序列将在两个聚类中被分割，而之前的序列将只添加到第一个聚类;这有效地降低了局部聚类阈值;(iii)不同的序列输入顺序会由于种子序列选择的不同而产生不同的聚类集合。点(i)也影响HCA使用单一连杆和较小程度的平均连杆，但不发生在完整的连杆。

在这里，我们提出了一个可以处理大量序列的HCA的分布式实现。它可以在一次运行中计算单个、完整和平均链接集群，并生成一个归并日志，随后可以在任何阈值处解析集群。CD-HIT、UCLUST和ESPRIT都以未对齐的序列数据作为输入，与之相反，HPC-CLUST(像motherur一样)以一组预先对齐的序列作为输入。这允许在对齐算法的选择上具有灵活性;未来版本的HPC-CLUST也可能包括对齐步骤。有关实现和算法的详细信息，请参见补充材料．

2方法

对于所有基准测试，我们使用了一个或多个专用的Dell Blade M605计算节点，该节点具有2个四核Opteron 2.33 GHz处理器和24 GB随机访问内存。每个软件管道都使用了最新版本:HPC-CLUST (v1.0.0)、MOTHUR (v.1.29.2)、ESPRIT(2011年2月)、CD-HIT (v4.6.1)和UCLUST (v6.0.307)。有关设置和参数的详细信息，请参见补充材料．

我们编译了来自NCBI Genbank的公开可用的16S细菌核糖体RNA全长序列数据集。使用INFERNAL v1.0.2与ssu-align包中的细菌16S模型对序列进行比对(Nawrockiet al。, 2009年)．重要的是，INFERNAL使用了线性扩展的配置文件对齐策略O（N)，并且可以进行琐碎的并行化。在两个保存良好的对齐列之间删除索引，并修剪序列，这样所有序列都具有相同的对齐长度。最终数据集由1 105 195个细菌序列(833 013个唯一)组成，其中1301个排列长度。

3的结果

3.1单机集群性能

HPC-CLUST在计算速度和内存效率方面进行了高度优化。它是到目前为止测试的集群实现中最快的，即使是在一台计算机上运行时(图1)．与MOTHUR相比，它产生相同或几乎相同的聚类结果(参见补充材料)．因为CD-HIT和UCLUST使用不同的聚类方法，所以它们不能直接比较，仅供参考。

在HPC-CLUST中，计算时间最多的是成对序列距离的计算，其次是对距离的排序，最后的聚类步骤是最快的。HPC-CLUST可以利用多线程在多个节点上执行，并在距离计算步骤中实际实现了最佳的并行化。中显示和讨论了其他基准测试补充材料．

3.2分布式聚类性能

将整个数据集(833 013个唯一序列)聚类到97%的识别阈值，在一个包含24个节点，每个节点8个核(192个核)的计算集群上总共需要2小时42分钟。由于并行化，距离和排序计算只需要57分钟(挂钟时间)，相当于>1万分钟的CPU时间。剩下的1小时和45分钟(挂钟时间)用于收集和聚类距离。距离矩阵使用的总内存为59.8或每个节点2.6 GB。在同一次运行中，执行合并步骤的节点在进行单链接、完整链接和平均链接聚类时，最多使用了4.9 GB内存

4结论

聚类通常是处理原始序列数据时的第一步，因此需要尽可能地快速和提高内存效率。在HPC-CLUST中实现分布式版本的层次聚类，现在可以完全聚类数量大得多的序列，实际上只受可用计算节点数量的限制。

确认

作者感谢Thomas S. B. Schmidt在测试HPC-CLUST时提供的反馈和帮助。

资金: ERC拨款(开始拨款' UMICIS/242870 '给C.vM)。

利益冲突:未声明。

参考文献

作者指出