全新基因序列組裝之平行處理單元與連結網路架構設計

Abstract

本篇論文研究用於全新基因序列組裝(DNA de novo sequence assembly )的平行化電路架構設計，其內容包含了演算法改良、軟體模擬以及電路設計結果。 存在於生物體內的基因序列，為了解生命運作及物種特性的重要資訊，因此各國競相進行為數眾多的基因定序計畫。由於生物基因的資料量龐大，如何提升運算速度以及降低成本，一直以來是個很重要的議題。隨著新一代基因定序技術的出現，許多短序列重組演算法相繼被提出，在這方面有著突破性的發展，不過目前在實際應用上仍不如預期。而限制效能的原因，主要在於資料存取頻寬上的限制，而使得其運算速度遲遲無法提升。本篇論文，便是針對這種情況，而進行關於這方面的研究和改善。 有鑑於此，我們提出一個可平行處理基因序列重組的演算法，並實現可執行該演算法的平行處理單元，搭配連結網路的電路架構，讓平行處理單元彼此之間可進行大量資料傳輸。相較於傳統的軟體演算法而言，此電路架構可發揮其頻寬及平行運算上的優勢，來加速處理基因序列重組的整體速度。透過軟體方式的前期模擬，我們確保了該演算法在求解序列重組問題的輸出解品質。另外，我們使用TSMC 90 nm製程，實現上述提及的平行處理單元電路，透過模擬硬體設計，得知該電路可以操作在100 MHz，在輸入同樣的重組問題下，我們可以得到最後的整體運算速度，提升約為目前軟體演算法的10倍。

This thesis researches into the topic of DNA de novo sequence assembly for a novel parallel hardware architecture design including the improvement of the algorithm, preliminary software simulation and the final result of circuit design. The genome sequences contained in beings are crucial for the knowledge of species. Because the sizes of genome data are such huge, it still consumes a lot of time with the emergence of Next Generation Sequencing. Currently, one of the bottlenecks is the limited bandwidth for data transfer, which greatly slows sequencing speeds. Hence we made an effort in improving this situation. In this thesis, we purpose a parallel DNA de novo sequence assembly algorithm. Based on the algorithm, processing elements (PEs) are designed and connected to the proposed interconnection network so that huge genome data could be transferred efficiently between PEs. Compared to previous approaches, it has advantages in both bandwidth and parallelism. Therefore, the sequencing process is much faster than those conventional approaches. As verified by software simulations, we can guarantee the quality of the solutions. Also, we have implemented the PE with TSMC 90 nm process. According to the simulation results, the hardware can be operated at frequency of 100 MHz and speed up about 10 times when compared to previous software approaches.