基于Contig的单面基因组片段填充问题研究

Research Progress of One-sided Repetitive Genome Scaffold Filling Based on Contig

近些年来,随着基因测序技术的继续发展与应用,大量不完整基因组片段的处理问题有待研究。同时由于目前大部分的生物学研究是基于基因组序列可以提供完整信息的假设,但通过生物测序技术获得一个完整的基因组序列仍是困难的。因此基因组重组问题在计算生物学领域愈发受到关注和研究,研究如何填充缺失基因组使其完整,具有重要意义。针对单面基因组片段填充算法,目前常采用最大化公共邻接数目的度量依据,是将缺失基因填充至不完整基因序列中得到填充后的重排列基因序列,使之与参照基因序列之间的新公共邻接数目最大。主要研究了基于contig(片段重叠群)的单面重复基因组填充问题,重点对该问题的现有算法在近似比、核心技术以及时间复杂度等多方面进行了对比分析与总结,并分别提出了各类算法的改进思路,有助于进一步研究基于contig的单面序列填充问题。

In recent years,with the continuous development and application of gene sequencing technology,the number of incomplete genome scaffolds needs to be studied.At the same time,most of the current biological research is based on the assumption that genome sequences can provide complete information,but it is still difficult to obtain a complete genome sequence by biological sequencing technology.Therefore,genome recombination has attracted more and more attention and research in the field of computational biology.It is of great significance to study how to fill the missing genome and make it complete.The one-sided genome scaffold filling algorithm is to fill the missing genes into the incomplete genome scaffold to obtain the filled rearranged genome scaffold,and maximizes the number of common adjacencies between it and the reference genome scaffold.We mainly study the one-sided repeated genome scaffold filling problem based on contig,analyze and summarize the existing algorithms and their time complexity.We focus on the comparative analysis and summary of the existing algorithms in approximation ratio,core technology and time complexity,and put forward the improvement ideas of various algorithms,which is helpful for the further study of one-sided scaffold filling problem based on contig in the future.