基于de+Bruijn图的DNA+contig生成算法Word下载.docx

基于de+Bruijn图的DNA+contig生成算法Word下载.docx

《基于de+Bruijn图的DNA+contig生成算法Word下载.docx》由会员分享，可在线阅读，更多相关《基于de+Bruijn图的DNA+contig生成算法Word下载.docx（155页珍藏版）》请在冰点文库上搜索。

导

师：

陈彬副教授

申请学位：

工学硕士

学

科：

计算机科学与技术

所在单位：

计算机科学与技术学院

答辩日期：

授予学位单位：

ClassifiedIndex:

TP319

U.D.C:

621.3

DissertationfortheMasterDegreeinEngineering

Candidate：

Supervisor：

AcademicDegreeAppliedfor：

Specialty：

Affiliation：

DateofDefence：

Degree-Conferring-Institution：

WangXu

AssociateProf.ChenBin

MasterofEngineering

ComputerScienceandTechnology

SchoolofComputerScienceand

Technology

June,2011

HarbinInstituteofTechnology

哈尔滨工业大学工学硕士学位论文

摘

要

为了探索生命的本质，人们迫切希望快速地获得新物种个体DNA分子的全部

碱基序列。

现在，新一代测序技术不断发展，但测序过程中DNA分子已被打碎成

碱基片段，于是从头测序被提出来了。

随着第二代、第三代测序技术的产生，人

们能在较短时间内获得大量的测序数据。

测序技术以高通量、低成本、高精度为

发展方向，现在积累的测序数据越来越多。

如何快速、准确地处理海量测序数据

已成为DNA测序发展的瓶颈。

测序之前，DNA分子要经过复制、打碎、过滤等过程，然后通过测序仪，把

DNA片段读出，读出的DNA片段称为读取。

要获得整个DNA分子的碱基序列，

首先要根据读取构造重叠群。

重叠群是由读取相互重叠而成的DNA片段，并且重

叠群上的每个碱基都被一条读取所覆盖。

在本文中，提出了一种新的重叠群生成

算法，叫SRGA。

该算法基于deBruijn图，将从头测序问题转化成一个四叉树的

搜索问题，并采用启发式搜索策略，能够快速地处理海量测序数据，而且能得到

质量较高的重叠群。

本文详细叙述了算法的原理以及实现过程。

为了存储大量的读取，在本文中

使用了一种新的deBruijn图结构。

为了引入启发式规则，决策表结构是必要的。

决策表中保存了正在参与拼接的读取，后继k-mer就是由这些读取决定的。

当选定

后继k-mer时，决策表需要更新。

算法中通过不断选取后继k-mer，来扩展重叠群。

故后继k-mer的选取是一个非常重要的过程，只有选择了正确的后继k-mer才能得

到质量较高的重叠群。

本文提出了读取锁定策略，即通过设置决策表中的锁定位，

将一些快要成功拼接的读取锁定，令后继k-mer由这些读取产生。

这样可以保证重

叠群上每一个碱基都被一个成功拼接的读取所覆盖。

最后，本文将SRGA与EULER算法进行了比较。

发现EULER产生的重叠群

较短，数量较多，单条重叠群与参考基因组匹配较好，但总体覆盖度较低。

而SRGA

能产生较长的重叠群，且使用了更少的时间与内存。

虽然单条重叠群与参考基因

组匹配稍差，但总体覆盖度较高。

关键词：

从头测序；

启发式搜索；

deBruijn图；

决策表

-I-

Abstract

Inordertoexploretheessenceoflife,peopleareeagertogetallthebasesonDNA

moleculesofnewspeciesquickly.Now,anewgenerationofsequencingtechnologyis

developingonandon,butintheprocessofsequencing,DNAhasbeenbrokeninto

fragments.Sodenovosequencingisproposed.Asthesecondgeneration,third

generationsequencingtechnologygenerated,peoplecangetalotofsequencedataina

relativelyshortperiodoftime.Thesequencingtechnologyisdevelopinginthedirection

ofhigh-throughput,lowcostandhigh-precision,whichleadstomoreandmore

sequencingdataareaccumulated.Howtoquicklyandaccuratelyhandlethemassive

sequencingdatahasbecomethebottleneckofthedevelopmentofDNAsequencing.

Beforesequencing,DNAmustbecopied,smashedandfiltered,andthenthe

sequencerreadDNAfragmentsout.TheseDNAfragmentsarecalledreads.First,we

