基于 De Bruijn Graph 的序列比对算法

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

Introduction

传统的序列比对大多都是线性的，在一定程度上忽略了基因组的整体结构；而基于 De Bruijn Graph 的序列比对算法则在结构的基础上完成与参考基因组的比对。

碎碎念： 这篇博客更多的个人的探索学习。对于基因组中结构变异的检测（诸如：融合事件）；很多软件都是基于现有的比对信息检索是否存在相应特征的 reads，来预测是否发生某种结构变异。但比对质量受很多因素的影响；如测序质量，深度，比对软件等等。

而 De Bruijn Graph 构建生成的路径在一定程度上还原了基因组的结构，那我们是否可以通过这些 Walk 来预测结构变异的发生？？？

Getting Started

相关文献：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

1. De Bruijn Graph 认识

De Bruijn Graph 是一个展示符号序列之间重叠关系的有向示意图

De Brijn Graph 在基因组组装中起到重要的作用；可利用其将 k-mer 之间的重叠部分构建 Graph，得到最优路径从而拼接短序列成 contig

关于 k-mer 中 k 的选择：其中 k-mer 的长度常为奇数，根本原因是避免正反义链混淆；在对一条 read 取其 k-mer 时，通常是正反取两次；在二代测序中，利用 k-mer 可以去除测序错误碱基，并充分利用数据

融合软件检测策略

  1. GeneFuse： 从原始 Fastq 中查找能够 Mapping 到两个不同的 Region 的 reads；
    1. 为获得更长的 read，还对双端测序的 reads 进行合并，以获得更长的 reads
    2. 局限性：若提供的 fusion csv 文件中的区域存在重叠（这里的重叠是指对应于参考基因组上的碱基排布存在 overlap）；可能造成假阴性，导致漏检；此外，不能检测 fusion csv 文件内包含之外的融合事件，只能检测特定的设计好的融合事件
    3. 优势：假阳性低，融合事件可视化
  2. Factera： 从带有 soft clipped 信息的 bam 文件（如：bwa）中查找融合断点，再以断点附近的 reads 来判断两个断点是否满足融合事件的发生条件

如：有 gene w 和 gene v 两者可能存在融合事件

​ （1）soft clipped reads 的剪切边界是潜在的融合断点

​ （2）如要判断两个断点是否支持发生某个融合事件，则需要对断点附近的 reads 进行比对

​ （3）判断条件：如果 R1 和 R2 来自融合序列，则 R1 的映射部分（非软剪切部分）应与 R2 的软剪切部分匹配，反之亦然

  1. DELLY： 适用于检测拷贝数变异和串联重复事件以及稳定重排（如：倒置、倒位或易位）；能够确定基因组重排的全部范围，包括复杂事件，
    1. 专门用于存在具有不同插入片段大小的不同配对端测序的情况下进行 SV 检测

基于 De Bruijn 图的融合规律探索

  1. 以某个融合对搭档基因开始搜索（不能发现新融合事件）

  2. 所有的 Walk 都将经过某个顶点（Vertex）

  3. 这个顶点是 k 长度 k-mer ；那么其最中间位置的 pos 大概率便是融合的断点；所以 k 一定是个 奇数

Walk 搜索策略：

  1. k 为奇数
  2. 首节点考虑 的节点
  3. 搜索算法：广度优先？深度优先？// 是否需要考虑搜索的路径中每个顶点只能出现一次？？？
  4. 遍历满足条件的首节点以获取所有的 Walk
  5. 确定断点：对遍历得到的 Walk 进行查找出现次数最多的顶点，该顶点便存在融合的断点？？？【可能需要设置阈值，以排除假阳性】
  6. 注释部分。。。

为控制资源的策略：

  • 只对特定的融合对进行搜索？？？从而判断该融合对是否发生融合事件？？？【局限性-可考虑作为融合check的一种策略】

纯属个人猜测，也尝试过代码实现，构建demo尝试发现walk的分布规律；可惜的是有点太异想天开了，哈哈哈哈！！！

References

[1] https://zhuanlan.zhihu.com/p/57177938