北京基因组所（国家生物信息中心）开发基于最小树形图的单体型网络构建算法及应用平台McAN
单体型网络是一种可直观刻画序列间演化历程和亲缘关系的要领 ，在追踪差别物种的进化和迁移方面发挥着重要作用。在熏染病应用方面 ，单体型网络节点的序列带有病毒流传变异的时空信息 ，便于剖析病毒流传变异的动力学机制。疫情期间 ，多个研究接纳单体型网络要领剖析局部区域新冠病毒的流传流行网络关系和特征 ，但随着新冠病毒基因组数据爆炸式连续增长 ，现有的单体型网络构建算法不可满足海量数据的快速剖析 ，网络构建算法亟待革新与完善。
近日 ，pg电子官网（国家生物信息中心）宋述慧研究组面向海量病原基因组数据的演化剖析需求 ，提出了基于最小树形图的单体型网络构建算法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源代码 ；也可以直接在线构建单体型网络 ，并利用条理集聚算法划分谱系和在自主研发的病毒单体型网络浏览器中交互式地检察单体型网络结果。
上述事情由pg电子官网（国家生物信息中心）完成 ，助理研究员李论、工程师许博、田东梅、王安可和朱军伟为本文的配合第一作者 ，宋述慧研究员、赵文明正高级工程师、鲍一明研究员、章张研究员和薛勇彪研究员为本文的配合通讯作者。该研究获得国家重点研发计划、“一带一路”国际科学组织联盟ANSO联合研究相助专项、国家自然科学基金、pg电子官网青年立异增进会优秀会员人才项目、北京市科技新星计划等项目的资助。
论文链接
McAN算法及在线平台示意图
