【正文】 及建議： 評閱人簽名： 年 月 日 天津工業(yè)大學(xué) 畢業(yè)論文 成績考核表 學(xué)生姓名 徐 學(xué)院名稱 計算機科學(xué)與軟件 專業(yè)班級 軟件 題目 基于高重復(fù)區(qū)域基因序列的無模板拼接算法 1． 畢業(yè)論文 指導(dǎo)教師評語及成績： 指導(dǎo)教師簽字： 年 月 日 2． 畢業(yè)論文 答辯委員會評語及成績： 答辯主 席 （或組長）簽字： 年 月 日 3． 畢業(yè)論文 總成績： 給定成績 給定成績 總成績 (a +b +c ) 成績： 成績： 摘 要 隨著新一代基因組測序技術(shù)的推廣使用，全基因組 Shotgun 拼接算法和軟件得到了廣泛的研究。 當(dāng)前 的基因測序技術(shù) 獲得 的 DNA 序列數(shù)據(jù)相對于第一代測序方法 Sanger 測序表現(xiàn)為：高通量、高覆蓋率、低成本，與此同時 還具有 短讀長、更多類型的錯誤 等特點 。 而且普通高等生物的基因組堿基數(shù)目巨大，如人類基因組總長約 30 億 bp。 另外高等生物的基因還具有非常復(fù)雜的重復(fù)結(jié)構(gòu)，因而基因組的無 模板 拼接 具 有很大難度 。 自從 2021 年以后 ， 出現(xiàn) 了多種基于下一代測序平臺基因序列的從頭拼接算法軟件包，包括 Telescoper、 Velvet、 ABySS、AllPath SOAPdenovo、 EULERUSR、 Cortex 等。 ALKAN 等人在報告中指出，使用短讀長進(jìn)行人類基因組無模板拼接的結(jié)果 比使用 長讀長得到的拼接結(jié)果 還短 16%。 因此，我們很容易認(rèn)識到設(shè)計出更好的算法還有很大的空間。 對以上多個算法的結(jié)果進(jìn)行詳細(xì)的分析，我們提出了一種 基于圖論的算法，在 多個不同 基 算法拼接出的 contigs 的基礎(chǔ)上通過構(gòu)建索引、讀長映射、 contig聚簇、構(gòu)建簇圖等步 驟將 contig 拼接成更長的 稱為 scaffold 序列。構(gòu)建索引和讀長映射兩個步驟旨在通過讀長（ read）找到不同算法獲得的 contig 之間的相關(guān)性，然后通過這個相關(guān)性進(jìn)行聚簇，簇內(nèi)的所有 contig 具有互補性，是潛在的可拼接的 序列 。最后構(gòu)建簇圖， 求解 圖的全局最長路徑 ，得到 拼接的結(jié)果。 實驗結(jié)果表明 ， 算法得到最長的 scaffold 序列的長度 和 scaffold N50 等兩項指標(biāo) ，相對于 目前拼接效果最好的算法 Velvet、 ABySS、 SOAPdenovo 等增長的比例高達(dá) 50%。 當(dāng)更多的 基 算法結(jié)果加入到我們的算法中 ，結(jié)果將會有更大的提高。本文提出的方法大幅度的提高了 contig 的序列的長度，將為進(jìn)一步對基因 評估和分析 降低了難度，為解決生物問題提供了更好的 線索 ， 將迅速加快生物基因組研究的步伐。 關(guān)鍵詞： 無模版 拼接； 重疊群 ； 融合 ； 基因組測序 ABSTRACT The emergence of nextgeneration sequencing platforms leads to resurgence of research in wholegenome Shotgun assembly algorithms and software. DNA sequencing data from recent platforms typically presents higher throughput, higher coverage, lower cost, but shorter read lengths and different error profiles when pared with Sanger sequencing data. Producing highquality de novo assemblies from shortreads remains challenging, primarily because of the plex repeat structures found in the genomes of most higher anisms. Since 2021, several assembly software packages have been created or revised for de novo assembly of nextgeneration sequencing data, including Velvet, ABySS, AllPaths, SOAPdenovo, and Telescoper. Alkan et al. report that a de novo shotgun assembly of the human genome using shortreads is 16% shorter than the reference assembled using more laborious means. Indeed, it is well recognized that there is room for better algorithmic use of the data. After a detailed analysis of the results of these assembly algorithms, we propose a graphbased algorithm, using contigs from some base assembly algorithms by indexing, read mapping, contig clustering and clustergraph building and some other steps with the result of longer sequence called scaffold. By indexing and read mapping, we aim at obtaining the correlation between the contigs from different assembly algorithms, and then clustering these contigs. Contigs in each cluster are considered plementary, potential that could be assembled. Finally, we build a clustergraph for each cluster, the longest path of each clustergraph will be the scaffold produced by our method. The results of our study show that two standard metrics (the largest scaffold and scaffold N50) are increased by 50% when pared to the current best algorithm Velvet, ABySS, and SOAPdenovo. We also demonstrate that the assembly results could be further improved when more base assembly algorithms are included. The proposed method greatly improves the length of contig sequence, reduces the difficulty of further evaluation and analysis of genes, provides better clues to solve biological problems and rapidly accelerates the pace of genomic research anisms. Key words： De novo assembly。 Contig。 Incorporates。 DNA sequencing 目 錄 第一章 緒 論 ....................................................................................... 1 背景目的和意義 .............................................................................................. 1 術(shù)語 .................................................................................................................. 2 基因組測序技術(shù)簡介 ...................................................................................... 4 第一代測序技術(shù) .................................................................................... 4 第二代測序技術(shù) .................................................................................... 5 新一代測序技術(shù) .................................................................................... 7 基因組拼接技術(shù)簡介 ...................................................................................... 9 基因組拼接技術(shù)的研究現(xiàn)狀 ................................................................ 9 基因組重測序技術(shù) ............................................................................ 11 基因組無模版拼接技術(shù) .................................................................... 12 論文組織結(jié)構(gòu) ................................................................................................ 13 第二章 基因組無模版拼接算法 .......................................................... 15 基因組無模版拼接的難點 ............................................................................ 15 當(dāng)前拼接算法采用的兩種途徑 .................................................................... 16 幾種常見的無模版拼接的方法介紹 ............................................................ 18 Velvet 拼接算法 ................................................................................... 18 ABySS 拼接算法 .................................................................................. 18 SOAPdenovo 拼接算法 ........................................................................ 19 Telescoper 拼接算法 ............................................................................ 19 融合的基因組拼接方法 ...............................................................