2026-03-12T05:11:27Z https://miyazaki-u.repo.nii.ac.jp/oai

oai:miyazaki-u.repo.nii.ac.jp:00002561 2025-01-09T05:36:18Z 73 73:36 73:36:330 73:36:330:320

ヘイレツ DP マッチング ニヨル タイイキ アラインメント ノ コウソクカ 並列DPマッチングによる大域アラインメントの高速化 High-speed Global Alignment by Parallel DP Matching 山森, 一人 11805 ヤマモリ, クニヒト 50293395 Yamamori, Kunihito 東, 博志 13163 ヒガシ, ヒロシ 吉原, 郁夫 11807 ヨシハラ, イクオ Yoshihara, Ikuo Higashi, Hiroshi 13166 Dynamic Programming, DP matching, global alignment, DNA sequence, parallel, branch-cut Recent advance of genomic analysis technologies gives us a lot of DNA sequence data. These are used for further genome analysis. To find the optimum global alignment is investigated as one of the genomic analysis. For this purpose, Dynamic Programming (DP) matching is usually used. However, DP matching requires storage space in the square of the length of the sequences. For example, to find the optimum global alignment for one million bases, 1TB memory is needed. So, divide and conquer method is proposed to reduce required memory space. However, it leads increasing of the amount of calculation of DP matching. So we propose a method to achieve fast computation time with small required memory by combination of branch-cut and parallel processing. Our method succeeded to reduce computation time to 8% of conventional method. departmental bulletin paper 宮崎大学工学部 Faculty of Engineering, University of Miyazaki 2010-09-30 VoR application/pdf 宮崎大学工学部紀要 39 345 350 Memoirs of Faculty of Engineering, University of Miyazaki AA00732558 05404924 https://miyazaki-u.repo.nii.ac.jp/record/2561/files/engineering39-53.pdf http://hdl.handle.net/10458/3236 https://miyazaki-u.repo.nii.ac.jp/records/2561 jpn