WEKO3
アイテム
アミノ酸配列のマルチプルアライメントにおける反復改善過程の並列化とA*アルゴリズムの適用
https://ipsj.ixsq.nii.ac.jp/records/17355
https://ipsj.ixsq.nii.ac.jp/records/17355ab3cad39-ce99-419f-b69a-91e8196646d3
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TOM4009016.pdf (2.4 MB)
|
Copyright (c) 1999 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1999-12-15 | |||||||
| タイトル | ||||||||
| タイトル | アミノ酸配列のマルチプルアライメントにおける反復改善過程の並列化とA*アルゴリズムの適用 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Multiple Protein Sequence Alignment Using Parallel Iterative Algorithm and A* Algorithm | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | オリジナル論文 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| 株式会社情報数理研究所（現 理化学研究所ゲノム科学総合研究センター） | ||||||||
| 著者所属 | ||||||||
| 技術研究組合新情報処理開発機構 | ||||||||
| 著者所属 | ||||||||
| 技術研究組合新情報処理開発機構 | ||||||||
| 著者所属 | ||||||||
| 技術研究組合新情報処理開発機構 | ||||||||
| 著者所属 | ||||||||
| 弘前大学理工学部 | ||||||||
| 著者所属 | ||||||||
| 技術研究組合新情報処理開発機構 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Information and Mathematical Science Laboratory, Inc / Presently with RIKEN Genomic Sciences Center | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Real World Computing Partnership | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Real World Computing Partnership | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Real World Computing Partnership | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Science and Engineering, Hirosaki University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Real World Computing Partnership | ||||||||
| 著者名 |
十時, 泰
秋山, 泰
鬼塚健太郎
野口, 保
斎藤, 稔
安藤, 誠
× 十時, 泰 秋山, 泰 鬼塚健太郎 野口, 保 斎藤, 稔 安藤, 誠
|
|||||||
| 著者名(英) |
Yasushi, Totoki
Yutaka, Akiyama
Kentaro, Onizuka
Tamotsu, Noguchi
Minoru, Saito
Makoto, Ando
× Yasushi, Totoki Yutaka, Akiyama Kentaro, Onizuka Tamotsu, Noguchi Minoru, Saito Makoto, Ando
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | タンパク質のアミノ酸配列のマルチプルアライメントの問題は，アミノ酸残基の保存や置換,欠失や挿入に一定の指標を与え，その総和（sum-ofLpairs）が最大となるものが最も確からしいアライメントであるというモデル化が現在主流になっている．このモデルは,総和の最大化に関する組み合わせ最適化問題を解くこととなる．大規模の問題を計算機で高精度に解くには,組み合わせの数が爆発するため，ヒューリステイクスの導入が必要となり，アライメントの精度と計算時間との間にトレードオフの関係が存在している．そのため実用的には従来から近似的な解法がとられてきた代表的な近似解法は，ツリーベース法であるが,解の精度は必ずしも十分ではなかった．我々は新しい戦略として反復改善法を拡張し，最良優先探索の効率的な近似化を図った上で,最良優先探索における近傍探索を並列実装した．さらに,Ａ*アルゴリズムを適用して探索空間の効率的な刈り込みを実現した．これらの改良の結果,大規模のマルチプルアライメントの問題を高精度に，現実的な計算時間内で得ることを可能とした． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Since the multiple sequence alignment problem requires enormous calculation time, one is faced with a trade-off between computation time and the quality of alignment. To date, although several approximation methods have been proposed, the quality of alignments produced by previous methods is limited. As a new strategy, we employed an iterative scheme with best-first search, and parallelized its search step. Furthermore we implemented the A* pruning algorithm instead of dynamic programming, to drastically reduce the search space. As a result, our new parallel system enables biologically accurate multiple sequence alignment to be performed within reasonable calculation time. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11464803 | |||||||
| 書誌情報 |
情報処理学会論文誌数理モデル化と応用（TOM） 巻 40, 号 SIG09(TOM2), p. 138-149, 発行日 1999-12-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7780 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
