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可以用来处理多倍体。