【正文】 天津工業(yè)大學 畢業(yè)論文 基于高重復區(qū)域基因序列的無模板拼接算法 姓 名 徐 學 院 計算機科學與軟件 專 業(yè) 軟件工程 指導教師 陳 職 稱 副教授 2021 年 5 月 27 日 天津工業(yè)大學畢業(yè) 論文任務書 題目 基于高重復區(qū)域基因序列的無模板拼接算法 學生姓名 徐 學院名稱 計算機科學與軟件 專業(yè)班級 軟件 課題類型 實際課題 課 題意義 利用全基因組無模板 拼接 技術(shù)，可以獲得動物、植物、細菌、真菌的全基因組序列，從而推進該物種的研究。一個物種基因組序列圖譜的完成，意味著這個物種學科和產(chǎn)業(yè)的新開端，這也將帶動這個物種下游一系列研究的開展。全基因組序列圖譜完成后，可以構(gòu)建該物種的基因組數(shù)據(jù)庫，為該物種的后基因組學研究搭建一個高效的平臺，為后續(xù)的基因挖掘、功能驗證提供 DNA 序列信息，為疾病、癌癥等的研究提供真實有效的數(shù)據(jù)。 任務與進度要求 選題確認并完成開題報告、任務書的填寫、提交、 審核 深入了解課題內(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。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 日 備注 院長 教研室主任 指導教師 畢業(yè)論文 開題報告 表 2021 年 3 月 8 日 姓名 徐 學院 計算機科學與軟件 專業(yè) 軟件工程 班級 軟件 題目 基于高重復區(qū)域基因序列的無模板拼接算法 指導教師 陳 一、與本課題有關(guān)的國內(nèi)外研究情況、課題研究的主要內(nèi)容、目的和意義： 1. 與本課題有關(guān)的國內(nèi)外研究情況 隨著新一代基因組測序技術(shù)的推廣使用 ，全基因組 Shotgun 拼接算法和軟件 得 到了廣泛的研究。 新一代的 基因測序 技術(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)，因而基因組的 無 模 板 拼接有很大難度。這樣，絕大多數(shù)生物的基因組都不能通過實驗手段一 次性獲得，必須借助計算機技術(shù)進行后續(xù)拼接。 自從 2021 年以后，出現(xiàn)了多種基于下一代測序平臺基因序列的 從頭 拼接算法軟件包，包括 Velvet， ABySS， AllPath， SOAPdenovo 等。 盡管人們普遍認識到，不同拼接算法所產(chǎn)生的結(jié)果具有互補的，但是現(xiàn)在還沒有一個方法能融合多個拼接算法的結(jié)果。 2. 課題研究的主要內(nèi)容 基因序列是包含在生物中每個染色體中的 DNA 堿基序列的集合?；蛐蛄衅唇邮且粋€研究如何將包含較短的讀長基因數(shù)據(jù)庫中的所有序列通過合并和排序之后拼接成長 序列的問題。通常序列拼接的輸出是一個稱為 重疊群（ contig）的集合，進而 由 contigs 經(jīng)過排序、調(diào)整、填補間隙等一系列的操作而生成的 scaffold 序列。 本文提出了一個基于圖論的算法，對多個不同算法拼接出的 contigs 進行拼接， 得到更長的 scaffold序列。算法首先識別出每對 contigs 之間的共同片段。然后將達到一定長度的共同片段聚到一個簇中。對于每一個簇，建立一個包含不同 contigs 之間關(guān)系的圖結(jié)構(gòu)，最后求解圖的最長路徑。 算法具體步驟如下： (1) 獲 得其他 算法 產(chǎn)生 contigs。 一部分算法的結(jié)果也 scaffolds。 盡量使用較長 的 scaffolds。 (2) 為 contigs 建立索引結(jié)構(gòu)。將每個算法生成的 contigs 集合建立一個索引結(jié)構(gòu)，生成索引文件。 (3) 利用索引進行映射。根據(jù)索引將原始數(shù)據(jù)庫中的全部的基因序列映射到 contigs 上。 我們規(guī)定readpair 中的 left read 和 right read 中的部分堿基同時和 contig 中的某段堿基一致（部分一致，具體的見映射規(guī)則），則稱為映射成功。映射結(jié)果一般表現(xiàn)為：一個 contig 的不同的位置上有多個 read 對應。映射規(guī)則如下： ○ 1 .對 contigs 中堿基進行 數(shù)值化。 ○ 2 .我們只對非 ATGC 堿基個數(shù)不超過堿基序列（ read）的 5%的 read，進行映射。 ○ 3 .同時對每個 read 的逆序的堿基互補序列進行映射。 ○ 4 .我們允許最少 2 個堿基，最多 2%個堿基的錯誤。 ○ 5 .我們只分別取出 left read 前 n（要求為取 3 的倍數(shù)）個堿基和 right read后 n 個堿基，組成的有間隙的序列進行映射。 (4) 尋找潛在可拼接的 contig 對。根據(jù)第 4 步中的映射結(jié)果，即每個 contig 會映射上多個 read，多個 read 組成了集合 (i，基本算法的標識； j，算法結(jié)果中 contig 編號 )。尋找潛在可拼接的 contig 對是任何兩個不同拼接算法中的 contig 映射到的集合 彼此之間交集的元素個數(shù)超過一個給定閾值。 (5) 求最長公共子序列篩選潛在可拼接的 contig 對。計算第 4 步中找到的潛在可拼接的兩個 contigs的最長公共子序列，移除最長公共子序列的長度小于某一閾值的 contig 對。 (6) 將潛在可拼接的 contigs 對進行聚簇，簇數(shù)記為 CCount? 。 ① 構(gòu) 建子圖，并拼接。將簇中所有 ,SGij （簇 i 中的第 簇 j 個子圖 ）合并成能表示一個簇的圖 CGi （暫且稱為簇圖， ClusterGraph），最后求解簇圖的最長路徑。最長路徑所包含的堿基序列即為我們算法拼接之后的結(jié)果。 (7) 最終結(jié)果的評估。比較 各項指標 N50、 MAX。 結(jié)果顯示，使用我們的算法，大幅度的增長了的 MAX {contigs}。我們也證實了，引進將更多的拼接算法的結(jié)果，我們的算法結(jié)果將提高的更多。 3. 課題研究的主要的目的和意義 利用全基因組無模板 拼接 技術(shù)，可以獲得動物、植物、細菌、真菌 、病毒 的全基因組序列，從而推進該物種的研究。一個物種基因組序列圖譜的完成，意味著這個物種學科和產(chǎn)業(yè)的新開端，這也將帶動這個物種下游一系列研究的開展。全基因組序列圖譜完成后，可以構(gòu)建該物種的基因組數(shù)據(jù)庫，為該物種的后基因組學研究搭建一個高效的平臺，為后續(xù)的基因挖掘、功能驗證提供 DNA 序列信息 ，為疾病、癌癥等的研究提供真實有效的數(shù)據(jù) 。 二、進度及預期 結(jié)果： 起止日期 主要內(nèi)容 預期結(jié)果 選題確認并完成開題報告、任務書的填寫、提交、審核 深入了解課題內(nèi)容、算法分析、確定算法系統(tǒng)框架、熟悉開發(fā)工具 完成算法的邏輯實現(xiàn)，和工具包的開發(fā)，完成算法系統(tǒng)的大部分功能，初稿完成 進行實驗結(jié)果整理，并 進一步提高各項指標，二稿完成 畢業(yè)論文 的審核、修改 及定稿并裝訂 答辯 完成 完成 完成 完成 完成 完成 完成課題的現(xiàn)有條件 硬件： 曙光小型機 (Sugon Server Main Server Chassis) 軟件： Vim、 Emacs、 Gcc/G++、 Eclipse、 Python、 Visual Studio2021 參考文獻： [1] Bresler, M., Sheehan, S., Chan, ., and Song, . Telescoper: De novo Assembly of Highly Repetitive Regions. ECCB39。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)目標，使學生得到較全面訓練。題目大小、難度適中，學生工作量飽滿，經(jīng)努力能完成。 10 題目與生產(chǎn)、科研等實際問題結(jié)合緊密。 10 課題調(diào)研、 文獻檢索 能獨立查閱文獻以及從事其他形式的調(diào)研，能較好地理解課題任務并提出實施方案；有分析整理各類信息，從中獲取新知識的能力。 15 論文撰寫 結(jié)構(gòu)嚴謹，理論、觀點、概念表達準確、清晰。 10 文字通順，用語正確，基本無錯別字和病句，圖表清楚，書寫格式符合規(guī)范。 10 外文應用 能正確引用外文文獻，翻譯準確，文字流暢。 5 論文水平 論文論點正確，論點與論據(jù)協(xié)調(diào)一致，論據(jù)充分支持論點，論證過程有說服力。 15 有必要的數(shù)據(jù)、資料支持，數(shù)據(jù)、資料翔實可靠，得出的結(jié)論有可驗性。 15 論文有獨到見解或有一定實用價值。 10 合計 100 意見