請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/78029
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 盧奕璋(Yi-Chang Lu) | |
dc.contributor.author | Hao-Wei Liu | en |
dc.contributor.author | 柳皓瑋 | zh_TW |
dc.date.accessioned | 2021-07-11T14:40:07Z | - |
dc.date.available | 2022-02-21 | |
dc.date.copyright | 2017-02-21 | |
dc.date.issued | 2017 | |
dc.date.submitted | 2017-01-19 | |
dc.identifier.citation | [1] The SAM/BAM Format Specification Working Group, Sequence Alignment/Map Format Specification, Sep 2016. [Online]. Available: http://samtools.github.io/hts-specs/SAMv1.pdf
[2] Samtools Organisation, The Variant Call Format (VCF) Version 4.2 Specification, Nov 2015. [Online]. Available: http://samtools.github.io/hts-specs/VCFv4.2.pdf [3] D. C. Koboldt, Q. Zhang, D. E. Larson, D. Shen, M. D. McLellan, L. Lin, C. A. Miller, E. R. Mardis, L. Ding, and R. K. Wilson, “VarScan 2: Somatic mutation and copy number alteration discovery in cancer by exome sequencing,” Genome Research, vol. 22, no. 3, pp. 568–576, 2012. [4] J. Shendure and H. Ji, “Next-generation DNA Sequencing,” Nat Biotechnol, vol. 26, no. 10, pp. 1135–1145, 2008. [5] H. Li, B. Handsaker, A. Wysoker, T. Fennell, J. Ruan, N. Homer, G. Marth, G. Abecasis, R. Durbin, and . G. P. D. P. Subgroup, “The sequence alignment/map format and SAMtools,” Bioinformatics, vol. 25, no. 16, pp. 2078–2079, Aug 2009. [6] P. Danecek, A. Auton, G. Abecasis, C. A. Albers, E. Banks, M. A. DePristo, R. E. Handsaker, G. Lunter, G. T. Marth, S. T. Sherry, G. McVean, and R. Durbin, “The variant call format and VCF tools.” Bioinformatics (Oxford, England), vol. 27, no. 15, pp. 2156–8, 2011. [7] H. Li, “A statistical framework for SNP calling, mutation discovery, association mapping and population genetical parameter estimation from sequencing data,” Bioinformatics, vol. 27, no. 21, pp. 2987–2993, 2011. [8] D.C.Koboldt,K.Chen,T.Wylie,D.E.Larson,M.D.McLellan,E.R.Mardis,G.M. Weinstock, R.K.Wilson, andL.Ding, “VarScan: Variant detection in massively parallel sequencing of individual and pooled samples,” Bioinformatics, vol. 25, no. 17, pp. 2283–2285, 2009. [9] Samtools Organisation, CRAM format specification (version 3.0), Sep 2016. [Online]. Available: https://samtools.github.io/hts-specs/CRAMv3.pdf [10] N. Popitsch and A. Von Haeseler, “NGC: Lossless and lossy compression of aligned high-throughput sequencing data,” Nucleic Acids Research, vol. 41, no. 1, 2013. [11] P. Elias, “Universal codeword sets and representations of the integers,” IEEE Transactions on Information Theory, vol. 21, no. 2, pp. 194–203, 1975. [12] Boost.org, Boost C++ Library. [Online]. Available: http://www.boost.org [13] J. H. McDonald, “Fisher’s exact test of independence,” in Handbook of Biological Statistics, 3rd ed. Sparky House Publishing, 2014, pp. 77–85. [14] F. Yates, “Contingency tables involving small numbers and the χ2 test,” Supplement to the Journal of the Royal Statistical Society, vol. 1, no. 2, p. 217, 1934. [15] K. Pearson, “On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling,”PhilosophicalMagazineSeries5,vol.50, no. 302, pp. 157–175, Jul 1900. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/78029 | - |
dc.description.abstract | 本論文提出一種基於鹼基位置排列的次世代定序資料檔案格式—vBAM與其參考軟體系統及變異分析硬體加速器。
vBAM檔案格式包含兩項子檔案,分別是vRead與rInfo,vRead儲存個別鹼基對應的資訊,rInfo則記錄整條短序列所共用的資訊。 vBAM檔案格式藉由移除不被變異檢測所使用的冗餘資訊,並將各位置上鹼基資訊以游程編碼壓縮,使得vBAM檔案得以較快速度進行變異檢測,同時其檔案大小也可縮減為BAM檔案的約百分之二十。 vBAM檔案的參考軟體系統由C++寫成,支援BAM到vBAM的編碼流程、vBAM解碼流程以及使用vBAM的變異檢測流程,在編碼時間上略慢於SAMtools由BAM轉為pileup的時間,而解碼與變異檢測速度則約為VarScan的4倍。 而硬體加速器則用於加速解碼與變異檢測作業,其晶片使用TSMC 40奈米製程,面積為2.25 mm^2,並運作於250 MHz的時鐘頻率,使用了較低精度的變異可信度資訊,但支援大部分的變異檢測功能。 與軟體相比較,使用加速器的vBAM解碼與變異檢測作業可再獲得約8倍加速。 | zh_TW |
dc.description.abstract | In this thesis, we propose a new nucletide-position-based file format, vBAM for next-generation sequencing data, and implement a reference software system including encoding, decoding and variant calling, as well as its hardware accelerator for decoding and variant calling.
The vBAM format contains two sub-files, vRead and rInfo, where vRead file stores location-typed data like bases and base qualities, rInfo file stores whole-read data such as read lengths and mapping qualities. The vBAM format removes all the redundant data which are not required by variant calling, and uses run-length coding to compress nucletide bases and base qualities. As the results, we make vBAM file have better efficiency for variant calling and need only 20% file size when compared to BAM format. The vBAM reference software, vBAM System, written in C++ supports BAM to vBAM file conversion, vBAM decoding and variant calling. The speed of vBAM encoding is only slightly slower than converting BAM to pileup using SAMtools, but the decoding and variant calling speed is about 4X faster than VarScan. The hardware accelerator is implemented using TSMC 40nm technology, with 2.25 mm^2 chip area, running at 250 MHz clock frequency. It supports most variant calling functions, with minor sacrifice in significance precision. Compare to software version, this accelerator can process 8X faster on vBAM decoding and variant calling. | en |
dc.description.provenance | Made available in DSpace on 2021-07-11T14:40:07Z (GMT). No. of bitstreams: 1 ntu-106-R03943103-1.pdf: 8795929 bytes, checksum: 1006e6e0bf5176a44f8ae0f5d3f5f23b (MD5) Previous issue date: 2017 | en |
dc.description.tableofcontents | 口試委員會審定書 i
誌謝 ii 摘要 iii Abstract iv 1 緒論 1 1.1 分析工具 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 SAMtools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 VarScan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 壓縮編碼演算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.1 游程編碼 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.2 一元編碼 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.3 以利亞伽瑪編碼 . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.4 以利亞戴爾達編碼 . . . . . . . . . . . . . . . . . . . . . . . . 7 2 檔案格式 9 2.1 整體檔案結構 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 vRead 檔案格式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.1 區塊標頭資訊 . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.2 對應位置大小、對應位置與序列深度 . . . . . . . . . . . . . . 13 2.2.3 鹼基種類與鹼基品質 . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.4 插入與刪除突變 . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.5 位元流與檔案串流 . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 rInfo 檔案格式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3 編碼器、解碼器與分析工具軟體設計 23 3.1 編碼器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.1.1 BAM 解析器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.1.2 轉置核心 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1.3 游程編碼、符號轉換與二元編碼器 . . . . . . . . . . . . . . . 29 3.1.4 rInfo 檔案編碼 . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.2 解碼器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.2.1 二元解碼器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2.2 短序列對應品質重建與游程解碼器 . . . . . . . . . . . . . . . 36 3.3 分析器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.1 鹼基統計 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.3.2 參考鹼基與變異鹼基 . . . . . . . . . . . . . . . . . . . . . . . 38 3.3.3 過濾結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.3.4 額外資訊 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.3.5 基因型資料 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.4 實驗結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4 解碼與分析硬體加速器設計 45 4.1 系統架構 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.2 解碼器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.2.1 控制單元 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.2.2 位元流緩衝 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.2.3 解碼單元 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.2.4 輸出處理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3 計數器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.3.1 有限狀態機 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.3.2 鹼基資料組合 . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.3.3 鹼基類別統計字典 . . . . . . . . . . . . . . . . . . . . . . . . 57 4.3.4 計數器輸出資料 . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.4 分析器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.4.1 卡方檢定計算單元 . . . . . . . . . . . . . . . . . . . . . . . . 59 4.4.2 分析器資料輸出 . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.5 硬體設計結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5 結論與展望 67 5.1 結論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.2 未來展望 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 參考文獻 69 | |
dc.language.iso | zh-TW | |
dc.title | 使用核苷酸位置壓縮演算法之基因變異檢定方法設計及其硬體分析器實現 | zh_TW |
dc.title | Design of a Variant Calling Method and its Hardware Analyzer with Nucleotide-Position-Based Data Compression Algorithm | en |
dc.type | Thesis | |
dc.date.schoolyear | 105-1 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 陳倩瑜(Chien-Yu Chen),陳和麟(Ho-Lin Chen),劉宗德(Tsung-Te Liu) | |
dc.subject.keyword | DNA序列,次世代定序,基因變異檢測,資料壓縮,硬體加速, | zh_TW |
dc.subject.keyword | DNA sequence,next-generation sequencing,variant calling,data compression,hardware acceleration, | en |
dc.relation.page | 70 | |
dc.identifier.doi | 10.6342/NTU201700135 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2017-01-20 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-106-R03943103-1.pdf 目前未授權公開取用 | 8.59 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。