單體型網絡是一種可直觀刻畫序列間演化過程和親緣關系的方法，在追蹤不同物種的進化和遷移方面發揮著重要作用。在傳染病應用方面，單體型網絡節點的序列帶有病毒傳播變異的時空信息，便于分析病毒傳播變異的動力學機制。疫情期間，多個研究采用單體型網絡方法分析局部區域新冠病毒的傳播流行網絡關系和特征，但隨著新冠病毒基因組數據爆炸式持續增長，現有的單體型網絡構建算法不能滿足海量數據的快速分析，網絡構建算法亟待改進與完善。

　　近日，中國科學院北京基因組研究所（國家生物信息中心）宋述慧研究組面向海量病原基因組數據的演化分析需求，提出了基于最小樹形圖的單體型網絡構建算法McAN，并開發了單體型網絡構建及可視化平臺。該成果以“McAN: a novel computational algorithm and platform for constructing and visualizing haplotype networks”為題在Briefings in Bioinformatics 期刊在線發表。

　　McAN根據流行病學特征及遺傳學原理，提煉出四個單體型網絡構建準則，根據這些準則將單體型網絡構建問題抽象為一個整數規劃問題，并對該整數規劃問題進行求解，且給出了McAN算法的最優性證明。此外，通過減少序列間距離的計算，McAN提高了單體型網絡構建的速度。對約1000條新冠病毒全基因組小數據集的測試表明，McAN的運行速度比傳統方法提升了兩個數量級；對500萬條的新冠病毒基因組序列大數據集測試，McAN算法耗時約25分鐘（50線程），具有處理海量病原基因組序列的能力；在模擬數據集上的測試結果表明，不損失精度的同時McAN的內存消耗與傳統方法相比降低90%以上；另在猴痘、甲型流感等多種數據集上，McAN均得到合理的結果。總之，McAN具有較快的運行速度和較高的精度，可高效滿足病原體快速演化追蹤的應用需求。

　　用戶可在BioCode或GitHub獲取McAN源代碼；也可以直接在線構建單體型網絡，并利用層次集聚算法劃分譜系和在自主研發的病毒單體型網絡瀏覽器中交互式地查看單體型網絡結果。

　　上述工作由中國科學院北京基因組研究所（國家生物信息中心）完成，助理研究員李論、工程師許博、田東梅、王安可和朱軍偉為本文的共同第一作者，宋述慧研究員、趙文明正高級工程師、鮑一明研究員、章張研究員和薛勇彪研究員為本文的共同通訊作者。該研究得到國家重點研發計劃、“一帶一路”國際科學組織聯盟ANSO聯合研究合作專項、國家自然科學基金、中國科學院青年創新促進會優秀會員人才項目、北京市科技新星計劃等項目的資助。

　　論文鏈接

McAN算法及在線平臺示意圖