2024年4月11日，中國(guó)農(nóng)業(yè)科學(xué)院深圳農(nóng)業(yè)基因組研究所（嶺南現(xiàn)代農(nóng)業(yè)科學(xué)與技術(shù)廣東省實(shí)驗(yàn)室深圳分中心）阮玨課題組聯(lián)合鵬城實(shí)驗(yàn)室周倩、哈爾濱工業(yè)大學(xué)劉賢明課題組,、深圳大學(xué)朱澤軒課題組,，在《自然·通訊（Nature Communications）》上發(fā)表了題為“KSNP: a fast de Bruijn graph-based haplotyping tool approaching data-in time cost”的研究論文，開發(fā)出基于德布魯因圖（de Bruijn graph,，DBG）的單體型重建新算法,，該算法首次將DBG用于單體型組裝，極大提高了單體型重建的速度,，比現(xiàn)有方法提速5-10倍,。該成果提供了雜合基因組分型與組裝領(lǐng)域的理論創(chuàng)新以及高效的實(shí)用工具,。

動(dòng)植物基因組通常包含來(lái)自兩個(gè)親本的多套染色體。為更好理解基因組序列與表型間關(guān)系,，需考慮遺傳變異位點(diǎn)的連鎖遺傳,，即單體型信息。單體型信息代表了群體中的遺傳多樣性,，并在群體基因組學(xué)研究中揭示更多遺傳資源,。

在雜合基因組上實(shí)現(xiàn)基因分型和單體型重建是基因組算法領(lǐng)域的研究熱點(diǎn)和難題。雜合基因組單體型重建算法根據(jù)測(cè)序序列中攜帶的連鎖信息,，將一系列雜合的單堿基變異位點(diǎn)（SNP）分型至代表不同親本的集合之中,。描述單體型重建原理的標(biāo)準(zhǔn)數(shù)學(xué)模型為最小錯(cuò)誤糾正（Minimum Error Correction, MEC），其最優(yōu)化已被證明為NP-hard難題?，F(xiàn)有算法一般采用概率推斷（如馬爾科夫模型）,、最大割、及固定參數(shù)的動(dòng)態(tài)規(guī)劃來(lái)近似求解,，但仍然不能突破密集數(shù)學(xué)計(jì)算中的瓶頸,。隨著第三代長(zhǎng)讀長(zhǎng)（long read）測(cè)序技術(shù)的發(fā)展和測(cè)序數(shù)據(jù)量的膨脹，現(xiàn)有單體型重建算法中高計(jì)算復(fù)雜度的瓶頸日益突出,。

為提高重建單體型的計(jì)算效率,，基因組所（省實(shí)驗(yàn)室深圳分中心）阮玨研究員提出利用DBG處理海量測(cè)序read上攜帶的SNP信息（圖1），利用DBG表示全基因組read數(shù)據(jù)時(shí)的高度壓縮性和完備性,，完成對(duì)單體型的重建,。為模擬全基因組組裝的過(guò)程中DBG的構(gòu)建和處理，研究人員將長(zhǎng)讀長(zhǎng)測(cè)序的連續(xù)k個(gè)SNP的基因型當(dāng)做一個(gè)節(jié)點(diǎn)（kmer）,，兩個(gè)節(jié)點(diǎn)之間的read當(dāng)做邊,，節(jié)點(diǎn)測(cè)序深度當(dāng)做邊的權(quán)重,構(gòu)建DBG。在這個(gè)過(guò)程中,，長(zhǎng)序列內(nèi)部的連接信息被快速捕獲,，最優(yōu)單體型在DBG上以一條路徑的形式存在。隨后對(duì)全路徑DBG采用搜索剪枝的方案,，不斷縮小優(yōu)化空間,，刪除圖上由于基因型錯(cuò)誤、測(cè)序深度不均等導(dǎo)致的錯(cuò)誤路徑（分支和鼓泡）,，最終在DBG圖上留下無(wú)歧義路徑,，即重建后的單體型序列（圖2）。

圖1 KSNP算法設(shè)計(jì)圖

圖2 KSNP DBG修剪策略示意圖

在人類標(biāo)準(zhǔn)數(shù)據(jù)集（GIAB）和雜合擬南芥數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果顯示,，對(duì)比現(xiàn)有的單體型重建工具,，KSNP具有5-10x的速度優(yōu)勢(shì)，其實(shí)際運(yùn)行時(shí)間接近數(shù)據(jù)讀入時(shí)間，表明KSNP的算法優(yōu)化已經(jīng)逼近速度優(yōu)化的極限,。KSNP是目前所有已知方案中理論時(shí)間復(fù)雜度最優(yōu)的算法,，實(shí)際運(yùn)行時(shí)間接近線性時(shí)間復(fù)雜度，是DBG在長(zhǎng)讀長(zhǎng)組裝領(lǐng)域的又一成功創(chuàng)新應(yīng)用成果,。

鵬城實(shí)驗(yàn)室助理研究員周倩,，哈爾濱工業(yè)大學(xué)計(jì)算學(xué)部博士生季發(fā)虎和深圳大學(xué)計(jì)算機(jī)學(xué)院畢業(yè)生林冬曉為本論文共同第一作者，基因組所（省實(shí)驗(yàn)室）阮玨研究員和深圳大學(xué)計(jì)算機(jī)學(xué)院朱澤軒教授為共同通訊作者,。該研究獲得了國(guó)家自然科學(xué)基金,、國(guó)家重點(diǎn)研發(fā)計(jì)劃和鵬城實(shí)驗(yàn)室重大攻關(guān)項(xiàng)目等基金資助，基因組所高性能計(jì)算平臺(tái)以及鵬城云腦為該研究提供了算力支持,。

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

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