【文章內(nèi)容簡介】 ................. 21 第三章 融合的基因組無模版拼接方法的實現(xiàn) ................................... 22 融合的拼接算法的簡介 ................................................................................ 22 數(shù)據(jù)準備 ........................................................................................................ 22 構(gòu)建索引 ........................................................................................................ 22 讀長映射 ........................................................................................................ 23 Contig 聚簇 ..................................................................................................... 23 構(gòu)建簇圖 ClusterGraph ................................................................................ 25 生成拼接結(jié)果 ................................................................................................ 26 第四章 實驗和結(jié)果評價 ...................................................................... 28 運行環(huán)境 ........................................................................................................ 28 實驗機器 .............................................................................................. 28 軟件包依賴 .......................................................................................... 28 數(shù)據(jù)集 ............................................................................................................ 29 準備數(shù)據(jù)庫 .......................................................................................... 29 數(shù)據(jù)預處理 .......................................................................................... 29 算法軟件包說明 ............................................................................................ 31 實驗結(jié)果分析 ................................................................................................ 32 小結(jié) ................................................................................................................ 34 第五章 結(jié)論和展望 .............................................................................. 35 結(jié)論 ................................................................................................................ 35 展望 ................................................................................................................ 36 參考文獻 ............................................................................................... 38 附錄 文獻翻譯 ................................................................................... 40 英文原文 ........................................................................................................ 40 中文譯文 ........................................................................................................ 47 謝 辭 ................................................................................................... 53 天津工業(yè)大學 2021 屆本科生畢業(yè)論文 1 第一章 緒 論 背景 目的和意義 生物信息學是以計算機為工具對生物信息進行存儲、檢索和分析的科學，是當前自然科學前沿領(lǐng)域之一，也將是 21 世紀自然科學的核心領(lǐng)域之一 [34]。生物信息學是研究生物信息的獲取、處理、存儲、分析和解釋等方面的一門綜合學科，通過計算機科學和信息技術(shù)而揭示大量而復雜的生物數(shù)據(jù)所包含的生物學奧秘。生物信息學還有一個重要的活動就是開發(fā)出一些工具軟件進行分析和處理，從而得到一些有用的生物學知識。 自從 2021 年 5 月 18 日 《自然》雜志 報道稱， 科學家已對含有 億個堿基對占人類基因組中堿基對總量的 8%左右的人類第一號染色體完成測序宣告持續(xù) 16 年的人類基因組計劃全部完成 [1]。作為人類自然科學史上重要的里程碑 ，“人類基因組”的研究已從“結(jié)構(gòu)基因組”階段進入“功能基因組”階段。在人類基因組計劃后相繼推出的水稻基因組計劃、馬鈴薯基因組計劃、草魚基因組計劃等和快速增長的微生物基因測序“海量”的基因信息的積累催生了“功能基因組”時代的 來臨。針對充分利用“海量”基因組信息的生物信息學不僅應運而生而且為以注釋、闡明基因功和利用基因生物學功能的“后基因組時代”的研究發(fā)揮了重大作用。 基因組測序的 目的 就是要確定 DNA 分子的堿基序列，而 DNA 序列拼接則是基因組測序的關(guān)鍵技術(shù)之一。 DNA 序列拼接 的定義可概括為：從 DNA 片段集合 F 中重構(gòu) 該 DNA 序列 S，其中 F 為該 DNA 序列 S 的子序列 。 無模版拼接 算法，是指在沒有參考基因作為模板的情況下 ,根據(jù) F 重構(gòu) S。 這些重構(gòu)的 DNA 源序列可以被進一步的評估和分析，可以成為解決生物問題的線索，如尋找致病病毒、進行藥物設(shè)計 、研究如何將纖維物質(zhì)轉(zhuǎn)化為生物燃料 、揭示生物遺傳和變異的。另外， 對進行基因診斷、基因治療、藥物設(shè)計都有巨大的作用。 基因組拼接的 挑戰(zhàn)在于將碎片狀的讀長進行重建得到原始的基因組 ?；诨瘜W的 第一代測序技術(shù) 桑格測序方法得到的讀 長 的長度范圍從大約 500 至 1000個堿基。像 Illumina， Complete Genomics 公司 [2]、 Helicos [3]、 454 Life Sciences [4]、 SOLID [5]、 Ion Torrent 公司 [6]等這些新一代的技術(shù)是以犧牲讀 長 的長度為 代價獲得高產(chǎn)量 。 這種海量的、短小的、包含錯誤的讀長數(shù)據(jù)導致了拼接的高難度。 序列拼接問題主 要轉(zhuǎn)化為圖論的知識進行求解。 拼接算法最初階段的提升主要在于如何處理數(shù)據(jù)以及如何檢測重疊區(qū)域。 de Bruijn 圖 [7]已被證明是一個非常有用的數(shù)據(jù)結(jié)構(gòu)，并用于短讀 長拼接 ，像 Velvet [8]、 ABySS [9]、 AllPath 2 [10]、SOAPdenovo [11]、 EULERUSR [12]、 還有 Cortex [13]許多高通量測序平臺產(chǎn)生配對末端或讀長對。配對 的 讀 長， 構(gòu)成了強大的信息源，大大促進了基因組 拼接 。最近的一 些拼接算法將提高使用讀 長 對信息放在最核心的地位，像 ALLPATHS 天津工業(yè)大學 2021 屆本科生畢業(yè)論文 2 LG [14]、 PEAssembler [15]和 基于 Pairend 的 de Bruijn 圖 [16]，他們是較早的一批 創(chuàng)新的使用的短讀長對 進行拼接的算法。 Telescoper [17]算法是以一個較長的序列作為種子進行啟發(fā)式迭代擴展的 。 然后， ALKAN [18]等人在報告中指出，使用短讀長進行人類基因組無模板拼接的結(jié)果比使用長度長拼接得到的參考基因序列還短 16%。 因此基因拼接還有很大的提升空間。 本文就是在此背景下 ，針對上述拼接算法獲得的序列還不夠長并且它們彼此之間具有互補性，我們 提出了 一種基于簇圖的算法，根據(jù) contig 的相關(guān)性，將 contig 聚到多個簇中，并為每一個簇構(gòu)建一個簇圖，通過求解簇圖的最長路徑，得到了更長的 scaffold。另外，利用互補性，本文的算法可以得到比其他任何算法更好的 結(jié)果，這便是本文算法最大的意義所在。 。 利用全基因組無模板 拼接 技術(shù)，可以獲得動物、植物、細菌、真菌的全基因組序列，從而推進該物種的研究。一個物種基因組序列圖譜的完成，意味著這個物種學科和產(chǎn)業(yè)的新開端，這也將帶動這個物種下游一系列研究的開展。全基因組序列圖譜完成后，可以構(gòu)建該物種的基因組數(shù)據(jù)庫，為該物種的后基因組學研究搭建一個高效的平臺 ，為后續(xù)的基因挖掘、功能驗證提供 DNA 序列信息，為疾病、癌癥等的研究提供真實有效的數(shù)據(jù) 。 術(shù)語 本節(jié)主要將文中用到的部分專業(yè)術(shù)語作了簡要的描述 ， 1． Read： 讀長，高通量測序平臺產(chǎn)生的序列就稱為 讀長 ，一次測序中儀器讀取的核苷酸序列，該序列是原始 DNA 序列經(jīng)過隨機打斷生成的碎片序列， 基因序列的無模板拼接（ de novo assembly） 就是要將這些碎片序列拼接成更長的序列。高通量測序中 read 一般會成對出現(xiàn) ，也就是以 readpair 形式存在 。 圖 11 讀長示意圖 2． Contig： 重疊群 ， 是 拼接軟件基于 read 之 間的 重復區(qū)將較短的 read 拼接成為更長 的序列 片段 稱為 contig。理論上同一個染色體上的 read 結(jié)合起來拼出一個 contig，但實際上 很難做 到。 Contig 是最終 得到的 完整的基因組序列的 子序列 。一般的拼接軟件會得到很多條 contig，需要進一步根據(jù) read pair 之間的信息進行組裝，產(chǎn)生更長的序列，從而完成拼接任務。 天津工業(yè)大學 2021 屆本科生畢業(yè)論文 3 圖 12 Contig 示意圖 3． Scaffold： 由拼接的產(chǎn)物 contig 經(jīng)過有效的連接之后產(chǎn)生的更長的序列。在實際情況中， contig 和 contig 之間并不能直接連接起來。很多情況下是它們之間只 有通過它們內(nèi)部的一些小的 read 之間的某些距離信息或者 mate 信息進行連接。這個 scaffold 所做的事情。它借助其他 reads 之間的關(guān)系信息，把 contig 直接的縫隙進行填充。 圖 13 scaffold 示意圖 4． Mate： 是 read pair 中的其中一個 read， read pair 中的兩個 read 一般稱為left read 和 right read。 圖 14 mate pair 示意圖 5． ClusterGraph： 我們算法生成的簇圖，是將同一個簇中的 所有 contig 根據(jù)其匹配的位置 信息建立 的圖結(jié)構(gòu) ，該圖結(jié)構(gòu)由多種類型 的子圖經(jīng)過一系列的節(jié)點合并和分割產(chǎn)生的 。 6． Contig N50： 拼接算法將所有的讀長經(jīng)過拼接得到的很多更長的序列contig。所有的 contig 的長度之和為