Archives

Metagenome序列分类之蛋白质空间搜索: Kaiju

今天开始会介绍一系列Metagenome(以后使用元基因组)数据分析中的序列分类问题,这类问题一直是研究的热点和难点。

热点:有用,比如直接鉴定环境样本(粪便、痰液、肺积液)病原,算法多样性, 从基于碱基组成统计分类、基于核酸Kmer查找、基于氨基酸序列MEM查找到序列比对,各种算法八仙过海、各显神通。

难点:序列分类准确性、敏感性、内存有效性、计算密集性等都是待解决问题。

Kaiju是一款基于在氨基酸空间进行相似性搜索的序列分类算法。

1. 算法介绍

Kaiju算法发表在了Nature Communications杂志 :Fast and sensitive taxonomic classification for metagenomics with Kaiju

图1. Kaiju算法

Kaiju算法可以通过上图进行解读,Kaiju两种模式,基于MUM(MaximUm exact Matches)模式和基于Greedy Score模式。

MUM模式:

1. 对输入的核酸序列进行六框翻译,遇到终止密码后切断生成多条ORF序列,输入序列可为氨基酸序列; 2. 排序,按照ORF序列长度排序; 3. 数据库搜索,对氨基酸序列进行BWT变换和FM索引,搜索每个ORF框并获取最长MEM(最小MEM长度,默认为11),如后 续的ORF不可能获取更长的MEM,终止搜索,使用具有最长MEM的命中序列对序列进行分类,如搜索到具有多个相同长度 MEMs,使用LCA回溯。

Greedy模式:

1. 对输入的核酸序列进行六框翻译,遇到终止密码后切断生成多条ORF序列,可输入氨基酸序列; 2. 排序,按照BLOSUM62值排序; 3. 数据库搜索,对氨基酸序列进行BWT变换和FM索引,搜索每个ORF的MEM(Greedy模式,最小MEM长度设置为7)并获取最 高的Score值(MEM向左侧延伸直至最大允许错配个数或者最左侧,比如官方Web服务设置为5, 最小匹配Score值为75), 如后续的ORF不可能获取更高的Score值,终止搜索,使用具有最高Score值的命中序列对序列进行分类,如搜索到具有 多个相同Score值的命中,使用LCA回溯。

几点说明:

BLOSUM62 矩阵, ORF Score 以及后续的MEM左侧延伸后Score值计算都是按照 BLOSUM62计算。 Kaiju的Greedy模式敏感度要比MEM模式高,但是牺牲了分类速度,对于一些新的基因尤为明显,Greedy采用的模式是启发式算法,只对MEM的末端延伸。 LCA算法见下图,从所有叶子节点向上回溯,找到所有命中节点的共同祖先,比如a|b|c叶子节点的LCA节点就是x节点。

[…]

使用SINTAX对16S序列进行分类:SINTAX

一、SINTAX介绍

先前介绍过RDP分类器的使用:使用RDP对16S序列进行分类:rdp_classifier, 现在介绍另外一个基于非朴素贝叶斯分类算法: SINTAX(SImple Non-Bayesian TAXonomy) , 文章见:

SINTAX: a simple non-Bayesian taxonomy classifier for 16S and ITS sequences.

SINTAX使用 Kmer (默认k=8, 放回式采样32 kmers)去计算和参考库共享Kmer, 确定最佳Hits, 迭代100次, 确定每个Level的分类(出现次数最多的分类)和可信度(出现的频率)。由此可见并不需要训练参考序列库。

后面会继续介绍 DADA2 assignTaxonomy 和 assignSpecies QIIME2 的 q2-feature-classifier,新文章: Optimizing taxonomic classification of marker gene sequences

二、SINTAX 实践:

1 数据库下载

SINTAX提供了 RDP training set 16 (13k seqs, with species […]