DNA2次元電気泳動画像のパターンマッチング : 問題の困難さとヒューリスティック・アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
DNAやタンパク質の2次元電気泳動画像を比較することは、遺伝子の異常の検出などに有効である。そのためには歪みが不均一な場合の2次元平面上の点集合パターンマッチングを行なう必要がある。本稿では、まず、不均一な歪みを持つ場合の点集合のパターンマッチング問題の形式的定義を与え、この問題が2次元以上においてNP困難であることを示す。一方、1次元でかつ点の順序が保存されるという制約つきの場合に対しての、動的計画法に基づく多項式時間アルゴリズムを示す。そして、このアルゴリズムに基づき開発した、DNA2次元電気泳動画像のパターンマッチングのためのヒューリスティック・アルゴリズムを、実行結果例とともに示す。
- 社団法人電子情報通信学会の論文
- 2000-05-04
著者
-
阿久津 達也
東京大学 医科学研究所 ヒトゲノム解析センター
-
阿久津 達也
京都大学化学研究所バイオインフォマティクスセンター:京都大学大学院情報学研究科知能情報学専攻
-
阿久津 達也
京都大学化学研究所バイオインフォマティクスセンター
-
藤山 秋佐夫
国立情報学研究所
-
藤山 秋佐夫
国立遺伝研
-
藤山 秋佐夫
国立情報研:国立遺伝研
-
藤山 秋佐夫
国立遺伝学研究所
-
金家 京徹
三井情報開発株式会社バイオシステム室
-
大山 彰
三井情報開発株式会社バイオシステム室
-
大山 彰
三井情報開発株式会社 バイオシステム室
-
大山 彰
三井情報開発株式会社
-
藤山 秋佐夫
理化学研究所横浜研究所ゲノム科学総合研究センター
-
金家 京徹
三井情報開発株式会社 バイオシステム室
関連論文
- 代謝ネットワークの最小反応カットを求めるアルゴリズム
- 整数計画法を用いたブーリアンネットワークの解析・制御手法(システムバイオロジー,システムバイオロジー,一般)
- 高さの制限された無順序木の編集距離問題に対する近似アルゴリズム
- タンパク質ドメインネットワークに対する二部グラフのモデル
- タンパク質間相互作用ネットワークにおける相互作用ドメイン対の確率的選択に基づくべき乗分布のモデル化
- P-133 高温性水素資化性メタン生成菌の凝集性に関する解析(ポスター発表)
- 1A-11 芳香族化合物による土壌撹乱に対する微生物反応のメタゲノム的解析(口頭発表)
- ゲノム情報 ヒト・チンパンジー比較ゲノム地図
- 分子生物情報学の現状と動向 (「分子生物情報学の新展開」)
- 特集「分子生物情報学の新展開の編集にあたって (「分子生物情報学の新展開」)
- 最適degenerate pattern探索アルゴリズムと転写因子結合部位同定問題への適用
- 最適 degenerate pattern 探索アルゴリズムと転写因子結合部位同定問題への適用
- ヒト21番染色体シークエンス地図 (ゲノムサイエンスの新たなる挑戦) -- (第1部 ヒトのゲノム解析 1.ヒトゲノムの大規模構造・シークエンス解析)
- 高さの制限された2個の無順序木に対する最大共通部分木の近似アルゴリズムの改良
- 2J-3 確率モデルに基づく木の類似度のパラメータ学習について(情報爆発時代におけるマルチメディアデータと交通情報システム,一般セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- パス頻度ベクトルからのグラフ推定問題の困難性について
- 類似度の高い無順序木の比較に対する高速アルゴリズム
- ブール関数推定のための貪欲アルゴリズムの性能解析
- タンパク質ベータシート予測 : 動的計画法と形式文法によるアプローチ(一般セッション3)
- 相互作用RNA2次構造予測 : 形式文法によるアプローチ
- 形式文法に基づくRNA2次構造予測(若手研究者のための講演会)
- 5 肝細胞癌発癌過程におけるテロメア不均一性の意義(第2回新潟ゲノム医学研究会)
- ヒト染色体バンド境界に正確に同定したDNA複製終結領域
- 点集合の距離重複度列のノルムと最大部分集合問題
- DNAマイクロアレイ画像の解析
- DNAマイクロアレイ画像の解析
- 期待精度最大化に基づくRNAシュードノット予測
- 構造トポロジーと複雑ネットワーク特徴量からのタンパク質フォールディング速度予測
- 無順序木の編集距離計算のための厳密アルゴリズム
- ヒト-チンプY染色体の常染色体よりも速い進化 (進化でどこまでわかるか?--日本進化学会2006年大会特集) -- (シンポジウム 霊長類-ヒト--進化速度のパラドクス)
- 整数計画法によるシュードノットつきRNA2次構造予測
- 整数計画法によるシュードノットつきRNA2次構造予測
- 相互作用RNA2次構造予測 : 形式文法によるアプローチ
- 日本語バイオポータルサイトJabion（ジャビオン）の概要とその利用法について
- 霊長類の比較ゲノム科学(「バイオインフォマティクスの世界」)
- 比較ゲノム学 ゲノム時代の比較ゲノム学--ヒトだけ見ればすべてが分かるか? ヒト-チンパンジー比較ゲノム解析研究の意義 (特集=ヒトゲノム解読完了,その先は?) -- (ポストゲノムシークエンス)
- 効率的クリークアルゴリズムに基づく電気泳動画像マッチング、タンパク質構造マッチング、および、タンパク質側鎖パッキング
- ヒトゲノムの解読と初期解析について
- ヒトとチンパンジーのちがいはわずか1.23%だった--世界初の比較ゲノム地図で明らかに
- ヒトゲノムの概要配列解析 (ゲノムサイエンスの新たなる挑戦) -- (第1部 ヒトのゲノム解析 1.ヒトゲノムの大規模構造・シークエンス解析)
- DNA2次元電気泳動画像のパターンマッチング : 問題の困難さとヒューリスティック・アルゴリズム
- DNA2次元電気泳動画像のパターンマッチング : 問題の困難さとヒューリスティック・アルゴリズム
- ゲノム情報 ヒト21番染色体の全解読--その達成への歩みと意義
- ゲノムリソ-スの作成とゲノム生物学への適用(ヒト--物理地図からシ-クエンス地図へ) (ゲノムサイエンス--生命の全体像の解明をめざして) -- (第1部 日本におけるヒト・ゲノム研究の最前線)
- 学会見聞記 第2回 ヒトゲノムシ-クエンシングストラテジ-国際会議
- ゲノムDNA解析のための2次元電気泳動画像システム
- 国際ヒト・ゲノム会議93
- ワ-クショップ「日本におけるヒトゲノム研究」に参加して(学会見聞記)
- Cold Spring Harbor Meeting"ras蛋白質の機能と進化"に参加して
- 線形計画法による非線形システムS-systemの推定
- ゲノムリソース ヒトゲノムリソースの整備 (特集 ゲノム医学の現在と未来--基礎と臨床)
- 確率ブーリアンネットワークのアトラクター検出とブーリアンネットワークとのアトラクターの関係
- タンパク質間相互作用ネットワークにおける相互作用ドメイン対の確率的選択に基づくべき乗分布のモデル化
- 入次数に制約のあるブーリアンネットワークに対する先行状態検出問題および制御問題について
- 細胞アレイ解析のための線形計画法を用いたレポーター遺伝子の最適配置
- タンパク質間相互作用強度予測の高速化と困難性(ニューラルネットワーク及び生物工学)
- 制約付きプロファイルアライメント(文字列アルゴリズム)
- タンパク質間の相互作用強度予測(バイオインフォマティック)
- タンパク質間の相互作用強度予測
- パス頻度ベクトルからのグラフ推定問題の困難性について
- 整数計画と帰還点集合による代謝ネットワークの構造的堅牢性の測定
- 生育温度による代謝ネットワーク構造の差異
- 21aTP-11 原核生物における代謝ネットワークの構造と成育温度の関係(生物・生態系(社会・言語・ゲーム等含む)1,領域11,統計力学,物性基礎論,応用数学,力学,流体物理)
- 半空間の和集合の例からの推定
- 位置依存スコア行列の例からの学習の計算複雑度について
- 2K-1 高さ制約付き無順序木の高速類似検索アルゴリズムについて(情報爆発時代におけるアルゴリズム高率化,一般セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 生物配列の局所マルチプルアラインメントの計算困難性
- バイオインフォマティクスへの誘い : バイオ情報学研究会(研究会千夜一夜)
- 「情報処理学会論文誌 : 数理モデル化と応用」の編集にあたって
- 「情報処理学会論文誌 : 数理モデル化と応用」の編集にあたって(まえがき)
- 「情報処理学会論文誌 : 数理モデル化と応用」の編集にあたって
- TD-1-3 バイオインフォマティクスにおける知識発見
- 局所多重アライメントのための局所探索アルゴリズム : 特殊ケースにおける収束性の解析と腫瘍細胞分類への応用
- ゲノム情報解析の現状と課題
- バイオインフォマティクスへの扉
- 遺伝子制御ネットワーク解明のためのアルゴリズム (ゲノムサイエンスの新たなる挑戦) -- (第3部 ゲノム情報科学)
- 遺伝子発現制御ネットワークの論理的解析
- 配列のローカル・アラインメントの困難さについて
- 遺伝子ネットワーク解明のためのアルゴリズム
- 立体構造のマルチプルアラインメントに基づくタンパク質立体構造予測
- 東京大学医科学研究所ヒトゲノム解析センターDNA情報解析分野
- 遺伝子ネットワーク解明のためのアルゴリズム
- RNA二次構造予測のための近似アルゴリズム
- ゲノム情報解析におけるスコア関数学習の計算複雑度について
- 3.幾何的マッチングによるタンパク質立体構造の比較 (「ゲノム情報」)
- タンパク質スレッディング問題の近似について
- 行列乗算とハッシュ関数を用いたブーリアンネットワークの同定アルゴリズム
- 遺伝子発現量ダイナミックスにおける自己相似性について(バイオインフォマティックス(2))
- バイオインフォマティクスと人工知能の相互作用(バイオインフォマティクスと人工知能の新たなインタラクション)
- 特集「バイオインフォマティクスと人工知能の新たなインタラクション」にあたって(バイオインフォマティクスと人工知能の新たなインタラクション)
- 線形計画法による非線形システム S-system の推定
- ブーリアンネットワークの高速同定アルゴリズム
- 遺伝子発現パターンデータからの定性ネットワークの推定
- 遺伝子発現量の時系列データからの遺伝子ネットワーク推定
- 確率的数理モデルを用いたアポトーシス制御機構の解明
- 遺伝子発現パターンからの細胞分類アルゴリズム
- 線形計画法による遺伝情報解析のためのスコア関数の学習
- 無順序木の編集距離の指数時間厳密アルゴリズム
- 文字列の距離空間上の最大マージン識別器とそのタンパク質科学への応用
- 無順序木の編集距離の指数時間厳密アルゴリズム