UPARSE、DADA2、unoise3，三大算法学习笔记

扩增子的OTU聚类和降噪处理，在生信分析中必不可少。今儿个，小锐和大家分享下3种相关算法。

UPARSE

简介

UPARSE-OTU算法能构建出一系列OTU代表序列，可以使用cluster_otus命令就能实现的。

构建OTU前，Reads需要做好预处理：（1）根据overlap将配对的Reads拼接起来；（2）去除barcode序列；（3）进行质量过滤。

UPARSE聚类标准（如下图所示）

作为OTU的代表序列的条件如下：

1. 所有的OTU序列应该小于97%相似度。

2. OTU的序列和相邻的序列应该大于97%相似度。

3. 嵌合体已经删除。

UPARSE-REF 算法简单介绍

首先需要提供一个假定是完整、正确的D序列集数据库。为了构建出序列模型M，UPARSE-REF使用了简单方式去推算出序列错误情况。模型M可以是一个或多个refseq。M是单条refseq代表是没有嵌合体扩增。M是多条refseq代表是嵌合体扩增。M和S之间的错配代表两个序列之间的距离。

下图展示一个嵌合体的参考序列情况。

聚类方法

UPARSE-OTU使用了贪婪的算法查找样品中物种的组成。每一个输入序列比较当前OTUs数据库，UPARSE-REF算法会出现以下三种情况：

(a) UPARSE-REF算法以97%的相似度识别存在的OTU。

(b) UPARSE-REF算法匹配上嵌合体模型。

(c) UPARSE-REF算法小于97%的相似度的作为新的OTU，加入到OTUs数据库中。

DADA2

简介

DADA是一种基于模型的校正方法，而且不需要OTUs构建，能够识别454测序序列的碱基变异的算法。DADA2是对DADA算法的做了一些改进，适用于illumina测序序列。

下图展示了DADA2把测序和扩增错误的序列做了校正，而没有用UPARSE的方法进行Make OTUs。

DADA2 的核心算法

基于Illumina测序、扩增序列的错误，采用selfConsist无监督学习模型，计算出Rate λ_ji。 通过错误率模型，衡量扩增子序列i是否来在来自j（模板），如下图例子

Unoise3

简单介绍

Unoise的算法是对测序错误，扩增错误序列的校正。整个UNOISE分析包含了两部分：

(a) 去除测序错误和PCR点错误；

(b) 去除嵌合体。最后生成的OTU被称之为ZOTUs(Zero-radius OTUs)。

核心算法

使用fastq-uniques计算unique序列，并按照size排序，然后采用了两个度量指标来进行判别两个unique序列是否来自同一个模板。指标分别是：莱文斯坦距离d和skew值。

其中skew值即簇图(下图)心点X的丰度为c，成员M序列的丰度为m，skew(M, X) = m/c

如果d和skew值足够小，那么M就是X的一个具有d个点错误的变体，需要去除。

上图中绿色圆圈表述真实生物学序列，红色圈描述了替换突变导致的变体，圆圈的大小代表序列的丰度,d=1代表两条序列差异的个数。右侧是去噪之后的展示。

unoise公式：

其中α =2 、γ=4 （默认）

β(d) 是允许的最大差异值，如果skew（M,X）

上图中（1）X和b皆被正确预测；（2）e因为丰度比skew值不能满足条件，被认为是正确的扩增子序列；（3）f的丰度和e相近，但是可以满足条件，被正确的去除，g因丰度低被错误的去除。

今天的算法笔记就分享到这咯

希望能对您有帮助~

参考文献：

Edgar, R.C. (2013) UPARSE: Highly accurate OTU sequences from microbial amplicon reads, Nature Methods [Pubmed:23955772, dx.doi.org/10.1038/nmeth.2604].

Callahan B J, McMurdie P J, Rosen M J, et al. DADA2: high-resolution sample inference from Illumina amplicon data. Nature methods, 2016, 13(7): 581-583.

UNOISE2: Improved error-correction for Illumina 16S and ITS amplicon read. bioRxiv, 2016

撰稿：黄云

编辑：王丽燕