請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/76444
標題: | 使用快速取樣與連結策略之新式長序列基因映射器 A Novel Long Read Aligner Using Fast Seeding and Linking Strategies |
作者: | Nae-Chyun Chen 陳乃群 |
指導教授: | 盧奕璋(Yi-Chang Lu) |
關鍵字: | 基因序列映射,高通量定序,次世代定序,奈米孔道定序, sequence alignment,high-throughput sequencing,next-generation sequencing,nanopore sequencing, |
出版年 : | 2017 |
學位: | 碩士 |
摘要: | 自二十一世紀以來,次世代定序的突破性進展使得基因定序的金錢與時間成本皆大幅降低,開展一系列全新的生物與醫學研究。於2015年,利用特殊奈米孔道的高通量定序技術問世,此定序方法能夠快速分析更長的基因序列,有潛力解決許多序列分析的困難,例如大範圍的序列增減、重複區或是單倍型分析。然而由於這類奈米孔道定序的正確率尚不如前一代定序技術,對目前的主流基因映射演算法來說,映射奈米孔道序列相對困難。
在本論文中,我們針對低正確率的長基因序列,提出了一基於布洛─惠勒斯轉換之短序列取樣與連結之基因映射器(BWSL)。此一方法採用包含取樣階段、連結階段與排列階段的三級架構設計。從目標序列中取樣出大量的短序列以提高映射的成功率,在連結與序列排列階段,我們設計了有效率的一維投影與分區動態演算法以提高程式效率與映射正確率。 在基於模擬奈米孔道序列的實驗中,BWSL的映射靈敏度優於目前最好的序列映射器。以人類第四對染色體的模擬序列實驗為例,BWSL的映射靈敏度高達98.35%,與文獻中表現最好的GraphMap相比,結果高出0.83%。此外,BWSL比對結果的每鹼基對平均分數與變異分析結果也優於GraphMap,顯示BWSL在奈米孔道序列相關應用上的潛力。 In the previous decade, the advent of high-throughput sequencing makes it possible to acquire and analyze sequence data with low cost and high speed. Since 2015, nanopore-based single-molecule sequencing platforms can generate reads longer than thousands of base pairs at high speed. However, when compared to the accuracy of traditional sequencer, the sequencing accuracy of nanopore platforms is relatively lower, which becomes a great challenge for sequence aligners. In this thesis, we propose Burrows-Wheeler-transform-based aligner with Seeding and Linking (BWSL) to efficiently align long nanopore reads. A three-stage architecture involving seeding, linking and extending is designed for sensitive mapping and accurate alignment. A great number of short seeds is generated to ensure high mapping quality. The seeds are processed with novel algorithms to efficiently be mapped to correct positions and generate accurate alignments. The sensitivity of BWSL on synthetic MinION datasets outperforms current state-of-the-art mappers. Using human chromosome 4 dataset as an example, the sensitivity reaches as high as 98.35% in BWSL, which is 0.83% better than GraphMap. Also, BWSL has high average alignment scores and great variant calling accuracy. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/76444 |
DOI: | 10.6342/NTU201701631 |
全文授權: | 同意授權(全球公開) |
電子全文公開日期: | 2022-08-29 |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-106-R04943093-1.pdf | 6.81 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。