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

[…]