KSNP: a fast de Bruijn graph-based haplotyping tool approaching data-in time cost

编辑 / 发布于2024-09-03 / 更新于2024-09-09 / 阅读 16

MEC https://academic.oup.com/bioinformatics/article/21/10/2456/207527

找到一个最少的SNP变换操作(0->1,1->0),将SNP片段分成两组,每组组内SNP不冲突(每个SNP位点上的SNP都是一样的),每组代表一个单倍型。

Abstract

长reads可以覆盖更多的变异位点提升了准确的单倍型组装的机会。SNP基因型的错误使得目前单倍型工具的计算要求很高。

本文提出KSNP,基因DBG的单倍型构建工具,相较于其他工具,KSNP至少有5倍的加速。

  • 先写了长reads作用,然后目前haplotype的问题(computational challenge),提出了本文的KSNP,简单介绍,主要提出了它的优势(5-fold speedup)。

Introduction

haplotype 是什么,区分继承自二倍体或多倍体亲本的染色体上的等位基因

haplotype 的作用,解释遗传机制,杂合隐隐组装,变异检测,

haplotype 的问题,需要处理因测序或比对在reads中出现的有错误的SNP基因型,

现有工作介绍,MEC(minimum error correction)

目前进展,long reads 有效之处,现有工具的表现

遇到的问题,计算负担,举例,分析了时间复杂度,提出需要haplotyping更有效的计算方法。

本文工具的介绍:把SNPs 字符串作为read,使用有效的图组装(DBG)。提出了个基于DBG图的工具KSNP,可以根据 aligned CLR,HiFi, ONTreads 生成人类单倍型。可以节约90%的时间。

Results

Overview of KSNP

整体介绍

Performance of KSNP

KSNP支持2-5的k-mer,越大的k-mer增加了边的可靠性,同时减少了边的深度。可以想象的到,更大的k会导致更高的haplotype准确率,更小的k导致更高的召回率和更长的haplotype。通过实验验证了这一想法,5-mer在HG001,HG002,HG005 在CLR数据集上,平均每个read上有6.6,9.6,12.6个杂合的SNPs,相对于2-mer低了2-3%的recall rate。 但对于HG01109和A.thaliana F1 ,CLR reads上平均包含23.3 和36.0个杂合SNPs,用5-mer只导致了0.2% 和 0.01%的降低,同时降低了hamming error。在长度和错误率都大于CLR reads的ONTreads上,使用Longshot和PEPPER-Margin-DeepVariant(PMD)来检测SNPs,PMD输出了更少,但更准确的SNPs。对于这两个识别的SNPs,5-mer显著向低了hammming error,在对应的0.3%的recall loss。对A. thaliana CLR 数据,更大的k值降低了获得的haplotype N50的长度。如果更好的haplotype连续性优先级高,更小的k值是更好的。

KSNP 的时间复杂度是O(Nd(logN+V)) 。运行时间是线性的。和其他几个haplotype工具对比,LongShot,Whatshap,HapCUT2 和 Margin 在人类和heterozygous A. thaliana 染色体上比对。对于准确率,Margin和Longshot最好,考虑到haplotype长度和recall,WhatsHap,HapCUT2和KSNP更好,对于计算资源,KSNP使用最少的峰值内存和cpu时间,只有其他工具的1.2%-19.4%。评估端到端时间,使用单线程测试,KSNP比其他有5-11倍的速度优势,在运行中,发现读和解压缩bam和vcf文件占用了83.5%的时间,构建和解决图只用了5.7%。

Methods

Graph processing in KSNP

Read re-alignment

输入比对read的BAM文件和VCF文件(记录变异)。KSNP采用一个局部 re-alignment方法减小由于测序或比对导致的错误。它提取read上SNP及周围31bp的碱基(SNP及左右各15bp),将提取的序列比对到两个目标序列上,一个是从参考序列上相应的窗口提取,另外一个是通过将可选的SNP等位基因替换参考序列上的等位基因获得,编辑距离较小的SNP等位基因是可信的,使用 myer的位向量算法计算比对分数,每列用32位表示。

Graph construction

修正后的SNP基因型作为string,导出k-mer,并将位置和基因型作为标志。每个特征k-mer初始化为图中的一个节点。相同特征的k-mer折叠成一个节点,一个k+1-mer 形成前缀k-mer和后缀k-mer之间的边,覆盖两个连接节点上的read的数量作为边的深度(权重)。考虑到二倍体基因组两个单倍型的自然对称性,同时生成顶点和边的补集,减少测序深度的不平衡。(对称性,没怎么搞明白)

Graph pruning

基因型错误会被编码到不明确的路径,这路径在图的遍历中被筛选掉

(1) Fast edge trimming

最初的图回包含有低depth的边, 2k+1 竞争边表示 2k 不同的phasing解决方案,删除shadow-depth的边,如果max edge depth M 大于预设值C(default 15),depth小于M/2的边被删除,否则删除depth小于M/5的边

(2) Tips removing

