加速以序列比對為基礎之三代定序錯誤校正法;Acceleration of Alignment-based Error Correction for Third-generation Sequencing

National Chung Cheng University Institutional Repository > 工學院 > 資訊工程學系 > 學位論文 > Item A095B0000Q/80

Please use this identifier to cite or link to this item: http://ccur.lib.ccu.edu.tw/handle/A095B0000Q/80

Title:	加速以序列比對為基礎之三代定序錯誤校正法;Acceleration of Alignment-based Error Correction for Third-generation Sequencing
Authors:	莊為堯;CHUANG, WEI-YAO
Contributors:	資訊工程研究所
Keywords:	第三代定序技術;序列比對校正法;位元平行化;動態規劃;3rd generation sequencing;alignment-based correction;bit parallelism;dynamic programming
Date:	2018
Issue Date:	2019-05-23 10:30:24 (UTC+8)
Publisher:	資訊工程研究所
Abstract:	第三代定序技術所定序出來的序列較長，而且定序速度較快，但是序列的錯誤率也比較高。因此在基因體組裝之前，通常會將序列上之定序錯誤進行校。其中一種錯誤校正策略是以序列比對為基礎之方法，此方法基於較耗時之動態規劃(Dynamic Programming)技巧來做序列比對。本篇論文中使用一位元平行化(Bit Parallelism)演算法來加速動態規劃，並與傳統之頻帶動態規劃(Banded DP)加速進行比較．此外，我們亦調整該位元平行演算法以適應三代定序特有之錯誤型態。實驗結果指出，採用位元平行化之動態規劃，確實比傳統頻帶動態規劃速度更快，但是校正準確率卻些微下降。進一步觀察顯示位元平行化動態規劃，在連續重複區間(Tandem Repeats)經常校正失敗，需要為此區域設計特殊方法才能改善。 The 3rd generation sequencing can produce long reads with fast turnaround time yet also with high error rate. Consequently, errors on the sequencing reads are usually corrected before genome assembly. One of the strategies of error correction is alignment-based method, which requires time-consuming alignment among reads based on dynamic programming (DP). In this thesis, we implement a bit-parallelism algorithm to accelerate DP and compare with traditional banded DP speedup. In addition, the bit-parallelism algorithm is fine tuned for correcting errors specific in third-generation sequencing. The results showed that, though bit-parallelism DP is faster than banded DP, the accuracy is unexpectedly decreased. Further investigation indicated that bit-parallelism DP performs worse in tandem repeat regions, which requires specific algorithms for better accuracy.
Appears in Collections:	[資訊工程學系] 學位論文

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	337	View/Open

Loading...