mustgeneratecontigsfromreads.AcontigissuchaDNAfragmentthatisovoerlaped

byreads,andeachbaseiscoveredbyaread.Inthispaper,weproposeanewdenovo

sequencingalgorithm,calledSRGA.ThisalgorithmisbasedondeBruijngraph,andit

transformsthedenovosequencingproblemintoaquadtreesearchproblem.Inthis

algorithmheuristicsearchstrategyisused,soitisabletodealwithmasssequencing

dataquicklyandthecontigsgeneratedfromthealgorithmhavehighquality.

Inthispaper,theprincipleandtherealizationofthealgorithmisdescribed

detailedly.Inordertosaveagreatdealofreads,anewdeBruijngraphisused.Decision

tableisessentialforheuristicrules.Assemblingreadsaresavedinthedecisiontable,

andthesereadsdecidewhichk-meristhesubsequentk-mer.Thedecisiontableneedsto

beupdatewhenasubsequentk-merischosen.Wechoosesubsequentk-merrepeatedly

toextendcontig.Sochoosingthesubsequentk-merisanimportantprocess.Ifandonly

iftherightsubsequentk-merischosencanwegetthecontigwithhighquality.Here

lockedreadstrategyisproposed.Somereadswhichareaboutsuccesscanbelocked

throughsetthelockedbitinthedecisiontableandthenthelockedreadswilldecide

whichk-meristhesubsequentk-mer.Thisensuresthateachbaseonthecontigcanbe

coveredbyasuccessfulassemblingread.

Atlast,wecompareSRGAwithEULER.EULERproducesshortetcontigs,and

eachcontigcanmatchreferencegenomewell,butoverallcoverageislow.SRGA

produceslongercontigs,anduseslesstimeandmemory.Althougheachcontigcannot

matchreferencegenomewell,yetoverallcoverageishigh.

Keywords：

denovosequencing，heuristicsearch，deBruijngraph，decisiontable

-II-

目

录

要...............................................................................................................................I

Abstract.............................................................................................................................II

第1章绪论....................................................................................................................1

1.1课题背景...............................................................................................................1

1.2研究目的和意义...................................................................................................2

1.3国内外研究现状和分析.......................................................................................4

1.4基于deBruijn图的算法概述..............................................................................6

1.4.1deBruijn图简介...............................................................................................6

1.4.2基于deBruijn图算法的一般步骤.................................................................7

1.5本文主要研究内容...............................................................................................7

1.5.1基因组中存在大量重复片段..........................................................................8

1.5.2测序过程中可能出现错误..............................................................................8

1.5.3建立deBruijn图.............................................................................................9

1.5.4更新决策表策略..............................................................................................9

1.5.5后继k-mer选取策略.....................................................................................10

第2章拼接模型...........................................................................................................11

2.1数据分析..............................................................................................................11

2.2问题建模..............................................................................................................11

2.3模型分析.............................................................................................................12

2.4模型求解.............................................................................................................13

2.4.1拼接总体思路................................................................................................13

2.4.2contig的构建过程..........................................................................................14

2.5本章小结.............................................................................................................19

第3章contig生成算法...............................................................................................20

3.1deBruijn图的建立..............................................................................................20

3.1.1debruijn图的数据结构..................................................................................20

3.1.2deBruijn图的建立过程.................................................................................23

3.1.3有关deBruijn图的基本操作.......................................................................26

3.2构建contig..........................................................................................................27

3.2.1决策表更新过程............................................................................................27

-III-

3.2.2后继k-mer选取过程.....................................................................................33

3.2.3contig构建过程的其他模块..........................................................................36

3.3本章小结.............................................................................................................36

第4章结果及评价......................................................................................................37

4.1算法的输入与输出.............................................................................................37

4.2评价内容.............................................................................................................38

4.3评价方法.............................................................................................................41

4.4评价结果.............................................................................................................43

4.5本章小结.............................................................................................................44

结

论............................................................................................................................46

参考文献........................................................................................................................48

哈尔滨工业大学硕士学位论文原创性声明................................................................50

哈尔滨工业大学硕士学位论文使用授权书................................................................50

致

谢............................................................................................................................51

-IV-

第1章绪论

1.1课题背景

分子生物学是一门从分子水平上研究生命现象物质基础的学科，主要研究细

胞成分的物理、化学的性质和变化以及这些性质和变化与生命现象的关系。

而生

物信息学则是一门综合计算机科学、信息技术和数学的理论和方法来研究生物信

息的交叉学科，主要包括生物学数据的研究、存