论文部分内容阅读
基因组测序是生物信息学的核心,有着极其重要的应用价值。近些年来,新的测序技术大量涌现,与传统的Sanger方法相比,这些方法产生的read(由测序仪直接测得的DNA片段)长度更短,数量更多,覆盖率更大。然而,传统的拼接算法并不适用于利用短read进行拼接,新的拼接算法在拼接效果上仍有待提高,因此本文提出了一种全新的DNA拼接算法,即基于概率模型的基因组从头测序算法。本文首先分析三种通用的纠错方法,因为read中存在大量测序错误的碱基,这势必会降低拼接结果的准确性,所以有必要在拼接前利用纠错方法修正测序错误的碱基。本文研究的基于概率模型的基因组从头测序算法克服了原有拼接算法过度依赖碱基片段之间重叠信息的缺陷,创造性地将DNA拼接过程抽象为二阶离散马尔可夫过程,与此同时,每一条碱基片段被抽象为系统中的一个状态。算法首先构建概率模型存储系统的状态序列和全部转移概率,然后给定系统中的两个前驱状态,结合最大转移概率原则便可确定下一个最佳状态,最后用最佳状态更新前驱状态,重复上述过程,当前状态序列的长度便得到不断地扩展,当不存在最大转移概率时,便生成了一条满足一定长度要求的状态序列,即一条contig(拼接所得的一定长度的DNA片段)。重复上述过程,算法最终便可拼接出一定数量的contig。然而,在实际拼接过程中会出现无后缀、repeat以及错误高发区问题,这大大增加了DNA拼接的难度。本文采用一系列启发式规则对算法进行优化,从而解决了上述拼接难题。将基于概率模型的基因组从头测序算法对大肠杆菌序列数据的拼接结果同SOAPdenovo和Velvet方法进行比较,通过观察拼接所得到的contig的数量、总长度、最大长度、平均长度以及时间消耗等信息可知,基于概率模型的基因组从头测序算法有较好的拼接效果。