扩增子数据分析之聚类：UCLUST « Biostack.org

UCLUST 使用USEARCH作为序列比对引擎并对序列进行聚类， 聚类采用了一种贪婪算法（是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法 wikipedia）。

描述 UCLUST的文章发表在Bioinformatics杂志： Search and clustering orders of magnitude faster than BLAST

QIIME 1.9.x 版本的构建OTU使用的就是UCLUST算法， 本文主要介绍UCLUST算法以及想对于应等级聚类概念。

1. UCLUST算法介绍

UCLUST 可对氨基酸序列和核酸序列进行聚类，其算法原理如下：

UCLUST对序列进行聚类，寻找簇集，尝试满足下面个条件， T为指定相似度阈值：

 (1) 所有的簇心之间相似度 < T (2) 簇成员之间相似度 ≥ T

UCLUST的簇心选择和输入文件的序列顺序有很大关联，序列可以按照序列长度进行排序，也可以按照序列的丰度进行排序，设计的逻辑是序列在文件中先出现先获得作为簇心的机会，并且每个簇只有一条代表序列。

实现逻辑：

(1). 初始化空的database；(2). 将序列文件中序列按照顺序开始放入database, 根据以有几种情况进行选择：    a. Database 为空， 放入database;    b. 和Databases 序列比对，判断相似度阈值:       如果相似度 ≥T 置入对应的簇。       如果相似度 <T 添加到database, 该序列设置为簇心；

UCLUST采用了全局比对策略，适合针对扩增子以及基因水平的聚类， UCLUST可以保证簇内的成员和簇心的相似度≥ T， 成成员之间不能得到保证≥ T。

2. 命令行参数

UCLUST 使用 USEARCH 作为序列相似度计算引擎，也就是说设置的启发式参数会影响结果，比如查询序列搜索SEED(现在叫Centroid簇心序列)序列时不执行完全动态规划，不能保证是最相似序列。 下图为Usearch的flowchart，其中有很多参数可以设置，其实大部分时候还是遵循默认参数模式。

UCLUST算法通过cluster_fast和cluster_smallmem实现。

2.1 cluster_smallmem

主要支持参数列表：

-uc        :UC格式输出；-id        :相似度阈值；-centroids :簇心输出文件， fasta 文件格式；-strand    :针对核酸序列链方向指定；

不支持多线程，输入序列应该ortbylength 或者 sortbysize 排序；

实例：

usearch -sortbysize seqs.fasta -fastaout seqs_sorted.fasta -minsize 4usearch -cluster_smallmem  seqs_sorted.fasta  -id 0.97 -centroids nr.fasta -uc clusters.uc

nr.fasta 就是我们的簇心序列， clusters.uc 序列分类结果（簇心还是簇归属）； 如果处理的双端扩增子序列推荐使用sortbysize, 如果处理比如454序列或者基因序列推荐使用ortbylength去避免选择小的片段作为簇心。

2.2 cluster_fast

主要支持参数列表：

-uc        :UC格式输出；-id        :相似度阈值；-centroids :簇心输出文件， fasta 文件格式；-strand    :针对核酸序列链方向指定； -sort      :支持排序操作，length, size, others;-sizein    :输入序列文件带有丰度注释;-sizeout   :输出序列文件带有丰度注释;-threads   :支持多线程；-consout   :Consensus 序列;-msaout    :多序列比对结果；

实例：

usearch -cluster_fast derep.fa -id 0.9 -centroids nr.fasta -uc clusters.uc -sort size  -sizein -sizeout -threads 20  -consout  consout.fasta  -msaout  msaout.aln

3. 其它

ULAST的聚类策略和下图的等级聚类（Hierarchical Clustering， wikipedia图解）有很大的差别，Usearch中也实现了几种基于等级聚类的程序，比如cluster_agg, cluster_aggd 和 cluster_edges。

等级聚类的核心是定义两个簇距离，即如何度量两个簇之间的距离，有三种模式： 最小距离 (single linkage)、最大距离(complete linkage)，和平均距离（UPGMA）

图解如下：

single linkage， 两个簇的距离定义簇和簇之间的距离集合中的最小值，得到的簇最大。

Complete Linkage 两个簇的距离定义簇和簇之间的距离集合中的最大值，得到的簇最小。

Average Linkage 两个簇的距离定义簇和簇之间的距离集合的平均值，得到的簇介于single linkage和Complete Linkage之间。