单体型网络是一种可直观刻画序列间演化过程和亲缘关系的方法，在追踪不同物种的进化和迁移方面发挥着重要作用。在传染病应用方面，单体型网络节点的序列带有病毒传播变异的时空信息，便于分析病毒传播变异的动力学机制。疫情期间，多个研究采用单体型网络方法分析局部区域新冠病毒的传播流行网络关系和特征，但随着新冠病毒基因组数据爆炸式持续增长，现有的单体型网络构建算法不能满足海量数据的快速分析，网络构建算法亟待改进与完善。

　　近日，中国科学院北京基因组研究所（国家生物信息中心）宋述慧研究组面向海量病原基因组数据的演化分析需求，提出了基于最小树形图的单体型网络构建算法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算法及在线平台示意图