基因组所阮珏团队提出快速单体型重建算法KSNP

2024年4月11日，中国农业科学院深圳农业基因组研究所（岭南现代农业科学与技术广东省实验室深圳分中心）阮珏课题组联合鹏城实验室周倩、哈尔滨工业大学刘贤明课题组、深圳大学朱泽轩课题组，在《自然·通讯（Nature Communications）》上发表了题为“KSNP: a fast de Bruijn graph-based haplotyping tool approaching data-in time cost”的研究论文，开发出基于德布鲁因图（de Bruijn graph，DBG）的单体型重建新算法，该算法首次将DBG用于单体型组装，极大提高了单体型重建的速度，比现有方法提速5-10倍。该成果提供了杂合基因组分型与组装领域的理论创新以及高效的实用工具。

动植物基因组通常包含来自两个亲本的多套染色体。为更好理解基因组序列与表型间关系，需考虑遗传变异位点的连锁遗传，即单体型信息。单体型信息代表了群体中的遗传多样性，并在群体基因组学研究中揭示更多遗传资源。

在杂合基因组上实现基因分型和单体型重建是基因组算法领域的研究热点和难题。杂合基因组单体型重建算法根据测序序列中携带的连锁信息，将一系列杂合的单碱基变异位点（SNP）分型至代表不同亲本的集合之中。描述单体型重建原理的标准数学模型为最小错误纠正（Minimum Error Correction, MEC），其最优化已被证明为NP-hard难题。现有算法一般采用概率推断（如马尔科夫模型）、最大割、及固定参数的动态规划来近似求解，但仍然不能突破密集数学计算中的瓶颈。随着第三代长读长（long read）测序技术的发展和测序数据量的膨胀，现有单体型重建算法中高计算复杂度的瓶颈日益突出。

为提高重建单体型的计算效率，基因组所（省实验室深圳分中心）阮珏研究员提出利用DBG处理海量测序read上携带的SNP信息（图1），利用DBG表示全基因组read数据时的高度压缩性和完备性，完成对单体型的重建。为模拟全基因组组装的过程中DBG的构建和处理，研究人员将长读长测序的连续k个SNP的基因型当做一个节点（kmer），两个节点之间的read当做边，节点测序深度当做边的权重,构建DBG。在这个过程中，长序列内部的连接信息被快速捕获，最优单体型在DBG上以一条路径的形式存在。随后对全路径DBG采用搜索剪枝的方案，不断缩小优化空间，删除图上由于基因型错误、测序深度不均等导致的错误路径（分支和鼓泡），最终在DBG图上留下无歧义路径，即重建后的单体型序列（图2）。

图1 KSNP算法设计图

图2 KSNP DBG修剪策略示意图

在人类标准数据集（GIAB）和杂合拟南芥数据集上的实验结果显示，对比现有的单体型重建工具，KSNP具有5-10x的速度优势，其实际运行时间接近数据读入时间，表明KSNP的算法优化已经逼近速度优化的极限。KSNP是目前所有已知方案中理论时间复杂度最优的算法，实际运行时间接近线性时间复杂度，是DBG在长读长组装领域的又一成功创新应用成果。

鹏城实验室助理研究员周倩，哈尔滨工业大学计算学部博士生季发虎和深圳大学计算机学院毕业生林冬晓为本论文共同第一作者，基因组所（省实验室）阮珏研究员和深圳大学计算机学院朱泽轩教授为共同通讯作者。该研究获得了国家自然科学基金、国家重点研发计划和鹏城实验室重大攻关项目等基金资助，基因组所高性能计算平台以及鹏城云脑为该研究提供了算力支持。

算法开源地址：https://github.com/zhouqiansolab/KSNP

论文地址：https://www.nature.com/articles/s41467-024-47562-4