今天开始会介绍一系列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节点。
[…]