ゲノム情報解析におけるスコア関数学習の計算複雑度について
スポンサーリンク
概要
- 論文の詳細を見る
ゲノム情報解析においてはスコア関数が幅広く用いられている。これまでにサンプルデータからスコア関数を導出する実用的方法が数多く提案されてきたが、計算論的な解析はほとんど行われていなかった。本稿ではサンプルデータが与えられた時にそれと無矛盾なスコア関数を導出する問題について考察を行い、多くの問題に適用可能な手法を提案する。この手法では、スコア関数が無矛盾であるという制約を線形不等式集合で表し、それにLPを適用することによりスコア関数を導出する。一方、タンパク質スレッディングと呼ばれる問題については、スコア関数の導出が計算論的観点から困難であることを示す。
- 一般社団法人情報処理学会の論文
- 1997-05-16
著者
関連論文
- 局所探索法とその拡張 : タブー探索法を中心として
- A Set Covering Approach for the Pickup and Delivery Problem with Additional Constraints (Numerical Optimization methods, theory and applications)
- 多制約配送計画問題に対する集合被覆アプローチ
- 分枝限定法 : さらなる計算効率の希求(堅く柔らかく…数理計画アプローチ再訪)
- 2-A-3 MAX-2-SATに対する分枝限定法の改良(離散最適化(3))
- 1-A-5 矩形パッキング問題に対する厳密解法(離散最適化(2))
- 時間枠つき配送計画問題に対するパス再結合と適応的パラメータ調整
- 分子生物情報学の現状と動向 (「分子生物情報学の新展開」)
- 特集「分子生物情報学の新展開の編集にあたって (「分子生物情報学の新展開」)
- 点集合の距離重複度列のノルムと最大部分集合問題
- DNAマイクロアレイ画像の解析
- DNAマイクロアレイ画像の解析
- リアルタイムシステムの固定優先度スケジューリングに対する優先度周期探索法
- 最適化アルゴリズム : この10年の歩み(最適化 : 広がる応用)
- ルール生成に必要なデータ量に関するランダム性に基づいた解析
- 1-D-1 ルール生成に必要なデータ量に関するランダム性に基づいた解析(マーケティング(1))
- DNA2次元電気泳動画像のパターンマッチング : 問題の困難さとヒューリスティック・アルゴリズム
- DNA2次元電気泳動画像のパターンマッチング : 問題の困難さとヒューリスティック・アルゴリズム
- 線形計画法による非線形システムS-systemの推定
- 2-F-15 点容量付き内向木詰込問題の計算量(グラフ(2))
- 点容量付き内向木詰込問題の計算複雑度
- 長方形配置問題に対するbest-fit法の効率的な実現
- 組込みシステムにおけるスケジューリングテーブル作成法 (最適化モデルとアルゴリズムの新展開)
- 排他制約付きナップサック問題における上界の計算法およびその有効性 (最適化モデルとアルゴリズムの新展開)
- 3次元パッキングに対する効率的なbottom-left法 (最適化モデルとアルゴリズムの新展開)
- Bottom-Left 安定点の効率的な列挙法とその応用 (最適化モデルとアルゴリズムの新展開)
- RA-006 3次元箱詰め問題に対する構築型解法の効率的実現法(A分野:モデル・アルゴリズム・プログラミング,査読付き論文)
- 近傍ハッシュ法によるエラー許容頻出パターン列挙(一般セッション3)
- Fast Algorithms to Enumerate All Common Intervals of Two Permutations and Their Applications(Optimization Theory in Descrete and Continuous Mathematical Sciences)
- 多点対カット問題に対する集合被覆アプローチに基づく近似解法
- LA-004 Analysis of an Edge Coloring Algorithm Using Chernoff Bounds
- Chernoff Bounds を用いた辺彩色アルゴリズムの解析
- 半定値計画法にもとづく彩色問題の発見的解法
- DS-1-13 A Path Relinking Approach with an Adaptive Mechanism to Control Parameters for the Vehicle Routing Problem with Time Windows
- TD-1-3 バイオインフォマティクスにおける知識発見
- 局所多重アライメントのための局所探索アルゴリズム : 特殊ケースにおける収束性の解析と腫瘍細胞分類への応用
- ゲノム情報解析の現状と課題
- バイオインフォマティクスへの扉
- 遺伝子制御ネットワーク解明のためのアルゴリズム (ゲノムサイエンスの新たなる挑戦) -- (第3部 ゲノム情報科学)
- 遺伝子発現制御ネットワークの論理的解析
- 配列のローカル・アラインメントの困難さについて
- 遺伝子ネットワーク解明のためのアルゴリズム
- 立体構造のマルチプルアラインメントに基づくタンパク質立体構造予測
- 東京大学医科学研究所ヒトゲノム解析センターDNA情報解析分野
- 遺伝子ネットワーク解明のためのアルゴリズム
- RNA二次構造予測のための近似アルゴリズム
- ゲノム情報解析におけるスコア関数学習の計算複雑度について
- 3.幾何的マッチングによるタンパク質立体構造の比較 (「ゲノム情報」)
- タンパク質スレッディング問題の近似について
- 多重グラフにおける均等辺彩色を求める高速アルゴリズム
- 行列乗算とハッシュ関数を用いたブーリアンネットワークの同定アルゴリズム
- 織方図作成における最適化問題のグラフによる定式化 (数値最適化の理論と実際)
- 局所探索法 : 反復改善に基づく最適化の基本戦略(新・ORの図解,学会創立50周年記念号)
- 離散最適化問題に対するメタヒューリスティクス(ここまで使える数理計画法)
- Combinatorial Optimization : Theory and Algorithms (3rd Edition), B. Korte and J. Vygen 著, 出版社 Springer, 発行 2006年, 全ページ 597頁, 価格 53.45ユーロ, ISBN 3-540-25684-9
- 有効ターム数の確率的解析(不確実性の下での意思決定と数理モデル)
- メタヒューリスティクスの世界
- 組合せ最適化の数理--計算困難問題への挑戦 (特集 数理工学の地平--現代における新展開)
- 「メタ・ヒューリスティクス」を使ってみよう!
- 「メタ・ヒューリスティクス」って何ですか?
- 数理計画ソフト初体験 (ユーザのための数理計画応用)
- 遺伝アルゴリズムにおける交叉法に対する一考察(計算量理論)
- 大規模な線形順序付け問題に対する高性能な局所探索アルゴリズム
- 頂点容量制約付き有向全域木パッキング問題に対する近似解法
- 第30回SSORを振り返って
- サブツアー交換交叉に対する二つのコメント
- サブツアー交換交叉に対する2つのコメント
- 線形計画法による非線形システム S-system の推定
- ブーリアンネットワークの高速同定アルゴリズム
- 遺伝子発現パターンデータからの定性ネットワークの推定
- 遺伝子発現パターンからの細胞分類アルゴリズム
- 頂点容量付き有向全域木パッキング問題に対するラグランジュ緩和ヒューリスティック (最適化手法の深化と広がり)
- 複雑な個数制約の付いた多資源一般化割当問題について (最適化手法の深化と広がり)
- レクトリニア多角形配置問題に対する高速な構築型解法
- 線形順序付け問題の解法(ランキングとレイティング)
- Heuristic Algorithms for Rectilinear Block Packing (アルゴリズムと計算理論の新展開 : RIMS研究集会報告集)
- 線形計画法による遺伝情報解析のためのスコア関数の学習
- 一般化上界制約付き集合多重被覆問題に対する発見的解法 (最適化手法の理論と応用の繋がり)
- 2-C-1 通過節点と通過経路に制約を持つ最短路問題とその解法(離散最適化(2))
- 2-A-9 一般化上界制約付き集合多重被覆問題に対する発見的解法(特別セッション スモールビジネスOR(1))
- 汎用ソルバーによる研究集会開催日程スケジューリングの自動化(論文・事例研究)
- 2-A-5 最適化アルゴリズムを実装する際の留意点について : 組合せ最適化問題に対するメタヒューリスティクスの場合を中心として(特別セッション 最適化の実装技術)
- RA-005 3次元パッキング問題に対するbest-fit法の効率的実現法(アルゴリズム・コンピュテーション(3),A分野:モデル・アルゴリズム・プログラミング)
- 2-B-9 通過節点と通過経路に制約を持つ最短路問題:解法実装の改良(離散最適化(6))
- 学生実験のスケジューリングシステムの構築(現場とつながるOR)
- メタ戦略-問題解決のための実践的解法
- メタヒューリスティクス事始め : まずは局所探索法から(はじめようメタヒューリスティクス)
- 概説メタ戦略(はじめようメタヒューリスティクス)
- 3次元箱詰め問題に対する構築型解法の効率的実現法(一般)