超快速序列聚类算法汇总

评论5,571

前段时间在Briefings in Bioinformatics上发表一篇关于超快速序列聚类分析的文章,文章原始是想列举目前可以用于meta-genome序列分析的算法,但是这列算法和工具也可以用于其他的生物学应用,譬如搜索直系同源基因等等。

下面找选文中一小段话让大家对相关的聚类算法和软件一睹为快:

Sequence clustering is not a new topic; it existed long before the emerging of metagenomics and NGS technologies. In the past, many available clustering programs were used for clustering protein sequences such as ProtoMap [18], ProtoNet [19], RSDB [20], GeneRAGE [21], TribeMCL [22], ProClust [23], UniqueProt [24], OrthMCL [25], MC-UPGMA [26], Blastclust [27] and CD-HIT [28–31]. Many methods were also used for clustering expressed sequence tags (ESTs), such as Unigene [32], TIGR Gene Indices [33], d2_cluster [34] and several others [35–37].

想了解更多,请阅读原文:

Li W, Fu L, Niu B, Wu S, Wooley J. Ultrafast clustering algorithms for metagenomic sequence analysis. Brief Bioinform (2012)doi: 10.1093/bib/bbs035First published online: July 6, 2012

在上面列举的软件和算法中,其实大部分我目前自己还没用过;就我自己经验而论,CD-HIT我到挺喜欢。CD-HIT里面引入的序列排序机制我很欣赏。貌似大家常用的nr数据库就是通过CD-HIT对NCBI 所有的基因序列聚类得到的。

我们知道在对同源基因进行聚类的时候,最常见的一个处理方式就是all vs all的序列比对。简单地分析上面构建nr库的例子:

如果我们把nr库的范围缩小为所有的细菌中的蛋白序列。目前测序的完成图和草图基因组序列接近4000。姑且认为3000,假设每个基因组有4000个蛋白序列。采用普通的all对all的方式的话,计算量为(3000x4000)2。但是CD-HIT的做法是(一般我们在筛选同源序列的时候会有一个筛选的cutoff是coverage,即两条序列比对上的区域均要大于这个长度百分比):

1)拿到3000x4000个序列之后先把这些序列按照序列长度从长到短排序

2)选取最长的一条序列,作为seed序列,seed序列不是要和所有的序列进行alignment,而是对长度>=(seed 序列长度)* (用户设定的coverage)的序列进行比对。例如,加入coverage为80%,seed序列长度为2000aa,那么这条序列只和长度为1600aa以及以上的序列进行比对。小于1600aa的序列即使和seed序列比对的时候100%match,coverage也小于80%,因此和长度小于1600aa的序列比对时没有意义的。

3)和seed比对的那些序列,若满足identity以及其他相关参数,则认为和seed 序列式同一个cluster,放入seed cluster里面后,将其从全部的序列list里面除掉。

4)第一个seed比对完之后,seed序列和与seed序列同源的那些序列就被从序列list里面删掉,序列list相比之前变小。然后从剩下的那些序列里面选择最长的重复2)和3)直到序列list为空。

由上可见,利用cd-hit的策略后序列比对的计算量小了很多。当然,CD-HIT虽快,但是里面难免还是有一些问题存在,譬如:与seed比对上的序列可能与后面更短的序列更相似。

发表评论

匿名网友