前段时间在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].
想了解更多，请阅读原文：
在上面列举的软件和算法中，其实大部分我目前自己还没用过；就我自己经验而论，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比对上的序列可能与后面更短的序列更相似。