【正文】 了名為 EULER的拼接 算法軟件包 。在國(guó)內(nèi)，中科院計(jì)算技術(shù)研究所與華大基因研究中心合作，基于曙光 3000 超級(jí)計(jì)算機(jī)系統(tǒng)，開發(fā)了 Phrap 的并行算法，實(shí)現(xiàn)了 Phrap 的并行化。 圖 15 基因測(cè)序過程示意圖 基因組重測(cè)序技術(shù) 基因組重測(cè)序顧名思義是對(duì)于已經(jīng)測(cè)序完成的序列，由于某種 需求 （如設(shè)計(jì)標(biāo)記、 SNP 挖掘 、尋找結(jié)構(gòu)變異位點(diǎn) 等）要對(duì)此物種中的不同 個(gè)體進(jìn)行 再次測(cè)序。 基因組無模版拼接技術(shù) 基因組 無模版拼接技術(shù)，又叫 基因組 從頭 拼接 即 de novo 測(cè)序， 指 不需要任何參考序列資料即可對(duì)某個(gè)物種 的基因 進(jìn)行測(cè)序，用生物信息學(xué)分析方法進(jìn)行拼接、組裝，從而獲得該物種的基因組序列圖譜。 新一代基因測(cè)序技術(shù)所產(chǎn)生的序列片段具有序列短、高覆蓋度、額外的雙端信息等特點(diǎn) ,這使得原有的一些傳統(tǒng)的拼接技術(shù)無法使用 ,加大了拼接問題的復(fù)雜度和難點(diǎn)。 3． 將糾錯(cuò)之后的 read pair 讀入到內(nèi)存中， 設(shè)定 kmer，構(gòu)建 de Bruijn 圖數(shù)據(jù)結(jié)構(gòu)來表示 read 間的 重復(fù)區(qū)域（ overlap） 。 7． 最后，使用 讀長(zhǎng)對(duì) 來填補(bǔ) 多個(gè) contig之間的空缺 (Gap)， 從而 得到比 contig更長(zhǎng)的 scaffolds。 5． 在簡(jiǎn)化圖的基礎(chǔ)上，利用找到一條最優(yōu)路徑， 根據(jù)最優(yōu)路 徑 輸出 最終的拼接 序列 (contigs)。 基于 de Bruijn 圖的拼接 方法 簡(jiǎn)要步驟 如下： 1． 先將基因組按照一定的覆蓋度生成多個(gè)副本，然后將所有的副本基因 包括原始基因組進(jìn)行 隨機(jī) 打散， 利用相關(guān)的方法 進(jìn)行雙端測(cè)序， 最終 得到 該生物的基因組序列 數(shù)據(jù)（ read pair） ， 數(shù)據(jù)文件（ fastq 格式 ） 中包含每個(gè)堿基的質(zhì)量系數(shù) 。一個(gè)物種基因組序列圖譜的完成，意味著這個(gè)物種學(xué)科和產(chǎn)業(yè)的新開 端！這也將帶動(dòng)這個(gè)物種下游一系列研究的開展。全基因組重測(cè)序是對(duì)已知基因組序列 （參考基因）的物種進(jìn)行不同個(gè)體的基因組測(cè)序，并 分析 個(gè)體或群體 的 差異性 ，從而發(fā)現(xiàn)生物的遺傳特性 。第二，就提高序列拼接速度問題而言，單機(jī)上的拼接算法研究已經(jīng)相當(dāng)廣泛深刻，機(jī)群系統(tǒng)上的拼接算法研究剛剛開始。 國(guó)內(nèi)在片段拼接方面的研究主要開始于近幾年，目前主要集中在北京大學(xué)和中科院北京華 人基因研究中心，后者承擔(dān)和完成了 HGP 國(guó)際大合作中 1%的測(cè)序工作并在國(guó)際上首次獨(dú)立進(jìn)行在中國(guó)廣泛種植的水稻 ( Oryza sative L. ssp. Indica)全基因組的測(cè)序拼接工作，并取得成功。 Phil Green 小組一直在不斷地完善和改進(jìn)該套系統(tǒng)。 gordon et al.,1998)。當(dāng)前世界范圍內(nèi)的主要測(cè)序中心以及重要的測(cè) 序工程都普遍采用了鳥槍(Shotgun)測(cè)序法。 另外，這樣的序列片段中還可能隱含錯(cuò)誤的信息?，F(xiàn)在還不能直接測(cè)定整個(gè)分子的序列，然而，可以得到待測(cè)序列的一系列序列片段。人類基因組計(jì)劃（ HGP）采用的就是這種策略。核苷酸由堿基區(qū)分， DNA中，堿基分別是腺嘌呤 (Adenine)、胞嘧啶 (Cytosine)、鳥嘌呤 (Guanine)和胸腺嘧啶 (Thymine)，分別用字母 A， C， G， T 表示。經(jīng)過基因測(cè)序就可以得到每條染色體中的基因序列，這樣的序列并非是完整的，而是一些短小的、重復(fù)的、無序的、包含錯(cuò)誤的序列片段（術(shù)語稱“ reads”，讀長(zhǎng)）。相信將來大規(guī)模測(cè)序工作將轉(zhuǎn)移到大型的商業(yè)化的公司和服務(wù)商，而不是在小型的實(shí)驗(yàn)室和小型的研究中心中進(jìn)行，倘若現(xiàn)在的預(yù)期能變?yōu)楝F(xiàn)實(shí)， 500 元測(cè)定個(gè)人基因組的愿望還是可以實(shí) 現(xiàn)的。 隨著新一代測(cè)序技術(shù)的發(fā)展，完全可以實(shí)現(xiàn)將測(cè)定一個(gè)人的基因組的全部成本控制在 500 元到 5000 元 之內(nèi)。具有讀長(zhǎng)優(yōu)勢(shì)以及原始數(shù)據(jù)準(zhǔn)確的 Sanger 法將用于小規(guī)模測(cè)序的縫隙市場(chǎng)，而第二代和第三代測(cè)序儀將用于大規(guī)模的項(xiàng)目。新一代測(cè)序技術(shù)將憑借低成本、高通量、長(zhǎng)讀長(zhǎng)等各大顯著特點(diǎn)引領(lǐng)測(cè)序技術(shù)走向嶄新的時(shí)代。然而納米孔測(cè)序的準(zhǔn)確度依然不盡如人意，目前其測(cè)序錯(cuò)誤率在 4%左右。但是， SMRT 測(cè)序技術(shù)目前仍處于試用階段。目前 HeliScope 測(cè)序技術(shù)已有所應(yīng)用，但是由于單分子測(cè)序設(shè)備價(jià)格十分昂貴，使其推廣應(yīng)用存在一定困難。 Ion torrent 測(cè)序技術(shù)摒棄了 454 測(cè)序技術(shù)中采用生物發(fā)光檢測(cè)延伸產(chǎn)生的焦磷酸的檢測(cè)原理，通過檢測(cè) DNA 鏈延伸時(shí)產(chǎn)生的氫離子實(shí)現(xiàn)邊合成邊測(cè)序。 第三代測(cè)序 技術(shù) 的關(guān)鍵優(yōu)勢(shì)是能夠?qū)?單個(gè) DNA（脫氧核糖核酸）分子進(jìn)行測(cè)序，而目前市場(chǎng)上的主流測(cè)序儀只能對(duì)分子群體進(jìn)行平均測(cè)序。下一小節(jié)就這些新一代測(cè)序技術(shù)的原理、特點(diǎn)和應(yīng)用前景作簡(jiǎn)要介紹。 目前尚未測(cè)序的物種基因組也能應(yīng)用新一代測(cè)序技術(shù)，不過目前主要集中在454 測(cè)序儀，因?yàn)樗淖x長(zhǎng)較長(zhǎng)，而其他測(cè)序儀器應(yīng) 用主要集中在微生物的基因組從頭測(cè)序。對(duì)于已有基因組參考序列的物種，可以以更低的成本對(duì)更多具有不同性狀特征的品種和個(gè)體進(jìn)行基因組重測(cè)序研究。自動(dòng)化桑格測(cè)序法生成的 read 長(zhǎng)度能達(dá)到 1000bp，而第二代測(cè)序技術(shù)得到的 read 長(zhǎng)度與第一代測(cè)序技術(shù)相比顯得較短， 454 測(cè)序技術(shù)生成的 read 較長(zhǎng)，能達(dá)到 250400bp，而 SOLiD 測(cè)序技術(shù)得到的 read 長(zhǎng)度在 2550bp。第二代測(cè)序技術(shù)以 Sanger 研 究所現(xiàn)在使用的 Illumina 新一代儀器為例，算上樣品準(zhǔn)備、儀器運(yùn)行、數(shù)據(jù)分析的時(shí)間，平均一臺(tái)儀器在一個(gè)月內(nèi)就可以產(chǎn)生相當(dāng)于 1 個(gè)人全基因組圖譜的數(shù)據(jù)，而其運(yùn)行成本已經(jīng)降到一兩萬美元左右的量級(jí)，平均每兆數(shù)據(jù) 2 美元左右。 第二代測(cè)序技術(shù)的一個(gè)芯片上可以并行同時(shí) 執(zhí)行上百萬個(gè) DNA 片段的測(cè)序，因而有比 Sanger 測(cè)序技術(shù)高得多的通量。將待測(cè) DNA 片斷固定到磁珠表面，然后 PCR 擴(kuò)增獲得大量待測(cè) DNA 片斷的拷貝。454 測(cè)序儀測(cè)序的價(jià)格較昂貴，雖然是傳統(tǒng) Sanger 測(cè)序儀費(fèi)用的 1/10，但卻是 天津工業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 6 其他新一代測(cè)序儀測(cè)序費(fèi)用的 10 倍左右。 454 測(cè)序技術(shù)原理如下 ： 首先將基因組打碎為短 DNA 片段，再將這些 DNA片段固定在特別設(shè)計(jì)的 DNA 捕獲磁珠上。由于所有的克隆都在同一平面上，這些反應(yīng)就能夠大規(guī)模平行進(jìn)行。他們被稱為第二代測(cè)序技術(shù)。通常譜帶中達(dá)到峰值時(shí)最亮的顏色所代表的堿基被讀出，有時(shí)會(huì)出現(xiàn)幾種亮度相近的情況，這可能會(huì)帶來一定差錯(cuò) 。通過高分辨率變性聚丙烯酰胺凝膠電泳分離這些片段，隨后利用放射自顯影就可以讀出DNA 的序列。 2． 序列測(cè)定：聚合酶用單鏈 DNA 模板作指導(dǎo)，不斷地將 dNTP 加到引物的 339。 第一代測(cè)序技術(shù) 于 1976 年問世 的 Sanger 自動(dòng)化測(cè)序技術(shù) ， 代表了 廣泛使用的鳥槍法 的 第一代測(cè)序技術(shù) 。 核苷酸由堿基區(qū)分， DNA 中，堿基分別是腺嘌呤 (Adenine)、胞嘧啶 (Cytosine)、鳥嘌呤 (Guanine)和胸腺嘧啶 (Thymine)，分別用字母 A， C， G， T 表示。 DNA 是由核苷酸單體構(gòu)成的線性、無分支的多聚分子。覆蓋度是指測(cè)序獲得的序列占整個(gè)基因組 的比例。 8． 測(cè)序深度和覆蓋度 ： 測(cè)序深度是指 一次 測(cè)序得到的 所有的 堿基 的總數(shù) 數(shù)與 被 測(cè) 生物 基因組大小的比值，它是評(píng)價(jià) 基因 測(cè)序量的指標(biāo)之一。 Contig N50 是一個(gè)常見的評(píng)價(jià) 基因組拼接的結(jié)果好壞的 指標(biāo) 。 6． Contig N50： 拼接算法將所有的讀長(zhǎng)經(jīng)過拼接得到的很多更長(zhǎng)的序列contig。這個(gè) scaffold 所做的事情。一般的拼接軟件會(huì)得到很多條 contig，需要進(jìn)一步根據(jù) read pair 之間的信息進(jìn)行組裝，產(chǎn)生更長(zhǎng)的序列，從而完成拼接任務(wù)。高通量測(cè)序中 read 一般會(huì)成對(duì)出現(xiàn) ，也就是以 readpair 形式存在 。 利用全基因組無模板 拼接 技術(shù)，可以獲得動(dòng)物、植物、細(xì)菌、真菌的全基因組序列，從而推進(jìn)該物種的研究。 因此基因拼接還有很大的提升空間。配對(duì) 的 讀 長(zhǎng)， 構(gòu)成了強(qiáng)大的信息源，大大促進(jìn)了基因組 拼接 。 這種海量的、短小的、包含錯(cuò)誤的讀長(zhǎng)數(shù)據(jù)導(dǎo)致了拼接的高難度。另外， 對(duì)進(jìn)行基因診斷、基因治療、藥物設(shè)計(jì)都有巨大的作用。 基因組測(cè)序的 目的 就是要確定 DNA 分子的堿基序列，而 DNA 序列拼接則是基因組測(cè)序的關(guān)鍵技術(shù)之一。 自從 2021 年 5 月 18 日 《自然》雜志 報(bào)道稱， 科學(xué)家已對(duì)含有 億個(gè)堿基對(duì)占人類基因組中堿基對(duì)總量的 8%左右的人類第一號(hào)染色體完成測(cè)序宣告持續(xù) 16 年的人類基因組計(jì)劃全部完成 [1]。 Incorporates。 當(dāng)更多的 基 算法結(jié)果加入到我們的算法中 ，結(jié)果將會(huì)有更大的提高。 對(duì)以上多個(gè)算法的結(jié)果進(jìn)行詳細(xì)的分析，我們提出了一種 基于圖論的算法，在 多個(gè)不同 基 算法拼接出的 contigs 的基礎(chǔ)上通過構(gòu)建索引、讀長(zhǎng)映射、 contig聚簇、構(gòu)建簇圖等步 驟將 contig 拼接成更長(zhǎng)的 稱為 scaffold 序列。 另外高等生物的基因還具有非常復(fù)雜的重復(fù)結(jié)構(gòu)，因而基因組的無 模板 拼接 具 有很大難度 。 15 論文有獨(dú)到見解或有一定實(shí)用價(jià)值。 10 文字通順，用語正確，基本無錯(cuò)別字和病句，圖表清楚，書寫格式符合規(guī)范。題目大小、難度適中，學(xué)生工作量飽滿，經(jīng)努力能完成。一個(gè)物種基因組序列圖譜的完成，意味著這個(gè)物種學(xué)科和產(chǎn)業(yè)的新開端，這也將帶動(dòng)這個(gè)物種下游一系列研究的開展。比較 各項(xiàng)指標(biāo) N50、 MAX。 ① 構(gòu) 建子圖，并拼接。尋找潛在可拼接的 contig 對(duì)是任何兩個(gè)不同拼接算法中的 contig 映射到的集合 彼此之間交集的元素個(gè)數(shù)超過一個(gè)給定閾值。 ○ 4 .我們?cè)试S最少 2 個(gè)堿基，最多 2%個(gè)堿基的錯(cuò)誤。映射結(jié)果一般表現(xiàn)為：一個(gè) contig 的不同的位置上有多個(gè) read 對(duì)應(yīng)。將每個(gè)算法生成的 contigs 集合建立一個(gè)索引結(jié)構(gòu)，生成索引文件。 算法具體步驟如下： (1) 獲 得其他 算法 產(chǎn)生 contigs。 本文提出了一個(gè)基于圖論的算法，對(duì)多個(gè)不同算法拼接出的 contigs 進(jìn)行拼接， 得到更長(zhǎng)的 scaffold序列。 盡管人們普遍認(rèn)識(shí)到，不同拼接算法所產(chǎn)生的結(jié)果具有互補(bǔ)的，但是現(xiàn)在還沒有一個(gè)方法能融合多個(gè)拼接算法的結(jié)果。12 Special Issue, Bioinformatics[J]. 2021,28 i311i317 [2] MacCallum,I. et al. ALLPATHS 2: small genomes assembled accurately and with high continuity from short paired reads[J]. Genome Biol. 2021, 10, R103 [3] Simpson,. et al. ABySS: a parallel assembler for shortread sequence data[J]. Genome Res. 2021, 19, 1117–1123 [4] Zerbino,. and Birney,E. Velvet: algorithms for de novo shortread assembly using de Bruijn graphs[J]. Genome Res. 2021, 18, 821–829 [5] Li,R. et al. De novo assembly of human genomes with massively parallel shortread sequencing[J]. Genome Res. 2021, 20, 265–272 起止日期 2021 年 2 月 25 日至 2021 年 6 月 6 日 備注 院長(zhǎng) 教研室主任 指導(dǎo)教師 畢業(yè)論文 開題報(bào)告 表 2021 年 3 月 8 日 姓名 徐 學(xué)院 計(jì)算機(jī)科學(xué)與軟件 專業(yè) 軟件工程 班級(jí) 軟件 題目 基于高重復(fù)區(qū)域基因序列的無模板拼接算法 指導(dǎo)教師 陳 一、與本課題有關(guān)的國(guó)內(nèi)外研究情況、課題研究的主要內(nèi)容、目的和意義： 1. 與本課題有關(guān)的國(guó)內(nèi)外研究情況 隨著新一代基因組測(cè)序技術(shù)的推廣使用 ，全基因組 Shotgun 拼接算法和軟件 得 到了廣泛的研究。 天津工業(yè)大學(xué) 畢業(yè)論文 基于高重復(fù)區(qū)域基因序列的無模板拼接算法 姓 名 徐 學(xué) 院 計(jì)算機(jī)科學(xué)與軟件 專 業(yè) 軟件工程 指導(dǎo)教師 陳 職 稱 副教授 2021 年 5 月 27 日 天津工業(yè)大學(xué)畢業(yè) 論文任務(wù)書 題目 基于高重復(fù)區(qū)域基因序列的無模板拼接算法