位置依存スコア行列の例からの学習の計算複雑度について
スポンサーリンク
概要
- 論文の詳細を見る
位置依存スコア行列(PSSM)はバイオインフォマティクスにおいて幅広く応用されている。例えば、アミノ酸配列群からの共通パターン(モチーフ)検出や、遺伝子制御領域推定、タンパク質の二次構造予測などに利用されている。PSSMは通常は学習データから推定されるが、本稿ではその学習問題について計算論的観点から研究を行なった。具体的には、学習データとして与えた正負の例から、正負の例を正しく分類するPSSMがあるかないかを判定する問題を考え、その問題が一般にはNP困難であるが、PSSMのサイズが定数で押さえられる場合には多項式時間で解けることがわかった。また、PSSMの混合分布の推定などの関連する問題についてもいくつかの結果を得た。
- 一般社団法人情報処理学会の論文
- 2002-01-24
著者
-
宮野 悟
東京大学医科学研究所
-
阿久津 達也
京都大学化学研究所バイオインフォマティクスセンター:京都大学大学院情報学研究科知能情報学専攻
-
宮野 悟
東京大学医科学研究所ヒトゲノム解析センター
-
宮野 悟
科学技術振興事業団erato北野共生システムプロジェクト
-
坂内 英夫
東大・医科研
-
オット ザーシャ
東京大学医科学研究所ヒトゲノム解析センター
-
坂内 英夫
東京大学医科学研究所ヒトゲノム解析センター
-
Ott S
Univ. Tokyo Tokyo Jpn
-
阿久津 達也
京都大学化学研究所
関連論文
- 代謝ネットワークの最小反応カットを求めるアルゴリズム
- 整数計画法を用いたブーリアンネットワークの解析・制御手法(システムバイオロジー,システムバイオロジー,一般)
- 高さの制限された無順序木の編集距離問題に対する近似アルゴリズム
- タンパク質ドメインネットワークに対する二部グラフのモデル
- 発見科学の構想と展開(発見科学)
- タンパク質間相互作用ネットワークにおける相互作用ドメイン対の確率的選択に基づくべき乗分布のモデル化
- 分子生物情報学の現状と動向 (「分子生物情報学の新展開」)
- 特集「分子生物情報学の新展開の編集にあたって (「分子生物情報学の新展開」)
- リカレントニューラルネットワークによる細胞内反応経路の脆弱・頑健部位の推定手法(バイオサイバネティックス,ニューロコンピューティング)
- D-2-14 細胞内反応経路の脆弱部位推定に関する一考察(D-2. ニューロコンピューティング,一般セッション)
- リカレントニューラルネットワークを用いた細胞内反応システムにおけるロバストネス瓦解部位予測
- Java RMI による Genomic Object Net の分散オブジェクト化(バイオエンジニアリングI)
- Java Genomic Object Net と SBML Level2間におけるXMLパスウェイのファイル変換(バイオエンジニアリングI)
- 最適degenerate pattern探索アルゴリズムと転写因子結合部位同定問題への適用
- 最適 degenerate pattern 探索アルゴリズムと転写因子結合部位同定問題への適用
- 高さの制限された2個の無順序木に対する最大共通部分木の近似アルゴリズムの改良
- 2J-3 確率モデルに基づく木の類似度のパラメータ学習について(情報爆発時代におけるマルチメディアデータと交通情報システム,一般セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- パス頻度ベクトルからのグラフ推定問題の困難性について
- 類似度の高い無順序木の比較に対する高速アルゴリズム
- ブール関数推定のための貪欲アルゴリズムの性能解析
- タンパク質ベータシート予測 : 動的計画法と形式文法によるアプローチ(一般セッション3)
- 相互作用RNA2次構造予測 : 形式文法によるアプローチ
- 形式文法に基づくRNA2次構造予測(若手研究者のための講演会)
- 複数実験条件下における遺伝子ネットワーク比較のための推定法(セッション4A)
- 超高次元時系列データからの遺伝子ネットワーク推定について
- ペトリネットによる転写制御ネットワークのモデリングと統計的推測(一般セッション1)
- 機械学習によるタンパク質N-ミリストイル化規則の予測(Sequence & structure analysis)
- T-インバリアントによるシグナル伝達経路の構造表現(グラフ, ペトリ, ニューラルネット及び一般)
- T-インバリアントによるシグナル伝達経路の構造表現(グラフ, ペトリ, ニューラルネット及び一般)
- シグナル伝達経路解析のためのペトリネットに基づく形式的表現の提案(コンカレントシステム, 一般)
- ハイブリッド関数ペトリネットによる分裂酵母細胞周期のモデル化とシミュレーション(コンカレント工学及びハイブリッドダイナミカルシステムの理論と応用,一般)
- DNAマイクロアレイ画像の解析
- DNAマイクロアレイ画像の解析
- 期待精度最大化に基づくRNAシュードノット予測
- 構造トポロジーと複雑ネットワーク特徴量からのタンパク質フォールディング速度予測
- がんの多様な鍵分子を探索するネットワーク推定法(セッション3B)
- パスウェイロジスティック回帰モデルに基づくがんの多様性解析(セッション3B)
- 無順序木の編集距離計算のための厳密アルゴリズム
- 整数計画法によるシュードノットつきRNA2次構造予測
- 整数計画法によるシュードノットつきRNA2次構造予測
- 相互作用RNA2次構造予測 : 形式文法によるアプローチ
- 効率的クリークアルゴリズムに基づく電気泳動画像マッチング、タンパク質構造マッチング、および、タンパク質側鎖パッキング
- DNA2次元電気泳動画像のパターンマッチング : 問題の困難さとヒューリスティック・アルゴリズム
- DNA2次元電気泳動画像のパターンマッチング : 問題の困難さとヒューリスティック・アルゴリズム
- ゲノムDNA解析のための2次元電気泳動画像システム
- 線形計画法による非線形システムS-systemの推定
- バイオパスウェイモデリングとシミュレーションを実現するためのシステム : Genomic Object Net(「バイオインフォマティクスの世界」)
- 確率ブーリアンネットワークのアトラクター検出とブーリアンネットワークとのアトラクターの関係
- タンパク質間相互作用ネットワークにおける相互作用ドメイン対の確率的選択に基づくべき乗分布のモデル化
- 入次数に制約のあるブーリアンネットワークに対する先行状態検出問題および制御問題について
- 細胞アレイ解析のための線形計画法を用いたレポーター遺伝子の最適配置
- タンパク質間相互作用強度予測の高速化と困難性(ニューラルネットワーク及び生物工学)
- 制約付きプロファイルアライメント(文字列アルゴリズム)
- タンパク質間の相互作用強度予測(バイオインフォマティック)
- タンパク質間の相互作用強度予測
- パス頻度ベクトルからのグラフ推定問題の困難性について
- 整数計画と帰還点集合による代謝ネットワークの構造的堅牢性の測定
- 生育温度による代謝ネットワーク構造の差異
- 21aTP-11 原核生物における代謝ネットワークの構造と成育温度の関係(生物・生態系(社会・言語・ゲーム等含む)1,領域11,統計力学,物性基礎論,応用数学,力学,流体物理)
- 半空間の和集合の例からの推定
- 位置依存スコア行列の例からの学習の計算複雑度について
- On the Complexity of Data Mining for Binary Decision Diagram Rules
- 2分決定グラフによるデータマイニングシステム
- 2K-1 高さ制約付き無順序木の高速類似検索アルゴリズムについて(情報爆発時代におけるアルゴリズム高率化,一般セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 共通配列探索手法とベイジアンネットワークによる遺伝子ネットワーク推定
- 生物配列の局所マルチプルアラインメントの計算困難性
- バイオインフォマティクスへの誘い : バイオ情報学研究会(研究会千夜一夜)
- 「情報処理学会論文誌 : 数理モデル化と応用」の編集にあたって
- 「情報処理学会論文誌 : 数理モデル化と応用」の編集にあたって(まえがき)
- 「情報処理学会論文誌 : 数理モデル化と応用」の編集にあたって
- TD-1-3 バイオインフォマティクスにおける知識発見
- 局所多重アライメントのための局所探索アルゴリズム : 特殊ケースにおける収束性の解析と腫瘍細胞分類への応用
- ゲノム情報解析の現状と課題
- バイオインフォマティクスへの扉
- 遺伝子制御ネットワーク解明のためのアルゴリズム (ゲノムサイエンスの新たなる挑戦) -- (第3部 ゲノム情報科学)
- 遺伝子発現制御ネットワークの論理的解析
- 配列のローカル・アラインメントの困難さについて
- 遺伝子ネットワーク解明のためのアルゴリズム
- 立体構造のマルチプルアラインメントに基づくタンパク質立体構造予測
- 東京大学医科学研究所ヒトゲノム解析センターDNA情報解析分野
- 遺伝子ネットワーク解明のためのアルゴリズム
- RNA二次構造予測のための近似アルゴリズム
- 行列乗算とハッシュ関数を用いたブーリアンネットワークの同定アルゴリズム
- 線形計画法による非線形システム S-system の推定
- ブーリアンネットワークの高速同定アルゴリズム
- ロバストな内積計算を用いたスパース学習(セッション2B)
- 5-4 ゲノムデータからの知識発見と遺伝子オブジェクトのシミュレーション (21世紀の医療・福祉を支える科学技術)
- バイオパスウェイのモデル化とシミュレーションに向けて(第11回年会「総合講演」)
- ゲノムデータと発見科学
- 遺伝子発現パターンからの細胞分類アルゴリズム
- バイオインフォマティクスの新しい流れ
- 「バイオインフォマティクスは躍る」
- E-CellからGenomicObjectNetへのバイオパスウェイモデルの変換
- GONとSBMLにおけるXMLパスウェイ形式の対応
- コメント (「明示的理解に魅せられて」へのコメントと回答)
- 生物情報データからの知識発見にむけて
- ヒトゲノム解析センター情報系分野の目指すもの
- ゲノム情報処理における最適化(最適化の数理)
- 6.ゲノムデータからの知識発見 (「ゲノム情報」)
- シミュレーションを通じた感染症対策の設計 : 選択的ワクチン投与による集団免疫強化の事例から(ビッグデータとデータ同化)