基于概率模型的基因组从头测序算法研究

摘要

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

目录

基于概率模型的基因组从头测序算法研究

RESEARCH ON DNA ASSEMBLY ALGORITHMS BASED ON THE STATISTICAL MODEL

摘 要

Abstract

目 录

第1章 绪论

1.1 课题背景与研究目的及意义

1.2 测序技术发展及其展望

1.3 拼接算法简介

1.3.1 贪婪算法

1.3.2 overlap-layout-consensus算法

1.3.3 基于de bruijn图的算法

1.3.4 拼接算法比较

1.4 论文的主要内容

第2章 测序数据纠错处理

2.1 引言

2.2 纠错算法简介

2.2.1 HiTEC算法

2.2.2 SHREC算法

2.2.3 Reptile算法

2.2.4 纠错方法比较

2.3 数据纠错

2.3.1 数据介绍

2.3.2 利用HiTEC算法纠错

2.4 本章小结

第3章 基于概率模型的基因组从头测序算法

3.1 引言

3.2 原理介绍

3.3 构建概率模型

3.3.1 编码规则

3.3.2 数据存储结构

3.3.3 构建哈希表

3.4 DNA拼接策略

3.4.1 种子选取规则

3.4.2 拼接方法

3.5 本章小结

第4章 基于启发式规则的算法优化

4.1 引言

4.2 无后缀问题及解决方案

4.2.1 退五进八原则

4.2.2 反向拼接策略

4.3 多个后缀问题及解决方案

4.3.1 repeat问题及解决方法

4.3.2 错误高发区问题及解决方案

4.4 本章小结

第5章 实验结果与分析

5.1 实验环境及测试用例

5.2 测试结果分析

5.2.1 与SOAPdenovo比较

5.2.2 与Velvet比较

5.3 本章小结

结 论

参考文献

哈尔滨工业大学学位论文原创性声明及使用授权说明

致 谢