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

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