タンパク質スレッディング問題の近似について
スポンサーリンク
概要
- 論文の詳細を見る
アミノ酸配列からのタンパク質立体構造の推定は遣伝情報解析における中心的問題の一つである。タンパク質スレッディングはそのための有効な手法の一つであり、ある種の最適化問題として定式化できる。しかしながら既にNP困難であることが証明されているので、多項式時間近似アルゴリズムについて考察する。まずMAX SNP困難であることを示し、さらにDENSE-k-SUBGRAH 問題以上に近似困難であることを示す。そしてアミノ酸相互作用の影響範囲を示すグラフが平面的である場合について、最適解の4倍以内の近似解を出力するアルゴリズムを示す。この結果はβシートと呼ばれる領域の推定に応用できる可能性がある。
- 一般社団法人情報処理学会の論文
- 1996-05-29
著者
関連論文
- 分子生物情報学の現状と動向 (「分子生物情報学の新展開」)
- 特集「分子生物情報学の新展開の編集にあたって (「分子生物情報学の新展開」)
- 点集合の距離重複度列のノルムと最大部分集合問題
- DNAマイクロアレイ画像の解析
- DNAマイクロアレイ画像の解析
- DNA2次元電気泳動画像のパターンマッチング : 問題の困難さとヒューリスティック・アルゴリズム
- DNA2次元電気泳動画像のパターンマッチング : 問題の困難さとヒューリスティック・アルゴリズム
- 線形計画法による非線形システムS-systemの推定
- TD-1-3 バイオインフォマティクスにおける知識発見
- 局所多重アライメントのための局所探索アルゴリズム : 特殊ケースにおける収束性の解析と腫瘍細胞分類への応用
- ゲノム情報解析の現状と課題
- バイオインフォマティクスへの扉
- 遺伝子制御ネットワーク解明のためのアルゴリズム (ゲノムサイエンスの新たなる挑戦) -- (第3部 ゲノム情報科学)
- 遺伝子発現制御ネットワークの論理的解析
- 配列のローカル・アラインメントの困難さについて
- 遺伝子ネットワーク解明のためのアルゴリズム
- 立体構造のマルチプルアラインメントに基づくタンパク質立体構造予測
- 東京大学医科学研究所ヒトゲノム解析センターDNA情報解析分野
- 遺伝子ネットワーク解明のためのアルゴリズム
- RNA二次構造予測のための近似アルゴリズム
- ゲノム情報解析におけるスコア関数学習の計算複雑度について
- 3.幾何的マッチングによるタンパク質立体構造の比較 (「ゲノム情報」)
- タンパク質スレッディング問題の近似について
- 行列乗算とハッシュ関数を用いたブーリアンネットワークの同定アルゴリズム
- 線形計画法による非線形システム S-system の推定
- ブーリアンネットワークの高速同定アルゴリズム
- 遺伝子発現パターンデータからの定性ネットワークの推定
- 遺伝子発現パターンからの細胞分類アルゴリズム
- 線形計画法による遺伝情報解析のためのスコア関数の学習