正員の例からの最良コンセンサスモチーフの抽出
スポンサーリンク
概要
- 論文の詳細を見る
アミノ酸配列からコンセンサスモチーフを見つけ出すことは,分子生物学における重要な課題である.本稿ではまず,この問題をbest consensus motif(BCM)問題として定式化する.アルファベットΣ上の型(type)とは,Σの部分集合からなる族Ωのこととする.型Ωのモチーフπをモチーフ成分の文字列π=π_1…π_nと定義する.ここで各π_iはΩの要素を表す.Ω上のBCM問題とは,互いに異なる文字列の組からなるyes-no sample S={α^<(1)>,β^<(1)>},...,(α^<(m)>,β^<(m)>)}が与えられた時,s中のgood pairsの数が最大になるような型Ωのモチーフπを見つける問題である.ここで組(α^<(i)>,β^<(i)>)がπに対してgoodであるとは,πがα^<(i)>を説明し,β^>(i)>を説明しないときをいう.次に,PROSITEデータベースでタンパク質モチーフを記述するのに使われている型Ω1={z|φ≠z⊆Σ}に対して,BCM問題がNP完全であることを示す.また,より一般的な型Ω_∞=Ω_1∪{Σ+}∪{Σ^<(i, j)>|1≤i≤j}に対してもこの問題がNP完全であることを示す.さらに,Ω1上のBCM問題に対して,確立的手法を用いた多項式時間greedyアルゴリズムとその近似率を与える.
- 社団法人電子情報通信学会の論文
- 1995-10-27
著者
関連論文
- 正員の例からの最良コンセンサスモチーフの抽出
- アミノ酸配列データからの機械発見システムBONSAI Garden
- 歩行からの次数限定木推論問題
- 最小共通包含木問題に対する並列近似アルゴリズム
- 推論の並列化(計算量理論とその周辺)
- 辞書式順序で最初の極大部分グラフを計算する問題のP完全性とNCアルゴリズム(計算アルゴリズムと計算量の基礎理論)
- 並列知識獲得システムBONSAI Garden
- 形式グラフ体系上の反駁木問題の並列化とグラフ同型問題(計算機構とアルゴリズム)
- BONSAI : 決定木とインデックス化による文字列からの機械発見システム
- Recovery of Incomplete Tables under Data Dependencies (形式言語理論とオ-トマトン理論)
- 並列アルゴリズムの理論
- 並列アルゴリズムの複雑さ
- 並列化とその限界 : 理論的側面から
- 分岐数限定超グラフに対する極大独立集合を求めるNCアルゴリズム
- ゲノム情報における機械学習の計算量 : 理論と実際 (「人工知能技術における計算量」)
- 学習アルゴリズムによるアミノ酸のインデックス化とタンパク質データからの知識獲得実験
- 機械学習理論を適用したアミノ酸配列からの知識獲得
- PAC 学習 : 確率的で近似的に正しい学習 (計算的学習理論とその応用)