Recent advance of genomic analysis technologies gives us a lot of DNA sequence data. Many researchers apply these data for post-genomic investigation. To find the optimum global alignment is investigated as one of the most important tasks of post-genomic investigation because it is the first step of there researches. Dynamic Programming (DP) matching is a major way to find the optimum alignment between sequences. However, DP matching requires O(N^2) memory space to align the sequences consisting of N bases. To reduce memory space, divide and conquer algorithm is used with DP matching, but it leads longer computation time. In this paper, we propose a high-speed method to obtain the optimum global alignment by parallel DP maching assisted with GPGPU(General Purpose computing on Graphics Processing Unit). In this method, we utilize many stream processors like an arithmetic pipeline. Experimental results showed that our method achieved about five times faster than that by CPU.
雑誌名
宮崎大學工學部紀要
巻
41
ページ
323 - 326
発行年
2012-07-30
出版者
宮崎大学工学部
Faculty of Engineering, University of Miyazaki
リポジトリのご案内
GPGPUを用いた並列DPマッチングによる大域アラインメントの高速化
engineering41_323-326.pdf
(801.57KB)
