資源描述:
《基于配對(duì)信息的dna從頭測(cè)序組裝算法研究》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、碩士學(xué)位論文基于配對(duì)信息的DNA從頭測(cè)序組裝算法研究ALGORITHMRESEARCHOFDNADENOVOASSEMBLYBASEDONMATE-PAIR趙瑋哈爾濱工業(yè)大學(xué)2011年6月中圖分類號(hào):TP319學(xué)校代碼:10213
UDC:621.3密級(jí):公開工學(xué)碩士學(xué)位論文基于配對(duì)信息的DNA從頭測(cè)序組裝算法研究碩士研究生:趙瑋導(dǎo)師:權(quán)光日教授申請(qǐng)學(xué)位:工學(xué)碩士學(xué)科:計(jì)算機(jī)科學(xué)與技術(shù)所在單位:計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院答辯日期:2011年6月授予學(xué)位單位:哈爾濱工業(yè)大學(xué)ClassifiedIndex:TP319
U.D.C:621
2、.3DissertationfortheMasterDegreeinEngineeringALGORITHMRESEARCHOFDNADENOVOASSEMBLYBASEDONMATE-PAIRCandidate:ZhaoWeiSupervisor:Prof.QuanGuangriAcademicDegreeAppliedfor:MasterofEngineeringSpecialty:ComputerScienceandTechnologyAffiliation:SchoolofComputerScienceandTechn
3、ologyDateofDefence:June,2011Degree-Conferring-Institution:HarbinInstituteofTechnology哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文摘要進(jìn)入二十一世紀(jì)以來,新一代測(cè)序技術(shù)的出現(xiàn)使得到全基因組的拼接組裝算法備受關(guān)注。以Roche公司454,Illumina公司Solexa,ABI公司SOLiD為代表的新一代測(cè)序技術(shù)產(chǎn)生的數(shù)據(jù)存在測(cè)序片段短、錯(cuò)誤率高等缺點(diǎn),使得傳統(tǒng)的拼接組裝軟件不再適用。但是由于其高通量、低成本的優(yōu)點(diǎn),尤其在細(xì)菌等微生物從頭測(cè)序中取得的成功極大的
4、鼓舞了人們對(duì)新一代測(cè)序技術(shù)的研究熱情。全基因組組裝算法研究是全基因組拼接組裝算法的一個(gè)重要環(huán)節(jié),研究并開發(fā)可運(yùn)行在個(gè)人計(jì)算機(jī)上的獨(dú)立的組裝算法是非常有必要的。面向新一代測(cè)序數(shù)據(jù)的全基因組拼接組裝算法分為兩個(gè)重要的部分,第一個(gè)部分是將新一代測(cè)序技術(shù)產(chǎn)生的DNA片段拼接成contig的過程,稱之為拼接階段。第二個(gè)部分是將拼接階段產(chǎn)生的contigs組裝成scaffold的過程,稱之為組裝階段。本文所要研究的就是全基因組的從頭測(cè)序組裝階段的算法,為達(dá)到這個(gè)目標(biāo),本文在研究新一代測(cè)序技術(shù)原理的基礎(chǔ)上,提出了快速篩選配對(duì)信息的算法與co
5、ntig組裝算法。通過配對(duì)信息庫的構(gòu)造過程,得到了所有contig上面所存在的配對(duì)信息,設(shè)計(jì)了兩個(gè)映射結(jié)構(gòu)獲得任意兩條contig之間的關(guān)聯(lián)關(guān)系,提出了獨(dú)特的數(shù)據(jù)結(jié)構(gòu)來保存任意兩條contig之間的配對(duì)信息數(shù)目,最終完成了從頭測(cè)序組裝算法的設(shè)計(jì)與實(shí)現(xiàn)。提出了快速篩選有效配對(duì)信息的算法以及contig組裝算法,該算法是可運(yùn)行在個(gè)人計(jì)算機(jī)上的串行算法。設(shè)計(jì)了節(jié)省內(nèi)存的數(shù)據(jù)結(jié)構(gòu),提高了算法的速度。充分利用了測(cè)序數(shù)據(jù)的生物學(xué)特征,在不考慮contig之間有重疊的情況下成功組裝了72%的contig。關(guān)鍵詞:DNA序列;從頭測(cè)序;全基因
6、組組裝;配對(duì)信息-I-哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文AbstractAsenteringintothe21stcentury,theemergenceofthenext-generationsequencing
platformsledtoresurgencetheresearchinthewhole-genomeassemblyalgorithmsand
software.DNAsequencingdatafromtheRoche454,IlluminaSolexa,andABISOLiD
platformswhichrep
7、resentthenext-generationsequencingplatformstypicallypresent
shortreadlengths,higherrorrateandothershortcomings.Theseshortcomingsleadto
thetraditionalgenomeassemblyalgorithmsandsoftwarenolongerapplicable.However,
duetoitshighthroughput,lowcost,andespeciallyitssuccess
8、inthedenovo
sequencingofthebacteriawhichgreatencouragepeople’spassionoftheresearchtothe
next-generationsequencingtechnology.Scaffoldingalg