配列アライメントの高速化に関する検討

カテゴリ: 研究会(論文単位)

論文No: IIS15076

グループ名: 【D】産業応用部門 次世代産業システム研究会

発行日: 2015/09/17

タイトル(英語): Accelerating Techniques for Sequence Alignment

著者名: 尾風 仁(沖縄工業高等専門学校),山田 親稔(沖縄工業高等専門学校),宮城 桂(沖縄工業高等専門学校),池松 真也(沖縄工業高等専門学校)

著者名(英語): Jin Okaze(National Institute of Technology, Okinawa College),Chikatoshi Yamada(National Institute of Technology, Okinawa College),Kei Miyagi(National Institute of Technology, Okinawa College),Shinya Ikematsu(National Institute of Technology, Okinawa College)

キーワード: 配列アライメント|Ｎｅｅｄｌｅｍａｎ－Ｗｕｎｓｃｈ　アルゴリズム|sequence alignment|Needleman-Wunsch algorithm

要約(日本語): 生物学分野における配列アライメントの一つに，Needleman-Wunsch(NW)アルゴリズムがある。NWアルゴリズムはDNA配列を比較し，2つの配列の共通部分を整列させることを目的とするグローバル配列アラインメントの手法である。しかしながら，配列全体を整列させるため，ローカルアラインメントであるSmith-Waterman(SW)アルゴリズムに比べて計算量が膨大になる。また，多系列からなる出力データを高速に解析するために，SWアルゴリズムを3次元に拡張し，GPUを用いて高速化する研究が行われているが，それではデータ全体の類似度を求めることができない。そこで本稿では，NWアルゴリズムに対して3次元への拡張を行った。この結果に対し並列化を行うことで，精度の高い多系列データ解析の高速化が期待される。

要約(英語): The NW (Needleman-Wunsch) algorithm is a sequence alignment in bioinformatics. The NW algorithm is also a global sequence alignment which is a way of arranging the sequences of DNA to identify regions of similarity. However, the NW algorithm needs a huge amount of calculation compared with SW (Smith-Waterman) algorithm. There are many studies in order to analyze in fast for output of multiple sequences with three-dimensional but the methods cannot get similarities of whole sequences. In this article, we extend NW algorithm to three-dimensional. The proposed method is expected to be fast analysis of high precision data sequences.

原稿種別: 日本語

PDFファイルサイズ: 1,657 Kバイト