de Bruijn Graph里twin和contig的溯源

说在前面的话
基于k-mer构建DBG,来进行assembly,已经被现在证实,是一种极好的方法。不过,我发现了构建DBG时,关于node的构建,有两种不同的“流派”。一派是velvet,SOAPdenovo,kallisto为代表的k-mer节点;另一派是bowtie的作者Ben Langmead的kminus1-mer节点。

前一派已经有了很多鲜活的例子,证实了其可行性;而后一派,很遗憾我未能找到某个很好的代表。通过一些学习,我还是了解到,后一派里关于化简DBG结构和图的修正错误,都还未被有针对性的解决。不过,Heng Li’s blog里有关于DBG的一文并提及,这两种图可以相互转化,所以,后一派应该也可以通过转化来解决化简和修正的问题。同时,这篇文章具体地剖析了“两派”的区别和关联,感兴趣的可以一看。
因此,下文讲的是前一派。

contig

k的局限性

velevt开篇即说,“A de Bruijn graph is a compact represation based on short words(k-mers) that is ideal for high coverage, very short read(25-50)bp data sets”,就是说,DBG不适合reads较长的测序数据。其声称,contig概念的引入,突破了这一限制。原因很容易发现,手动构建DBG时,就可以发现,k值越小,重复越多,分支越多,但受单个碱基错误而形成的不正确k-mer数量变少;相反,重复和分支减少,受单个碱基错误形成的不正确k-mer数量变多。contig要求内部node出度和入度均为1,因此,contig使得没有分支很简单的子图,那些连过来连过去很复杂的子图里的k值,不同的增大了。在后一步处理中,也会区别对待。

SOAPdenovo里的一张图提及,模糊的contigs将会用别的办法处理。

Graph Compression

图的压缩保证了DBG可以用于较大长度的reads和较大规模的基因组,在早期发布的一些软件中,经常提到short reads这样的词。不过,contig大幅度压缩了node的数量,在论文中,加上错误消除等手段,最后的“node”数,从一百万个变为了六百多个,这无疑是省下了后续步骤大量寻找node和其edge的时间。

twin

Graph Compression

图的压缩必不可少,kallisto小组成员Pall Melsted在他的博客里说到,“This gluing of a k-mer and its twin means that we can do one of two things”。并且,他计算了到底省下了多少时间。我在研究其博客时,也进行了计算。假设k值为2,那么正好能产生16($4\times4$)种node,即有$4^{k}$种。如果,用twin,当k为奇数时,恰好减少了一半,即$4^{k}/2$种;不过k为偶数呢,稍微有点不同,因为AT倒过来还是AT,这节约不了什么。像这样倒转过来还是自身的node,特点为前k/2个碱基等于后k/2个碱基的twin,也就是说,确立了前一半,就可以了,所以这样的node有$4^{k/2}$种,即$2^{k}$种,除开这些特殊的node,其他的node与k为奇数时相仿,减少了一半,因此为$(4^{k}-2^{k})/2+2^{k}=4^{k}/2+2^{k}/2$种。这同时也是k必须为奇数的一个原因。

既可以用于正链,也可以用于反链

在velevt中,提到“This ensures that overlaps between reads from oppsite hands are taken into account”,就是说,一个node,保证它可以用到另一条链上。edge也可以,“Any modification of one arc is implicitly applied symmetrically to its paired arc”,其中“arc”是指用来连接contig的边。因此,“To ensure that each k-mer cannot be its own reverse complement, k must be odd”。

小结

twin和contig的手段,都是为了化简图,但化简图并非只有这两步,一个许多reads构成的复杂的DBG图,有各种需要剔除的不需要分支。这些工作,velevt做的都很好,后来SOAPdenovo也在此基础上做了其他的工作,此外,kallisto中也有不同的创新思路和方法。这些还需我继续学习,包括拿到contig后如何进行assembly或者说alignment。

打赏还是得开着的,万一有人打赏呢?