【3.3.4】Linclust序列聚类(基于Kmer,更快速)

Linclust已集成到免费GPLv3许可MMseqs2软件套件。 Linclust的源代码和二进制文件可以是在 https://github.com/soedinglab/mmseqs2 下载

随着高通量测序技术的迅猛发展,测序成本在不断降低,测序效率在不断提高。由此产生越来越多的生物序列数据,呈指数级爆炸增长,当然也包括基因序列或蛋白质序列。这些海量序列是后续生物信息分析的重要数据来源,一方面可以得到前所未有的生物信息,但另一方面也对数据分析研究者带来了巨大挑战,即数据的计算成本也在呈指数级增长。如何快速有效的分析海量序列数据是研究者面临的首要问题。

其中蛋白质序列聚类是数据分析的重要研究内容,蛋白质序列聚类一方面可以对序列进行去冗余操作,另一方面可以降低数据规模,进而方便数据存储和后续的分析步骤。因此许多算法研究者开发了许多蛋白质序列聚类算法,其中CD-HIT和UCLUST(USEARCH聚类版本)是目前可以处理海量蛋白质序列的两个经典聚类算法。目前这两个算法的谷歌学术引用次数(截止2019年3月27号)分别为4314(CD-HIT)和8912(UCLUST),是目前序列聚类领域的代表性算法,而UCLUST速度和影响力更胜于CD-HIT,有一种唯我独尊的地位。

这两个算法都采用基于种子序列的启发式聚类思想,如下图所示。如果待比较序列和种子序列的距离(不相似性)小于给定阈值(如0.03),就将这条序列归入到种子序列所属类别。如果与所有种子序列的距离都大于给定阈值(如0.03),则将这条序列作为新的种子序列,加入到种子集合里。每条种子序列就是每个类的代表序列,由于每条待比对序列只与种子序列比较,避免了序列间两两之间的比较,大大降低了计算时间。所以CD-HIT和UCLUST的计算时间复杂度为O(KN),其中N 是序列的总条数,K 是种子序列的条数。

但在蛋白质序列聚类过程中,作者发现序列个数K 的大小与序列条数N 在同一个数量级,导致计算时间仍然很大,有时候甚至接近于N,因此时间复杂度有可能为O(N*N),并不是与N 线性增长。为了进一步降低运行时间,作者提出了Linclust算法,可将计算时间复杂度降低到O(N),比CD-HIT和UCLUST快上百倍,极大提高聚类效率。

UCLUST和CD-HIT不适用于序列差异性比较大的数据集

一、Linclust序列聚类算法步骤:

二、结果展示

3.1 运行速度比较

在UniProt蛋白质序列数据库进行比较,序列条数为61522444,比较的方法有CD-HIT、UCLUST等。下图是聚类时间的结果比较,相似性阈值分别设置为50%,70%和90%。可以看出Linclust方法在50%相似性阈值下,运行速度比UCLUST快2300倍,比CD-HIT快4600倍,比MMseqs方法快460倍,比MASH快69000倍,比DIAMOND快1600倍。在90%相似性阈值下,比CD-HIT快62倍,比UCLUST快100倍,MMseqs快570倍。

运行时间的指数级曲线,可以推断出Linclust运行时间与序列条数的关系是O(N 1.01次方),UCLUST是O(N 1.62次方),CD-HIT是O(N 2.75次方)。所以相对于其他方法,Linclust方法运行速度真正实现只与序列条数有关。

3.2 聚类灵敏度比较

聚类灵敏度(clustering sensitivity),作者定义为平均每个类的序列条数,平均序列条数越多,说明算法聚类灵敏度越好(a deeper clustering with more sequences per cluster implies a higher sensitivity to detect similar sequences)。下图是不同方法的聚类灵敏度比较,可以看出Linclust方法聚类灵敏度也不错。

3.3 聚类一致性(consistency)比较

可以反映聚类的质量,用聚类结果的GO注释相似性分析,计算每个聚类单元里类成员与代表序列间的GO相似性,得出每个类的平均(mean)和最低(worse)的GO相似性。如下图所示,可以看出Linclust方法的聚类质量也不错,高于其他方法

参考资料

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学