【正文】 f human genomes with massively parallel shortread sequencing[J]. Genome Res. 2021, 20, 265–272 起止日期 2021 年 2 月 25 日至 2021 年 6 月 6 日 備注 院長 教研室主任 指導教師 畢業(yè)論文 開題報告 表 2021 年 3 月 8 日 姓名 徐 學院 計算機科學與軟件 專業(yè) 軟件工程 班級 軟件 題目 基于高重復區(qū)域基因序列的無模板拼接算法 指導教師 陳 一、與本課題有關(guān)的國內(nèi)外研究情況、課題研究的主要內(nèi)容、目的和意義： 1. 與本課題有關(guān)的國內(nèi)外研究情況 隨著新一代基因組測序技術(shù)的推廣使用 ，全基因組 Shotgun 拼接算法和軟件 得 到了廣泛的研究。全基因組序列圖譜完成后，可以構(gòu)建該物種的基因組數(shù)據(jù)庫，為該物種的后基因組學研究搭建一個高效的平臺，為后續(xù)的基因挖掘、功能驗證提供 DNA 序列信息，為疾病、癌癥等的研究提供真實有效的數(shù)據(jù)。 天津工業(yè)大學 畢業(yè)論文 基于高重復區(qū)域基因序列的無模板拼接算法 姓 名 徐 學 院 計算機科學與軟件 專 業(yè) 軟件工程 指導教師 陳 職 稱 副教授 2021 年 5 月 27 日 天津工業(yè)大學畢業(yè) 論文任務(wù)書 題目 基于高重復區(qū)域基因序列的無模板拼接算法 學生姓名 徐 學院名稱 計算機科學與軟件 專業(yè)班級 軟件 課題類型 實際課題 課 題意義 利用全基因組無模板 拼接 技術(shù)，可以獲得動物、植物、細菌、真菌的全基因組序列，從而推進該物種的研究。一個物種基因組序列圖譜的完成，意味著這個物種學科和產(chǎn)業(yè)的新開端，這也將帶動這個物種下游一系列研究的開展。 任務(wù)與進度要求 選題確認并完成開題報告、任務(wù)書的填寫、提交、 審核 深入了解課題內(nèi)容、算法分析、確定算法系統(tǒng)框架、熟悉開發(fā)工具 完成算法的邏輯實現(xiàn)，和 算法 工具包的開發(fā)，完成算法系統(tǒng)的大部分功能，初稿完成 進行實驗結(jié)果整理，并在整理中進一步提高拼接序列的的各項指標，二稿完成 畢業(yè)論文 的審核、修改及定稿并裝訂 答辯 主要參考文獻 [1] Bresler, M., Sheehan, S., Chan, ., and Song, . Telescoper: De novo Assembly of Highly Repetitive Regions. ECCB39。 新一代的 基因測序 技術(shù)像 Illumina， Complete Genomics， Helicos， 454 Life Sciences， SOLID and Ion Torrent等， 測序得到的 DNA 序列數(shù)據(jù)相對于第一代測序 方法 Sanger 測序表現(xiàn)為 ：高通量、高覆蓋率、低成本，與此同時短讀長、 更多 類型的錯誤，而且普通高等生物的基因組堿基數(shù)目巨大，如人類基因組總長約 30億 bp，而按新一代的測序技術(shù)，一次實驗最多只能直接測得不大于 1, 000 個堿基 ， 另外高等生物的基因還具有非常復雜的重復結(jié)構(gòu)，因而基因組的 無 模 板 拼接有很大難度。 自從 2021 年以后，出現(xiàn)了多種基于下一代測序平臺基因序列的 從頭 拼接算法軟件包，包括 Velvet， ABySS， AllPath， SOAPdenovo 等。 2. 課題研究的主要內(nèi)容 基因序列是包含在生物中每個染色體中的 DNA 堿基序列的集合。通常序列拼接的輸出是一個稱為 重疊群（ contig）的集合，進而 由 contigs 經(jīng)過排序、調(diào)整、填補間隙等一系列的操作而生成的 scaffold 序列。算法首先識別出每對 contigs 之間的共同片段。對于每一個簇，建立一個包含不同 contigs 之間關(guān)系的圖結(jié)構(gòu)，最后求解圖的最長路徑。 一部分算法的結(jié)果也 scaffolds。 (2) 為 contigs 建立索引結(jié)構(gòu)。 (3) 利用索引進行映射。 我們規(guī)定readpair 中的 left read 和 right read 中的部分堿基同時和 contig 中的某段堿基一致（部分一致，具體的見映射規(guī)則），則稱為映射成功。映射規(guī)則如下： ○ 1 .對 contigs 中堿基進行 數(shù)值化。 ○ 3 .同時對每個 read 的逆序的堿基互補序列進行映射。 ○ 5 .我們只分別取出 left read 前 n（要求為取 3 的倍數(shù)）個堿基和 right read后 n 個堿基，組成的有間隙的序列進行映射。根據(jù)第 4 步中的映射結(jié)果，即每個 contig 會映射上多個 read，多個 read 組成了集合 (i，基本算法的標識； j，算法結(jié)果中 contig 編號 )。 (5) 求最長公共子序列篩選潛在可拼接的 contig 對。 (6) 將潛在可拼接的 contigs 對進行聚簇，簇數(shù)記為 CCount? 。將簇中所有 ,SGij （簇 i 中的第 簇 j 個子圖 ）合并成能表示一個簇的圖 CGi （暫且稱為簇圖， ClusterGraph），最后求解簇圖的最長路徑。 (7) 最終結(jié)果的評估。 結(jié)果顯示，使用我們的算法，大幅度的增長了的 MAX {contigs}。 3. 課題研究的主要的目的和意義 利用全基因組無模板 拼接 技術(shù)，可以獲得動物、植物、細菌、真菌 、病毒 的全基因組序列，從而推進該物種的研究。全基因組序列圖譜完成后，可以構(gòu)建該物種的基因組數(shù)據(jù)庫，為該物種的后基因組學研究搭建一個高效的平臺，為后續(xù)的基因挖掘、功能驗證提供 DNA 序列信息 ，為疾病、癌癥等的研究提供真實有效的數(shù)據(jù) 。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 審查意見 指導教師： 年 月 日 學院意見 主管領(lǐng)導： 年 月 日 天津工業(yè)大學本科 畢業(yè)論文 評閱表 （論文類） 題目 基于高重復區(qū)域基因序列的無模板拼接算法 學生姓名 徐 學生班級 軟件 指導教師姓名 陳 評審項目 指標 滿分 評分 選題 能體現(xiàn)本專業(yè)培養(yǎng)目標，使學生得到較全面訓練。 10 題目與生產(chǎn)、科研等實際問題結(jié)合緊密。 15 論文撰寫 結(jié)構(gòu)嚴謹，理論、觀點、概念表達準確、清晰。 10 外文應(yīng)用 能正確引用外文文獻，翻譯準確，文字流暢。 15 有必要的數(shù)據(jù)、資料支持，數(shù)據(jù)、資料翔實可靠，得出的結(jié)論有可驗性。 10 合計 100 意見及建議： 評閱人簽名： 年 月 日 天津工業(yè)大學 畢業(yè)論文 成績考核表 學生姓名 徐 學院名稱 計算機科學與軟件 專業(yè)班級 軟件 題目 基于高重復區(qū)域基因序列的無模板拼接算法 1． 畢業(yè)論文 指導教師評語及成績： 指導教師簽字： 年 月 日 2． 畢業(yè)論文 答辯委員會評語及成績： 答辯主 席 （或組長）簽字： 年 月 日 3． 畢業(yè)論文 總成績： 給定成績 給定成績 總成績 (a +b +c ) 成績： 成績： 摘 要 隨著新一代基因組測序技術(shù)的推廣使用，全基因組 Shotgun 拼接算法和軟件得到了廣泛的研究。 而且普通高等生物的基因組堿基數(shù)目巨大，如人類基因組總長約 30 億 bp。 自從 2021 年以后 ， 出現(xiàn) 了多種基于下一代測序平臺基因序列的從頭拼接算法軟件包，包括 Telescoper、 Velvet、 ABySS、AllPath SOAPdenovo、 EULERUSR、 Cortex 等。 因此，我們很容易認識到設(shè)計出更好的算法還有很大的空間。構(gòu)建索引和讀長映射兩個步驟旨在通過讀長（ read）找到不同算法獲得的 contig 之間的相關(guān)性，然后通過這個相關(guān)性進行聚簇，簇內(nèi)的所有 contig 具有互補性，是潛在的可拼接的 序列 。 實驗結(jié)果表明 ， 算法得到最長的 scaffold 序列的長度 和 scaffold N50 等兩項指標 ，相對于 目前拼接效果最好的算法 Velvet、 ABySS、 SOAPdenovo 等增長的比例高達 50%。本文提出的方法大幅度的提高了 contig 的序列的長度，將為進一步對基因 評估和分析 降低了難度，為解決生物問題提供了更好的 線索 ， 將迅速加快生物基因組研究的步伐。 Contig。 DNA sequencing 目 錄 第一章 緒 論 ....................................................................................... 1 背景目的和意義 .............................................................................................. 1 術(shù)語 .................................................................................................................. 2 基因組測序技術(shù)簡介 ...................................................................................... 4 第一代測序技術(shù) .................................................................................... 4 第二代測序技術(shù) .................................................................................... 5 新一代測序技術(shù) .................................................................................... 7 基因組拼接技術(shù)簡介 ...................................................................................... 9 基因組拼接技術(shù)的研究現(xiàn)狀 ...............................................................