北京基因组所（国家生物信息中心）开发基于最小树形图的单体型网络构建算法及应用平台McAN
单体型网络是一种可直观描绘序列间演化历程和亲缘关系的要领，在追踪差别物种的进化和迁徙方面施展着主要作用。在熏染病应用方面，单体型网络节点的序列带有病毒撒播变异的时空信息，便于剖析病毒撒播变异的动力学机制。疫情时代，多个研究接纳单体型网络要领剖析局部区域新冠病毒的撒播盛行网络关系和特征，但随着新冠病毒基因组数据爆炸式一连增添，现有的单体型网络构建算法不可知足海量数据的快速剖析，网络构建算法亟待刷新与完善。
克日，永利集团（国家生物信息中心）宋述慧研究组面向海量病原基因组数据的演化剖析需求，提出了基于最小树形图的单体型网络构建算法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算法及在线平台示意图
