课题背景
近年来，随着生物基因组测序技术的不断发展，测得的DNA序列数据也飞速增涨，这促进了生物信息学领域相关研究方向的深入开展。在生物基因组测序技术中，第一代测序技术是在人类基因组计划中得到了推广应用的Sanger测序技术[1]，由于存在测序覆盖率低、测序周期长和费用昂贵等方面的不足，Sanger测序技术已经逐渐被淘汰。随之而来的是第二代测序技术的诞生，第二代测序技术也被称为下一代测序技术（Next Generation Sequencing Technology, NGS）[2]。第二代测序技术的出现是测序技术领域的一次革命性改进，其特点包括：序列数据高通量、高覆盖率，但测得的DNA序列片段（read）长度很短，适合于大规模高通量的序列数据处理。第二代测序技术的出现为基因组研究领域提供了广阔的发展前景和丰富的数据支持，很多基因组研究领域的遗留难题因此有了新的解决途径，这也带动了整个生物信息学领域的产业化发展。
在第二代测序技术产生的短序列片段数据仍是各个科研小组的主要研究数据时，第三代测序技术已经开始崭露头角。当前的第三代测序技术主要有两种，即由美国太平洋生物科学公司（Pacific Biosciences, Pac Bio）推出的单分子实时测序技术（Single-Molecule Real-Timesequencing technology, SMRT）[3]和由英国牛津纳米孔公司推出的纳米孔测序技术（Nanopore sequencing）[4][5]。这两种测序技术一出现，便引起了生物信息学领域众多科研人员的广泛关注。第三代测序技术的特点是测得的DNA序列片段长度非常长，其平均长度能达到10000bp，但同时以现有的技术测得的序列数据却具有较高的错误率，乃至高达15%左右。尽管如此，这种长测序片段（long read）对于特定的基因组学问题仍然具有非常重要的意义。目前随着第三代测序技术的不断发展以及基因组拼接方法的不断成熟，生物信息学领域产生了越来越多的基因组长序列片段数据。这些基因组长序列数据对于生物信息学领域的许多问题都具有非常重要的研究价值，例如基因组序列组装以及结构变异检测等，目前也已经有许多科研小组基于这种长序列片段测序数据开展了一些相关研究[6][7]，并取得了非常好的效果。
可以预见的是，随着第三代测序技术的不断发展成熟，测序数据一定会朝着片段更长、错误率更低的方向发展。再加上越来越成熟的基因组拼接技术，我们将会得到越来越多的基因组长序列片段数据，而如何利用好这些序列数据，对生物信息学领域的相关研究具有极为重要的意义。生物信息学的研究重点主要体现在基因组学和蛋白质学两方面，也即从核酸和蛋白质序列出发，分析序列中表达结构和功能的生物信息。生物信息学的基本任务就是对各种生物序列进行分析，研究出新的计算机算法，从大量的序列信息中获取基因结构、功能和进化等知识。而在序列分析中，将未知序列同已知的参考序列进行比对是一种基础的研究手段，通过序列比对，进而可以分析不同序列的相似性。从序列的片段测定、拼接、基因的表达分析，到RNA和蛋白质的结构功能预测，物种亲缘树的构建都需要进行生物序列比对和相似性比较。因此生物信息学中，序列比对算法的研究具有非常重要的理论价值和实践意义[8][9]。
