CMO問題に対する改良版EOを用いた発見的解法

• 中田, 章宏

• 田村, 慶一

• 北上, 始

• 高橋, 誉文

書誌事項

タイトル別名

• Heuristic Using Modified EO for CMO Problem

抄録

蛋白質の類似構造を抽出する手法として蛋白質立体構造アラインメントがある．蛋白質立体構造アラインメントは構造的な類似性を使い，比較する蛋白質どうしの残基間の対応関係を求める．蛋白質立体構造アラインメントを組合せ最適化問題として定式化したのがCMO（Contact Map Overlap）問題である．CMO問題はコンタクトマップと呼ばれるグラフについて，頂点間のアラインメントにより保存される共通コンタクトと呼ばれる構造の数を最大化する問題である．CMO問題は，NP困難な問題の1つであることが知られており，進化計算を用いた手法などの研究が行われている．本論文では，CMO問題に対する改良版EOを用いた発見的解法を提案する．提案手法の特徴は，（1）世代交代に改良版EOを用いること，（2）動的計画法を用いて初期個体を作成すること，（3）改良版EOにおける状態遷移に即時移動戦略ではなく，最良移動戦略を用いることである．提案手法を実際に実装し，評価実験を行った結果，EOによる発見的解法よりも評価の高い最良解が得られた．

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.

収録刊行物

• 情報処理学会論文誌数理モデル化と応用（TOM）

  情報処理学会論文誌数理モデル化と応用（TOM） 6 (3), 87-99, 2013-12-27

キーワード

• [オリジナル論文] CMO問題，Extremal Optimization，発見的解法

詳細情報

• CRID: 1050282812881076992
• NII論文ID: 110009550161
• NII論文ID: 110009656647
• NII書誌ID: AA11464803
• ISSN: 18827780
• Web Site: http://id.nii.ac.jp/1001/00096948/
• 本文言語コード: ja
• 資料種別: article
• データソース種別:
  • IRDB
  • CiNii Articles
  • KAKEN