基于 Contig 的单面基因组框架填充 2-近似算法

来源：计算机技术与发展杂志2024年第02期北京时间：

作者：柳楠;卞忠勇;李洋;朱永琦

单位：山东建筑大学 计算机科学与技术学院,山东 济南 250101 Author(s): LIU Nan;BIAN Zhong-yong;LI Yang;ZHU Yong-qi School of Computer Science and Technology,Shandong Jianzhu University,Jinan 250101,China 关键词: 基因组;框架填充;近似算法;贪婪策略;最大匹配 Keywords: genome;scaffold filling;approximation algorithm;greedy strategy;maximum matching 分类号: TP301 DOI: 10. 3969 / j. issn. 1673-629X. 2024. 02. 022 摘要: 随着基因测序技术的持续发展,基因组框架填充问题受到广泛关注。 该文针对基于 contig 的单面含重复基因的基因组框架填充问题开展研究。 通过设计有效的近似算法,完成根据参照基因组,将缺失基因填充至基因测序获得的不完整框架中,提高基因组框架的完整性。 前期研究的基因组框架填充问题,缺失基因可以插入到不完整序列的任意两个基因之间,而基于片段重叠群(contig) 的基因组框架填充,缺失基因的插入位置被限制在两个 contig 之间,更具一般性,该问题已被证明是 NP 完全问题。 现有的近似算法中,2-近似算法处理的实例具有特殊性,2. 57-近似算法针对一般实例,但近似性能比不够理想。 该文以缺失基因、基因位点和断点三者之间的对应关系为基础,采用贪婪策略和最大匹配相结合的方式避免在填充过程中出现冗余公共邻接,并通过生成新的 contig 增加外邻接的数量,将针对一般实例的算法近似性能比提高到 2,完成了基于 Python 的可视化程序开发,进一步验证了算法的有效性。

摘要：随着基因测序技术的持续发展,基因组框架填充问题受到广泛关注。 该文针对基于 contig 的单面含重复基因的基因组框架填充问题开展研究。 通过设计有效的近似算法,完成根据参照基因组,将缺失基因填充至基因测序获得的不完整框架中,提高基因组框架的完整性。 前期研究的基因组框架填充问题,缺失基因可以插入到不完整序列的任意两个基因之间,而基于片段重叠群(contig) 的基因组框架填充,缺失基因的插入位置被限制在两个 contig 之间,更具一般性,该问题已被证明是 NP 完全问题。 现有的近似算法中,2-近似算法处理的实例具有特殊性,2. 57-近似算法针对一般实例,但近似性能比不够理想。 该文以缺失基因、基因位点和断点三者之间的对应关系为基础,采用贪婪策略和最大匹配相结合的方式避免在填充过程中出现冗余公共邻接,并通过生成新的 contig 增加外邻接的数量,将针对一般实例的算法近似性能比提高到 2,完成了基于 Python 的可视化程序开发,进一步验证了算法的有效性。

关键词：基因组;框架填充;近似算法;贪婪策略;最大匹配