2024-03-29T04:10:31Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000715482023-04-27T10:00:04Z01164:05352:06035:06233
FM-indexを用いた高速な配列相同性検索ツールの開発Development of a fast homology search tool based on FM-indexjpnhttp://id.nii.ac.jp/1001/00071548/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=71548&item_no=1&attribute_id=1&file_no=1Copyright (c) 2010 by the Information Processing Society of Japan東京工業大学大学院情報理工学研究科計算工学専攻東京工業大学大学院情報理工学研究科計算工学専攻東京工業大学大学院情報理工学研究科計算工学専攻鈴木, 脩司石田, 貴士秋山, 泰近年,DNA 配列等の配列決定技術の向上により高速に配列データを得ることが可能となった.これにより DNA 配列及びタンパク質配列のデータベースのデータ量が爆発的に増加している.このため大量の配列データに対して巨大な DB への相同性検索を行う機会が多くなってきてる.しかし,大規模なデータを用いた相同性検索では,BLAST など従来のツールでは解析が間に合わないという問題がある.本研究では Suffix Array を用いてクエリのインデックスを,FM-index を用いて DB のインデックスを構築し,これらのインデックスを用いてミスマッチをある程度許して短い領域で高いスコアとなる部分を見つけ,その部分の周辺をアラインメントするアルゴリズムを提案した.その結果,従来用いられてきた BLAST 以上の精度を保ったまま,約 10 倍の高速化を達成した.In recent years, a lot of biological sequence data can be determined easily and the size of DNA/protein sequence databases is increasing explosively because of the improvement of sequencing technologies. However, such a huge sequence data causes a problem that even general homology search analyses by using BLAST become difficult in terms of the computation cost. Therefore, we designed a new homology search algorithm that finds alignment candidates based on the suffix array of queries and the FM-index of a database. As results, the proposed method achieved about 10-fold speed up than BLAST.AA12055912研究報告バイオ情報学(BIO)2010-BIO-2320162010-12-092010-12-07