kallisto Pseudoalignments原理解析

原文链接
参考博客链接
kallisto Pseudoalignments是基于k-mers + T-DBG（transcriptome de Bruijn graph）
关于什么是de Bruijn graph 请点这里
如上图有三条overlapping的 transcripts，红、蓝、绿各代表一条。

第一步：建立索引

k-mers默认是31，k-mers越小会越敏感。图上的每一个node都代表一个k-mer。

k-compatibility class：transcripts包含node的k-mers ，那么称transcripts为该node的一个k-comptibility class。如图上最左边的node有三个k-compatibility class，因为三条transcripts都包含该node代表的k-mer。三个最上面的node只有两个k-compatibility class，因为只有蓝和红两条transcripts包含node 代表的k-mer。

contig:连续的有相同k-compatibility class的node组成。如上图中最左边的三个node构成一个contig，最上面的node也构成一个contig。

index会建立一个hash table<KmerEntry,KmerHash> KmerEntry里包含k-mer映射到contig的信息，KmerHash kmer的hash值。

第二步：比对

上图黑色的代表一条read。比对的时候read也会被切成一个个的k-mer。黑色的node代表比对上的。
然后找出每个比对上的node的k-compatibility class，然后取这些k-compatibility class的交集，就得到read的k-compatibility class。如果是paired-end，那就沿着一条参考序列取k-compatibility class。
冗余信息。最左段的3个node有相同的k-compatibility class，文章中又把这些相同的node称为k-equivalence class。在比对的过程中我们可以跳过这些k-equivalence class。这些信息已经存储在contig里。同一个contig里的node都有相似的k-compatibility class。为了确保跳过的是k-equivalence class,kallisto会检查跳过的最后一个node是否符合预期。正因为省掉这些冗余的node，比对速度快。如上图只需要取三个node的k-compatibility class的交集就能确定read的k-compatibility。