删除那些 不能延伸成 长的单倍型块的那些短的分支路径。 给定两个从一个节点开始的线性路径,如果它们的长度差别超过3倍,删除短的那条,KSNP从图上的最后一个节点往回开始删除,这样KSNP可以减少两条被检查过的路径再次分支的可能,提高识别段路径的效率。

(3) Bubbles resolving

快速修剪后,主要的未解决问题就是bubble结构了,一般来说,bubble从一个有两个出边的source节点开始,在一个有两个入边的sink节点结束,这两个节点间,有不相交的路径编码两种不同的phaseing解决方案。supper bubble 可能包含嵌套的bubble,表现出更复杂的phasing结构,这两种都称为bubble。对于每个bubble,KSNP查找一个从source节点到sink节点的有最小MEC分数的最优路径。如果一个bubble中路径的数量小于512,我们可以考虑每个方案,并计算它的MEC分数,有最小MEC分数的路径是最优路径,并移除其他所有路径。然而这种暴力方法是不实际的,由于嵌套结构,可能包含指数级别的路径。采用启发式算法去解决复杂路径。首先使用动态规划算法在线性时间内选择一个有最大weight(depth,笔误?虽然是一个意思)和的路径,然后通过修改可以生成更高MEC分数的边来修改路径,设计了一个模板列表,根据他们来切换可替代的边,路径的更新操作在MEC不增长或者迭代次数超过512后结束,大多数情况,MEC分数在十几次迭代后收敛。

MEC分数基于bubble包括的reads计算。然而,多个bubble之间的read set可能会有交叉,意味着一个read可能会涉及到多个bubble。这种情况下,分别计算单个bubbles的MEC分数是不可能的。所以有交集的read sets 结合到一个更大的bubble,整体解决。

(4) Branches resolving

运行完前面步骤后,可能仍然会保留长度较长的分支路径,这些分支可能是缺少边的未完成的bubble,因为不充足的测序或者之前的裁剪。通过恢复之前图上移除的边,这些分支可以连接到主路径上,形成bubble结构,然后可以通过步骤(3)解决。

Haplotype block generation

修剪完图后,通过遍历修剪后的图生成主要的单倍型blocks。过滤掉 被包含在长blocks中的短blocks。为了提升单倍型的连续性,如果两个blocks之间有重叠的SNPs,并且这些SNPs可以被long read横跨,将这样的blocks连接到一起。MEC分数决定两个互补单倍型中连接哪一个。

Time complexity of KSNP

分析复杂度。分析每一步的时间复杂度。

re-alignment 的时间复杂度是O(NdV)。 N 变异的数量,d 每个变异的最大覆盖深度,V 每个read的最大变异数量。

DBG 构建 O(Nd(logN+V)) 。

LogN表示二叉搜索read上第一个变异的时间。V个SNPs被用作k-mer。

fast triming 和 removing tips,时间复杂度和边的数量是线性关系,图最多有个2k+1(N-k)个边,k是一个固定为5的参数。图上的线性遍历的时间复杂度是O(N)。

bubble resolving 对每个候选路径计算MEC分数。最差是所有read都用到了,时间复杂度是O(NdV)。

总体上,KSNP的时间复杂度是 O(Nd(logN+V))。

Evaluation metrics of haplotype construction

6个评价标准 switch error rate, hamming error rate, haplotype N50, recall rate, CPU time, and the peak RAM consumption

switch error 组装的单倍型上两个相邻的SNPs和真正的单倍型上的相对应的SNPs不一致。switch error rate通过计算 错误的数量/(所有的SNPs数量 -1) 得到。

hamming error rate 单倍型中错误的phased SNP位点相对于真实父本或母本的单倍型的百分比。

recall rate 是正确的phased SNPs数量 / ground truth中所有phased SNPs的数量。

一个单倍型block的长度是第一个phased SNPs和最后一个phased SNPs 的距离, haplotype N50 是 haplotype block的长度L。有50%的blocks的长度和大于L。 这个值,通过对blocks按照长度从大到小排序,并累加这些长度,知道达到整体长度的50%。

Data processing in the experiments


HG001, HG002, and HG005 提取出来的phased 变异作为ground truth。

HG01109 双亲的illumina reads 用bwa-mem比对到GRCh37参考序列上,亲本的SNPs用bcftools mpileup 识别,


Discussion

主要的优势,fast。

从reads的发展,需要越来越多的计算资源,所以需要更加有效的算法。三个算法中有效节约时间并且结果也不错的点 DBG图,prune-search ,edge weight path length MEC score 保证结果可靠。

fast的用处有哪些。genome assembly, genome polishing 结构变异检测。染色体级别的haplotyping 不止需要long read,同时需要 long-range short read 例如Hi-C数据。因此,haplotyping 软件如果有可以处理多种测序技术read的能力是更好的。

未来,使用Hi-C测序数据和genetic data 来对边赋权重,提供更有效的证据。也希望KSNP可以用来处理多倍体。