A Re-sequencing Tool For Next Generation Sequencing Based On Burrows-Wheeler Transform

基於Burrows-Wheeler轉換之次世代定序技術重定序工具

盧振華(Chen-Hua Lu)

指導教授 ： 唐傳義

國立清華大學/電機資訊學院/資訊工程學系/碩士(2010年)

https://doi.org/10.6843/NTHU.2010.00454

摘要

本篇論文中，我們呈現了一個適用於次世代定序技術資料的重定序工具。這些資料是由大量的短序列所構成的，並將被對應到一個參考基因體上。我們修改並實作了Borrows-Wheeler Transform與FM-index的演算法，以此對人類的基因體建立索引；並提出了一個分割短序列的方法，使我們在對應時得以容許更長的漢明距離。最後，我們從1000 Genome Project中選出4組不同長度的真實資料，在個人電腦上進行測試，藉此展現此工具的性能，並與bowtie這個廣為使用的工具進行比較。

關鍵字

NGS ； BWT ； FM-index ； 重定序 ； 短序列讀數 ； 去氧核醣核酸

並列摘要

In this thesis, we present a re-sequencing tool designed for the Next Generation Sequencing (NGS) data. These data are composed huge amount of short reads, which are to align onto a referenced genome. We modified and implemented the algorithm of Borrows-Wheeler Transform and FM-index to build the genome index of human, and proposed an idea to segment each short read which lead us to align short reads with longer Hamming distance. Finally, we used 4 real data sets with different lengths form 1000 Genome Project to demonstrate the performance of our tool with a personal computer, and compared the results with a widely used tool, bowtie.

並列關鍵字

NGS ； BWT ； FM-index ； re-sequencing ； short read ； DNA

參考文獻

1. Flicek P. and Birney E. Sense from sequence reads: methods for alignment and assembly. Nature Methods (2009) 6:S6–12.

2. Li H., Ruan J., and Durbin R. Mapping short DNA sequencing reads and calling variants using mapping quality scores. Genome Research (2008) 18:1851-1858.

3. Li R., Li Y., Kristiansen K., and Wang J. SOAP: short oligonucleotide alignment program. Bioinformatics (2008) 24:713-714.

4. Smith AD., Xuan Z., and Zhang MQ. Using quality scores and longer reads improves accuracy of Solexa read mapping. BMC Bioinformatics (2008) 9:128.

5. Jiang H. and Wong WH. SeqMap: mapping massive amount of oligonucleotides to the genome. Bioinformatics (2008) 24:2395-2396.