基于 De Bruijn Graph 局部组装的变异检测

发表于 分类于 ， 阅读次数： 本文字数： 2.8k 阅读时长 ≈ 3 分钟

Introduction

基于图的比对策略，可以很好的解决因重复区域导致无法精确映射的问题；因为在构建图时，需要将重复区域进行分解，从而限制了 reads 的多次匹配现象。

Getting Started

基于图的比对策略，可以很好的解决因重复区域导致无法精确映射的问题；因为在构建图时，需要将重复区域进行分解，从而限制了 reads 的多次匹配现象。

1. SOAPindel: efficient identification of indels from short paired reads.

这是一款检测基因组插入缺失的软件；其中与传统比对软件不同的是，其会对未映射到参考基因组的reads进行广义的从头组装，以通过 de bruijn graph 穷举遍历来解析纯合子、杂合子和复杂的插入缺失

The most powerful indel calling approach would be to perform de novo assembly of each genome and identify indels by alignment of genomes.

最强大的插入缺失检测方法是对每个基因进行从头组装，并通过基因组比对识别插入缺失。然而，这在计算上难以实现，且需要非常高的测序深度；所以 SOAPindel 对区域进行完整的从头组装，在预期的基因组位置收集所有未映射的reads，然后对具有高密度此类reads的区域进行局部组装，最后将这些组装与参考基因组对齐。通过检查扩展的 de Bruijn Graph 中的所有路径，并选择那些锚定在参考基因组序列上的某些点的路径来处理这些复杂性（如：错误配对、测序错误、非唯一映射、重复序列等）【是否可以理解成组装的reads对象是：那些只有部分比对上参考的reads，在组装得到的各类路径就只需要关注那些以能够比对上参考的k-mer起始？？？】

优点：

  • 对各种错误来源很敏感；如错误配对、测序错误、非唯一映射、重复序列
  • 将杂合插入缺失理解为 de bruijn graph 中的两条不同路径
  • 测序序列覆盖度是灵敏度的主要决定因素，reads长度对于基于比对的方法的插入缺失检测的大小限制是主要因素，但对 SOAPindel 则不受reads长度的限制（得益于局部重组装）

2. deBGA: read alignment with de Bruijn graph-based seed and extension

传统的共线性多序列比对（MSA）算法可能并不适合表示非共线事件，如倒位、易位和重复；

可解决因基因组同源性高造成的一部分局限性；deBGA 可以将 reads 同多个基因组进行比对，且具有高通量，不受变异类型的限制，在处理单个基因中重复方面存在优势。

de Bruijn Graph 的优势：

  • 可以很好的展现基因组的整体结构
  • deBGA 可以利用 RdBG 的特性通过 unipath 合并具有相似 PRP(Putative Read Position) 的种子（seed），这可以有效地处理重复的种子序列

deBGA 程序主要分为两部分：

Index

  • 参考基因组的 de Bruijn Graph 称为：RdBG(Reference de Bruijn Graph)
  • RdBG 的顶点和边只是简单的从参考基因组的所有 (k+1)-mers 导出，deBGA研究顶点的入度和出度，以识别RdBG的非分支路径（即单路径）的起始顶点，并通过从起始顶点遍历图来导出单路径。然后通过折叠相应单路径的所有顶点来生成单路径（unitigs）的序列。由于一个单位在参考基因组中可能有多个拷贝，对于每个单位，deBGA还记录了其所有拷贝的起始位置。然后构建 RdBG-Index 来索引 unitigs。

Index-data structures

  • ：记录 unitigs，并为其分配一个特定的标识符
  • ：索引 unitigs 的所有 k-mers；对每个 k-mer，记录其标记 及它的 unipath 坐标（偏移量）
  • ：记录 unitigs 所有拷贝数的起始位置

Index-functions

  • 检索给定 k-mer 的 unipath 坐标（包括 kmer 在 unipath 内的偏移；偏移即位置）
  • 检索对应于给定 unipath 坐标的所有基因组位置
  • 为给定的 unipath 检索相应的 unitig

注意：对于参考基因组的任何 k-mer，它的 unipath 坐标时唯一的，因为它在 RdBG 中只出现一次；

image0

总结

  1. SOAPindel 并不是对所有区域进行从头组装；而是对那些潜在的可能插入缺失区域进行局部组装，使得其检测长插入的性能不再受reads长度的限制
  2. SOAPindel 不考虑多个映射位置的reads，这对灵敏度损失很小，却对特异性提升很高；收集到的每个未映射读数都会根据映射配偶的方向和预期距离给出一个近似的候选基因组位置（针对与配对双末端的reads而言）
  3. 二倍体基因组中的杂合子导致 de Bruijn Graph 中出现气泡（图 1H1a），在 SOAPindel 程序中会追踪导致气泡的两条路径（全基因组组装通常只追踪其中一条路径，最优路径）；长度>=K 的短重复将导致图上的分叉（图 1H1b）；当 串联重复长度>=max(K, L) （L 是模式长度；ATATAT 的模式是 AT），将导致循环（图 1H1c）；只要重复长度短于reads长度，我们就可以追踪任何一条路径。
图1
  1. SOAPindel 为解决低覆盖率导致因 k-mer 长度太长造成的路径中断现象，使用动态方法在路径断开的地方降低 k-mer 长度。对于候选纯合插入缺失，搜索具有逐渐缩短的 k-mer 的未使用 reads，直到形成路径或达到 k-mer 长度的下限；对于候选杂合插入缺失（具有许多未映射读数的一条路径被破坏的情况），我们完全重做组装以逐渐减少 K-mer 长度。
  2. 在组装过程中，利用参考上所有独特的 k-mers 与局部组装共线，将其作为标记来指导方向、消除错误和控制局部组装的长度；最后，将组装得到的所有 contigs 与参考基因组进行比对（Smith-Waterman alignment），以call出存在的任何插入缺失的基因型

References

[1] Limasset, A., Cazaux, B., Rivals, E. et al. Read mapping on de Bruijn graphs. BMC Bioinformatics 17, 237 (2016). https://doi.org/10.1186/s12859-016-1103-9

[2] Li S, Li R, Li H, et al. SOAPindel: efficient identification of indels from short paired reads. Genome Res . 2013;23(1):195-200. doi:10.1101/gr.132480.111