毋 东，魏亚伟，罗军伟，敖 山

（河南理工大学计算机科学与技术学院，河南焦作 454000）

0 概述

随着人类基因组计划的完成，基因组数据成为后基因组时代的重要标志，这些海量基因组数据的分析和挖掘深入到生命科学研究的各个方面，是众多生命科学研究的基础，更是计算机科学特别是生物信息学研究所面临的重大挑战。《国家“十三五”科技创新规划》和《国家自然科学基金委“十三五”发展规划》都明确将基因组数据分析以及生物大数据分析作为以“重大计划”形式倡导的研究内容。

目前，随着全基因组测序技术的发展，人们利用不同的序列组装方法获得越来越连续和完整的基因组序列。但是由于测序错误［1］、基因组重复区［2］、多态性等问题的存在，现有的序列组装方法往往输出一个包含间隙（gap）的序列集合，即scaffold［3］集合，其中每一个scaffold 是一条碱基序列，但是其包含一些gap 区域，通常由连续的“N”表示。而这些gap 区域可能对应基因编码或调控区域，这给下游分析中的基因表达和调控、结构变异分析、物种进化等研究增加困难。

为减少scaffold 中gap 的数量，增加序列的连续性和完整性，研究人员设计了gap 填充方法。gap 填充方法利用由测序技术获得的读数（read/序列片段）集合，确定scaffold 集合中gap 区域的序列。当前流行的测序技术主要包括第二代和第三代测序技术。第二代测序技术具有高速度、高通量、低成本等优点，但是第二代测序技术产生的读数长度较短，在一百到五百碱基左右，越来越多的研究表明，短读数对于复杂重复区的gap 区域的填充能力非常有限。……