高通量测序数据的基因组测序拼接是基因组学的核心内容。高通量测序数据具有通量高、reads长度短、错误率高的特点,对传统的基于Sanger数据的拼接方法提出了挑战,因此许多优秀的拼接方法应运而生。这些拼接方法主要基于交叠图和De Bruijn图,但其reads交叠长度或k-mer大小固定,这不利于处理拼接过程中出现的分叉(branches)和空隙(gaps),并且这些方法并未充分利用配对数据和单端数据来处理分叉结构。本文针对现有方法的不足,提出基于多重启发式的配对数据引导的拼接方法PERGA。拼接结果(称为contigs)中通常会出现一些拼接错误,目前有两类拼接错误识别方法:基于参考序列的检测方法(Reference-based approach)和无参考的检测方法(De novo approach)。前者未考虑结构变异的影响,后者在处理覆盖深度不均匀的数据时容易引入错误识别,因此这两类识别方法都存在一定的偏差(biases)。本文针对现有拼接错误识别方法的不足,提出无偏的(unbiased)拼接错误检测方法mis Finder。本文的主要内容包括:(1)基于支持向量机的分叉结构处理方法基因组拼接方法主要采用基于交叠图和De Bruijn图,并且在图中通常会出现分叉结构(branches),每个分叉对应一条路径(path),基因组拼接需要从众多候选路径中识别正确的路径。测序碱基错误(sequencing errors)和基因组的重复序列(repeats)是出现分叉结构的两个主要原因。我们分析分叉结构,根据分叉处的reads信息,提取能够区分正确路径和错误路径的特征,建立SVM预测模型,处理由于测序错误导致的分叉。(2)基于向前查看策略的分叉结构处理方法基因组中存在许多高度相似的非精确重复序列(nonexact repeats)和短串联重复序列(short tandem repeats,如长度<100 bp,相邻的两副本的间距<100 bp)。这些重复序列将会在拼接过程中导致分叉。SVM预测模型只考虑分叉处及其之前较短距离的局部分叉信息,并未考虑分叉之后的信息。我们设计了向前查看的方法来处理由于非精确重复序列导致的“气泡结构”,以及由于短串联重复序列导致的分叉,分离其不同的副本,使分叉信息的处理更加准确,提高拼接结果的质量。(3)基于多重启发式的基因组拼接方法现有拼接方法采用固定的交叠长度,不能有效地处理基因组中存在的重复序列和低覆盖区域的gaps,并且未充分利用配对数据和单端数据。针对现有方法存在的不足,我们提出配对数据引导的基因组拼接方法PERGA,以便更好地使用配对数据和单端数据处理分叉结构。PERGA采用多重启发式引导拼接:i)优先使用配对数据扩展contigs,并优先考虑与contigs具有最大交叠的配对数据;ii)如果没有配对数据,则使用与contigs具有最大交叠的单端数据进行扩展;iii)在contigs的扩展过程中遇到分叉时,根据当前的contigs的数据特征,使用SVM预测模型选择路径;iv)如果路径是不能区分的,则在分叉处使用向前查看方法处理非精确重复序列和短串联重复序列。(4)无偏的基因组拼接错误识别方法由于高通量测序数据的reads长度过短,导致基因组拼接结果引入拼接错误,对下游数据分析产生不利影响。基于参考序列的检测方法将拼接结果与参考基因组之间的差异直接视为拼接错误,并未考虑结构变异的影响;无参考的检测方法通过分析比对到拼接结果上的配对reads信息的不一致特征识别错误,容易引入计算偏差。结合上述两种方法,我们提出无偏的基因组拼接检错方法mis Finder,充分利用参考序列和比对到拼接结果上的配对数据信息,根据错拼处的reads数据的多种不一致特征,更加准确地识别拼接错误。