结构变异(Structural Variation,SV)通常是指规模介于单核苷酸多态性(single nucleotide polymorphism,SNP)和染色体变异之间的基因组变异形式,是生物遗传多样性的重要组成部分,不仅能够导致个体之间的表型差异,而且也与多种疾病的发生存在密切的联系。高通量测序技术的不断发展和广泛应用,为结构变异的预测和研究提供了技术支持。然而,数量规模庞大的短读长测序数据给结构变异预测带来了困难和挑战。基于高通量测序的基因组结构变异预测问题已经成为生物信息学领域的研究热点。由于包括人类在内的大部分动物和一半以上的高等植物,都是属于二倍体基因组。因此,重点围绕二倍体基因组展开研究,设计有效的结构变异预测分析算法,不仅能够提高预测结果的精确度和敏感度,有利于探索结构变异与重大疾病的内在关联,更能为多倍体基因组结构变异预测研究奠定基础。本文重点面向双序列比对问题和不同类型的结构变异预测问题进行研究,提出了一种双序列比对改进算法,以及基因组结构变异预测算法,以提高不同类型结构变异预测结果的精确度和敏感度。本文的主要内容和创新点如下:1.现有的双序列比对算法的回溯过程是严格按照最优解的来源方向执行的,容易造成比对结果中碱基过早匹配而不利于发现更长的空位片段,导致比对结果与InDel变异的实际情况产生偏差。另外,相对固定的空位罚分也不利于比对结果中增加空位和减少碱基错配。本文从动态空位罚分调整策略、算法逆推策略和得分矩阵单元格计算方法三个方面对Needleman-Wunsch算法进行了优化和改进,提出了一种DNA双序列全局比对改进算法(DNA-NW)。由于改进算法的逆推策略不再严格按照最优解的来源方向执行,因此不再使用名词“回溯”,而称之为逆推策略。该算法分为预处理阶段和比对执行阶段,预处理是通过基于莱温斯坦距离的动态空位罚分策略(DGPS-LD)实现,根据计算出的两条序列的莱温斯坦距离动态调整空位罚分的分值,使得比对结果更加倾向于增加空位;比对执行阶段是利用Needleman-Wunsch改进算法(INW)实现。尤其是Needleman-Wunsch改进算法(INW)不仅执行效率高于原有的Needleman-Wunsch算法,而且采用新的逆推策略能够在保证最优比对得分不变的前提下找到更长的空位片段,减少错配个数,在降低假阳性SNP可能性的同时,能够预测出更长的InDel变异,使得DNA序列比对结果较好的符合了 InDel变异的实际情况,更加有利于InDel变异的预测。2.对InDel及其预测方法现状进行了综述,介绍了高通量测序原始数据的质控与预处理方法。针对长度小于50 bp的InDel预测问题展开研究,提出了一种基于拆分读片段(split read)的InDel预测与分析方法(SRInDel)。该算法首先划定拆分读片段在参考基因组上的比对目标区域,再利用基于k-mer短序列的比对目标区域修正算法进一步缩小参考基因组参与比对的区域长度,使得序列比对结果中更容易出现插入变异。序列比对过程是使用本文第2章提出的DNA双序列全局比对改进算法(DNA-NW)实现的,根据比对结果可以有效预测出InDel变异的类型、长度和断点位置。针对均聚物序列中可能出现的测序错误问题,提出了 InDel预测结果的修正方法,设计了编码区InDel及移码突变的预测方法,还提出了InDel纯合性和杂合性的判别方法。此外,针对短串联重复序列的预测问题,提出了一种基于k-mer短序列的预测方法(kmer-STR)。与常用的短串联重复预测算法SSRIT相比,kmer-STR算法在保证结果正确性的前提下,显著提高了算法的执行效率,并能适用于大规模基因序列中短串联重复的预测过程。3.介绍了结构变异的主要类型及其预测方法的发展;针对50bp以上的结构变异预测问题展开研究,重点研究插入变异、缺失变异、倒位变异、染色体内易位和染色体间易位等类型的结构变异特征,提出了一种基于不一致读片段对和split read的结构变异预测方法SVDS。该预测方法能够预测插入变异、缺失变异、倒位变异、染色体内易位和染色体间易位五种主要的结构变异类型。该结构变异预测算法的一个显著特点是在序列比对时保留每条paired-end read的多个可能的比对结果,从而增加结构变异预测的敏感度。同时,计算每个候选结构变异的发生概率,并利用集合覆盖问题过滤候选结果中的假阳性结构变异,从而使算法在敏感度和精确度两个方面都获得了较大的提升。4.针对长度在lkb以上的拷贝数变异预测问题,本文提出了一种基于隐马尔科夫模型的拷贝数变异预测算法(CNV-HMM)。为了提高预测结果的精确度,本文分别对read深度信号的统计和概率建模问题、测序数据的GC偏好性及其校正、比对率及其对read深度的影响等方面进行了研究,并提出相应的解决方法。为了进一步提高拷贝数变异预测结果的敏感度和精确度,CNV-HMM算法还使用了基于split read的结果优化方法,不仅能够过滤部分假阳性拷贝数变异,还能够通过合并相同的变异从而得到更长的拷贝数变异预测结果。