正負の例からの最良コンセンサスモチーフの抽出 Extracting Best Consensus Motifs from Positive and Negative Examples

Search this Article

Author(s)

    • 丸山 修 MARUYAMA Osamu
    • 九州大学総合理工学研究科情報システム学専攻 Department of Information Systems, Kyushu University 39
    • 宮野 悟 MIYANO Satoru
    • 九州大学理学部基礎情報学研究施設 Research Institute of Fundamental Information Science, Kyushu University 33

Abstract

アミノ酸配列からコンセンサスモチーフを見つけ出すことは,分子生物学における重要な課題である.本稿ではまず,この問題を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アルゴリズムとその近似率を与える.

We define the best consensus motif (BCM) problem motivated by the problem of extracting motifs from nucleic acid and amino acid sequences. A type over an alphabetΣ is a familyΩ of subsets of Σ. A motif π of type Ω is a stringπ=π_1…π_n of motif components, each of which stands for an element in Ω. The BCM problem for Ω is, given a yes-no sample S={(α^<(1)>, β^<(1)>),...,(α^<(m)>, β^<(m)>)} of pairs of strings inΣ with α^<(i)>≠β^<(i)> for 1≤i≤m, to find a motif π of type Ω that maximizes the number of good pairs in S, where (α^<(i)>,β^<(i)>) is good forπ if π accepts α^<(i)> and rejects β^<(i)>. We prove that the BCM problem is NP-complete even for a very simple type Ω_1={z|φ≠z⊆Σ}, which is used, in practice, for describing protein motifs in the PROSITE database. We also show that the NP-completeness of the problem does not change for the type Ω_∞=Ω_1∪{Σ+}∪{Σ^<(i, j)>|1≤i≤j}, whereΣ^<(i, j)> is the set of strings over Σ of length between i and j. Furthermore, for the BCM problem forΩ_1, we provide a polynomial-time greedy algorithm based on the probabilistic method. Its performance analysis shows an explicit approximation ratio of the algorithm.

Journal

  • IEICE technical report. Theoretical foundations of Computing

    IEICE technical report. Theoretical foundations of Computing 95(344), 55-64, 1995-10-27

    The Institute of Electronics, Information and Communication Engineers

References:  13

Codes

  • NII Article ID (NAID)
    110003191466
  • NII NACSIS-CAT ID (NCID)
    AN10013152
  • Text Lang
    ENG
  • Article Type
    ART
  • Data Source
    CJP  NII-ELS 
Page Top