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对序列进行聚类,寻找簇集,尝试满足下面个条件, T为指定相似度阈值:

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

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

实现逻辑:

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