Archives

扩增子数据分析之聚类:UCLUST

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

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,其中有很多参数可以设置,其实大部分时候还是遵循默认参数模式。

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 4
usearch -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_aggdcluster_edges

等级聚类描述

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

图解如下:

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

single linkage

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

Complete Linkage

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

Average Linkage

Comments are closed.