基于邻接的单面基因组片段填充问题研究进展  

RESEARCH PROGRESS ON ONE-SIDED GENOMIC SCAFFOLD FILLING BASED ON ADJACENCY

作　　者：李春良 宋卫星 徐勤业 贾瀚栋 李晓峰[1] 柳楠[1] Li Chunliang;Song Weixing;Xu Qinye;Jia Handong;Li Xiaofeng;Liu Nan(School of Computer Science and Technology,Shandong Jianzhu University,Jinan 250101,Shandong,China)

机构地区：[1]山东建筑大学计算机科学与技术学院,山东济南250101

出　　处：《计算机应用与软件》2021年第12期1-6,49,共7页Computer Applications and Software

基　　金：国家自然科学基金项目(61902221);山东省自然科学基金项目(ZR2018MF012)。

摘　　要：伴随生物测序技术的不断发展,大量基因组片段的后续处理问题亟待解决。基因组片段填充是有效解决方法之一,受到广泛关注。基于普通序列的单面基因组片段填充问题是将缺失的基因序列填充到一个不完整基因组片段B中,得到B′,与完整的参考基因组A对比,使得A和B′之间的邻接数最大化。基于片段重叠群的该问题区别在于基因组片段通常由一组连续的片段重叠群(contig)构成,缺失基因只能在contig两端进行插入。针对这两个领域的相关问题进行深入研究,对已有算法及算法复杂性进行详细的分析与比较,为未来基因组片段填充问题的研究及生物测序技术的发展提供有价值的参考。With the continuous development biological sequencing technology,a number of the subsequent processing of the genomic scaffold needs to be solved urgently,and genomic scaffold filling is one of the effective solutions and has received extensive attention.A genomic scaffold filling problem based on common sequence is to fill the missing gene sequence into an incomplete scaffold B to obtain B′,with respect to a complete reference genome A,so that the number of common adjacencies between A and B′is maximized.The difference of this problem based on contig lies in that a scaffold is usually given as a sequence of contigs,and the missing gene can only be inserted at both ends of the contigs.The relevant problems in two fields are studied in depth.The existing algorithms and algorithm complexity are analyzed and compared in detail.It provides valuable reference for the future research of the genomic scaffold filling and the development of the biological sequencing technology.

关 键 词：基因组 片段填充 近似算法 邻接 断点 NP完全 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]