双対分解によるRNA構造アラインメント
スポンサーリンク
概要
- 論文の詳細を見る
本研究では,期待精度最大化原理に基づいてRNA構造アラインメントを整数計画問題として定式化し,双対分解によってこれを高速に解くアルゴリズムDAFSを提案する.本手法では,双対分解によってRNA構造アランメントを解きやすい部分問題,すなわち共通二次構造予測と(構造を考慮しない)配列アラインメントに分解して独立に効率よく解き,構造アランメントの制約を満たさない予測に対してペナルティを与える,という手順を繰り返すことによって最適解を得る.複数のデータセットにおける計算機実験から,とくに共通二次構造の精度においてDAFSは既存の手法と比べて最も高精度,あるいはそれに匹敵する精度であり,かつ同程度の精度の手法と比べて明らかに高速であることが示された.
- 2012-03-21
著者
-
加藤 有己
京都大学化学研究所バイオインフォマティクスセンター
-
加藤 有己
奈良先端科学技術大学院大学 情報科学研究科
-
榊原 康文
慶應義塾大学理工学部生命情報学科
-
佐藤 健吾
東京大学 大学院新領域創成科学研究科
-
加藤 有己
京都大学 化学研究所 バイオインフォマティクスセンター
-
浅井 潔
東京大学 大学院新領域創成科学研究科
-
佐藤 健吾
慶應義塾大学大学院理工学研究科開放環境科学専攻
-
浅井 潔
東京大学大学院新領域創成科学研究科:産総研生命情報工学研究センター
-
佐藤 健吾
(社)バイオ産業情報化コンソーシアム
-
榊原 康文
慶應義塾大学大学院理工学研究科
-
阿久津 達也
京都大学化学研究所
-
加藤 有己
奈良先端科学技術大学院大学情報科学研究科
関連論文
- 代謝ネットワークの最小反応カットを求めるアルゴリズム
- 整数計画法を用いたブーリアンネットワークの解析・制御手法(システムバイオロジー,システムバイオロジー,一般)
- 高さの制限された無順序木の編集距離問題に対する近似アルゴリズム
- タンパク質ドメインネットワークに対する二部グラフのモデル
- ペア確率多重文脈自由文法によるシュードノットつきRNA2次構造予測
- タンパク質間相互作用ネットワークにおける相互作用ドメイン対の確率的選択に基づくべき乗分布のモデル化
- 大規模ゲノム比較システムの開発と応用
- 3N-7 焼きなまし法を用いた対訳単語対抽出
- 最適degenerate pattern探索アルゴリズムと転写因子結合部位同定問題への適用
- 最適 degenerate pattern 探索アルゴリズムと転写因子結合部位同定問題への適用
- 高さの制限された2個の無順序木に対する最大共通部分木の近似アルゴリズムの改良
- 2J-3 確率モデルに基づく木の類似度のパラメータ学習について(情報爆発時代におけるマルチメディアデータと交通情報システム,一般セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- パス頻度ベクトルからのグラフ推定問題の困難性について
- 類似度の高い無順序木の比較に対する高速アルゴリズム
- ブール関数推定のための貪欲アルゴリズムの性能解析
- AT-2-3 バクテリアコンピュータの開発とバクテリア間通信の構築(AT-2.分子通信,チュートリアルセッション,ソサイエティ企画)
- 比較ゲノム解析システムの開発とマイコバクテリアゲノムへの応用
- 生命の言語の理解をめざして(平成19年度論文賞の受賞論文紹介)
- タンパク質ベータシート予測 : 動的計画法と形式文法によるアプローチ(一般セッション3)
- 相互作用RNA2次構造予測 : 形式文法によるアプローチ
- 形式文法に基づくRNA2次構造予測(若手研究者のための講演会)
- 多重文脈自由文法とマクロ文法の生成能力について
- 期待精度最大化に基づくRNAシュードノット予測
- 期待精度最大化に基づくRNAシュードノット予測
- 構造トポロジーと複雑ネットワーク特徴量からのタンパク質フォールディング速度予測
- 二次錘計画法による多タスク学習算法
- ネットワーク型雑音除去によるマイクロアレイデータからの薬剤耐性予測(機械学習によるバイオデータマイニング)
- ネットワーク型雑音除去によるマイクロアレイデータから由薬剤耐性予測(機械学習によるバイオデータマインニング)
- 無順序木の編集距離計算のための厳密アルゴリズム
- サポートベクタマシンを用いた対話表現の抽出
- ドメイン固有の文字列情報の組み込みによる形態素解析処理の精度の向上
- 最大エントロピー法を用いた対訳単語対の抽出
- 最大エントロピー法を用いた離散型共起表現の抽出
- 多義語の語義ベクトル分解
- 最大エントロピー法による対訳単語対の抽出
- 共起関係を利用した対訳コーパスからの連語の対訳表現抽出
- bigram 統計情報に基づくパージング
- d-bigram と他の統計情報との関連に関する実験
- 自然言語文評価におけるd-bigram 情報の活用方法に関する実験
- 自然言語における有繋文字列の抽出
- d-bigram 情報を用いた統語的規則の抽出
- 統計情報を用いた中国語における文単位一括変換法
- d-bigramを用いた中国語における文単位一括変換法
- d-bigramを用いた形態素解析
- d-bigramを用いた単語のクラスタリング
- d-bigramとtrigramの相関に関する実験
- d-bigramを用いた自然言語文評価に関する実験
- 確率多重文脈自由文法によるRNAシュードノット構造予測(DNA・タンパク質構造)
- RNA2次構造記述向き形式文法の生成能力について(文字列アルゴリズム)
- 整数計画法によるシュードノットつきRNA2次構造予測
- 整数計画法によるシュードノットつきRNA2次構造予測
- 相互作用RNA2次構造予測 : 形式文法によるアプローチ
- 機能性RNAの配列解析と構造解析(バイオインフォマティクスと人工知能の新たなインタラクション)
- 効率的クリークアルゴリズムに基づく電気泳動画像マッチング、タンパク質構造マッチング、および、タンパク質側鎖パッキング
- カーネル行列補完による生物学的ネットワークの推定(学習理論とパターン認識メディア理解, 学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- カーネル行列補完による生物学的ネットワークの推定(学習理論とパターン認識メディア理解, 学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- HMMによる系列の向き及び位置の変分推定法と蛋白質の構造比較への応用(バイオインフォマティクスとパターン認識)
- 確率ブーリアンネットワークのアトラクター検出とブーリアンネットワークとのアトラクターの関係
- タンパク質間相互作用ネットワークにおける相互作用ドメイン対の確率的選択に基づくべき乗分布のモデル化
- 入次数に制約のあるブーリアンネットワークに対する先行状態検出問題および制御問題について
- 細胞アレイ解析のための線形計画法を用いたレポーター遺伝子の最適配置
- タンパク質間相互作用強度予測の高速化と困難性(ニューラルネットワーク及び生物工学)
- 制約付きプロファイルアライメント(文字列アルゴリズム)
- タンパク質間の相互作用強度予測(バイオインフォマティック)
- タンパク質間の相互作用強度予測
- パス頻度ベクトルからのグラフ推定問題の困難性について
- 生育温度による代謝ネットワーク構造の差異
- 21aTP-11 原核生物における代謝ネットワークの構造と成育温度の関係(生物・生態系(社会・言語・ゲーム等含む)1,領域11,統計力学,物性基礎論,応用数学,力学,流体物理)
- 半空間の和集合の例からの推定
- 位置依存スコア行列の例からの学習の計算複雑度について
- 2K-1 高さ制約付き無順序木の高速類似検索アルゴリズムについて(情報爆発時代におけるアルゴリズム高率化,一般セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 生物配列の局所マルチプルアラインメントの計算困難性
- 整数計画法に基づくRNA間相互作用予測
- 整数計画法に基づくRNA間相互作用予測
- トーリックイデアルのグレプナ基底計算アルゴリズム : 数式処理システムAsirへの実装
- AsirによるToric idealのグレブナー基底計算
- 欠損推定量と雑音の分布を用いたマイクロアレイデータ分類
- 7 ポストゲノム時代の配列情報解析(バイオインフォマティクス)
- 配列情報解析と確率モデル(バイオインフォマティクス最前線特集号)
- SVMを用いたタンパク質糖鎖修飾部位予測
- 計算生物学におけるカーネル法(数学者のための分子生物学入門,研究会報告)
- 遺伝子発現量ダイナミックスにおける自己相似性について(バイオインフォマティックス(2))
- タンパク質間相互作用ネットワーク情報による転写機構の解明 (タンパク質間相互作用)
- バイオインフォマティクスと人工知能の相互作用(バイオインフォマティクスと人工知能の新たなインタラクション)
- 確率的数理モデルを用いたアポトーシス制御機構の解明
- DNAマイクロアレイ技術および関連する数学的課題(数学者のための分子生物学入門,研究会報告)
- AND/OR節点で構成されるブーリアンネットワークの定常状態を検出するアルゴリズムの改良
- AND/OR節点で構成されるブーリアンネットワークの定常状態を検出するO(1.787^n)時間アルゴリズム
- アラインメントとアミノ酸構成比に基づいたサポートベクターマシンによるタンパク質の細胞内局在予測
- 生体内ネットワーク構造の数理モデルと情報解析
- 機械学習を用いたDNA修復タンパク質の識別と分類
- RNA構造解析のための確率多重文脈自由文法(Sequence & structure analysis)
- バイオインフォマティクスにおける基本アルゴリズム(数学者のための分子生物学入門,研究会報告)
- Detection and Enumeration of Steady States in Biological Information Networks (Acceleration and Visualization of Computation for Enumeration Problems)
- 大規模ゲノム比較システムの開発と応用
- DNAコンピューターの原理と展望
- 比較ゲノム解析システムの開発とマイコバクテリアゲノムへの応用
- 1 バイオインフォマティクス概説 : 比べることで生命は解明できるか?(バイオインフォマティクス)
- 双対分解によるRNA構造アラインメント
- 機械学習を用いたマススペクトルデータからの糖鎖構造推定法の開発(合同企画セッション:バイオデータマイニング)