论文摘要
生物信息学是研究对生物数据进行获取、存储、分析等多个方面的一门综合性学科,是生命科学研究的重要组成部分。基因组测序是生物信息学中最基本的研究方向之一,然而大多数生物的基因组都不可能在实验中一次性测得,需要利用序列拼接技术对实验中获得的零散的DNA片段进行拼接操作。当前的序列拼接算法主要有两类:基于Hamilton路径的拼接算法和基于Euler路径的拼接算法。基于Hamilton路径的算法会导致NP-完全问题,具有过高的时间复杂度;基于Euler路径的拼接算法把DNA序列拼接问题转化为在de Bruijn图中寻找Euler路径的问题,存在线性时间算法,但需要的存储空间较Hamilton路径算法多。随着测序技术的发展,测序过程中获得的DNA片段越来越短,基于Euler路径的拼接算法在处理这种短片段拼接时更具优势,是目前序列拼接的重要研究方向。在Euler路径算法中,一个关键步骤是de Bruijn图的构建,一直以来,构建de Bruijn图的方式都没有改变过,总是让后一个k-mer与前一个k-mer之间有k-1个碱基的交叠,相邻的两个k-mer之间相互错开一位。但本文的研究发现,如果让有边连接的两个k-mer之间相互错开两位或者更多位数的碱基,使他们之间有k-2个或者更少的碱基相交叠,会对de Bruijn图结构的复杂性产生重要影响。本文针对这些影响进行详细分析,并设计了一个可以对错位数与de Bruijn图结构关联性信息进行查询的系统。系统运行结果表明,k-mer之间的错位数变化对de Bruijn图结构复杂性确有显著影响,已有的算法如能考虑到错位数的影响,选择合适的错位数来构建结构更加简单的de Bruijn图,并在拼接算法中考虑错位数因素,会得到更好的拼接效果。