WEKO3
アイテム
CMO問題に対する改良版EOを用いた発見的解法
https://ipsj.ixsq.nii.ac.jp/records/96970
https://ipsj.ixsq.nii.ac.jp/records/969701ecb0b75-0a7c-41d7-8076-5c5b3eb2de35
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TOM0603009.pdf (699.2 kB)
|
Copyright (c) 2013 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-12-27 | |||||||
| タイトル | ||||||||
| タイトル | CMO問題に対する改良版EOを用いた発見的解法 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Heuristic Using Modified EO for CMO Problem | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | [オリジナル論文] CMO問題，Extremal Optimization，発見的解法 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| 広島市立大学大学院情報科学研究科 | ||||||||
| 著者所属 | ||||||||
| 広島市立大学大学院情報科学研究科 | ||||||||
| 著者所属 | ||||||||
| 広島市立大学大学院情報科学研究科 | ||||||||
| 著者所属 | ||||||||
| 広島市立大学大学院情報科学研究科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Sciences, Hiroshima City University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Sciences, Hiroshima City University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Sciences, Hiroshima City University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Sciences, Hiroshima City University | ||||||||
| 著者名 |
中田, 章宏
× 中田, 章宏
|
|||||||
| 著者名(英) |
Akihiro, Nakada
× Akihiro, Nakada
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 蛋白質の類似構造を抽出する手法として蛋白質立体構造アラインメントがある．蛋白質立体構造アラインメントは構造的な類似性を使い，比較する蛋白質どうしの残基間の対応関係を求める．蛋白質立体構造アラインメントを組合せ最適化問題として定式化したのがCMO（Contact Map Overlap）問題である．CMO問題はコンタクトマップと呼ばれるグラフについて，頂点間のアラインメントにより保存される共通コンタクトと呼ばれる構造の数を最大化する問題である．CMO問題は，NP困難な問題の1つであることが知られており，進化計算を用いた手法などの研究が行われている．本論文では，CMO問題に対する改良版EOを用いた発見的解法を提案する．提案手法の特徴は，（1）世代交代に改良版EOを用いること，（2）動的計画法を用いて初期個体を作成すること，（3）改良版EOにおける状態遷移に即時移動戦略ではなく，最良移動戦略を用いることである．提案手法を実際に実装し，評価実験を行った結果，EOによる発見的解法よりも評価の高い最良解が得られた． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Proteins are important biochemical compounds that have biogenic functions for biological activities. The three-dimensional structures of proteins are closely related to its biological functions, and therefore, techniques for comparing them have been studied. Many of these techniques for comparing protein structures are based on protein structure alignment, which is one of the most effective methods. CMO (Contact Map Overlap) is formulated as combinatorial optimization to find the optimal structure alignments. In this paper, we propose a novel heuristic using Modified Extremal Optimization (MEO) for CMO. Our MEO-based heuristic is characterized by three features. First, the proposed heuristic uses MEO for alternation generations. Second, an initial solution is created by dynamic programming (DP). Third, state transition is executed using the best admissible move strategy. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11464803 | |||||||
| 書誌情報 |
情報処理学会論文誌数理モデル化と応用（TOM） 巻 6, 号 3, p. 87-99, 発行日 2013-12-27 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7780 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
