木の最適ラベリング問題とその進化系統樹への応用
スポンサーリンク
概要
- 論文の詳細を見る
本稿では、葉にラベルを持つ木に対し、枝におけるラベルの差異が最小となるように、内部頂点にラベルを割り当てる問題(OTLAP)を考察する。全ての割り当てを試す自明なアルゴリズムを用いた場合、頂点数nの木にm種類のラベルを最適に割り当てるときの時間計算量はO(m^n)であり,頂点数nの指数時間を要する。そこで本稿では、入力の木に対して,多項式時間で最適ラベリングを計算する動的計画法アルゴリズムDPAOを与える。アルゴリズムの時間計算量は,O(km^2n)時間であり,木の頂点数nに関して線形である.ここに,kは木の最大次数とする.また、提案手法をインフルエンザウイルスの進化系統樹における仮想的分類単位の最適ラベリング問題に応用する。
- 2009-02-26
著者
関連論文
- 木の最適ラベリング問題とその進化系統樹への応用
- インフルエンザウイルスのRNA分節間に起こる共変異の探索 (特集 「諸分野の連携による知識発見」および一般)
- 接尾辞木を用いた圧縮尺度計算による効率よいスパムポスト検出手法(ポスターセッション,iDBフォーラム2008(招待講演・ポスター英語ディスカッション))
- インフルエンザウイルスの抗原変異予測とワクチン (特集 新型インフルエンザウイルス)
- 極小出現を用いた頻出多部エピソードの効率のよい発見アルゴリズム (特集 「知見の創出を目指した情報技術」および一般)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム (コンピュータシステム)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム (VLSI設計技術)
- 数値データからの意外な回帰結合ルールの発見
- XQUBE:具体例と演示からのXQuery問合せ構築のための視覚言語(セッション6c:問合せ処理・インデクシング)
- An EM algorithm for inferring geographic transmission probability tables from a large phylogenetic tree (特集 「ベイジアン・ネットワーク」および一般)
- インフルエンザウイルスの進化における共変異の変化の解析(セッション7)
- インフルエンザウイルスの進化における共変異の変化の解析
- D-4-18 高速ストリーム処理のための文字列パターン照合手法とそのFPGA設計(D-4. データ工学,一般セッション)
- 学際領域にて(編集委員今年の抱負2009:経糸から横糸まで)
- D-1-7 並列ビット分配にもとづいた効率的な正規表現照合アルゴリズム(D-1.コンピュテーション,一般セッション)
- 非巡回正規表現に対する効率的なパターン照合
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- 頻出順序木パターンを見つけるオンラインアルゴリズム (計算機科学基礎理論の新展開)
- 滑走窓や忘却の概念を用いたオンライン型半構造データマイニングアルゴリズム
- 滑走窓や忘却の概念を用いたオンライン型半構造データマイニングアルゴリズム
- 半構造データマイニングのための部分構造パターンの効率的探索
- D-1-6 動的刈り込み接尾辞木を用いた圧縮尺度計算によるスパム検出(D-1. コンピュテーション,一般セッション)
- ウェブ閲覧における効率的なキーワード抽出とその利用
- 4ZK-7 ブラウジング支援のための一覧性の高いキーワードリストの抽出(情報爆発時代におけるテキストデータ処理,学生セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- プロパティ接尾辞木のオフライン線形時間構築アルゴリズム(構造化文書・XML,データ工学論文)
- D-020 プロパティ接尾辞木 : メタデータ付き系列データのための効率よい索引構造(D分野:データベース)
- プロパティ付き接尾辞木の効率よいオフライン構築について
- LA_002 単語幅を制約した接尾辞木の効率のよい構築アルゴリズム(A分野:モデル・アルゴリズム・プログラミング)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとついたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- WWWからの情報抽出 : Webラッパーの自動構築(WWW上の情報の知的アクセスのためのテキスト処理)
- テキストマイニングにおける最適パターン発見
- テキストマイニングにおける最適パターン発見(データ・テキストマイニング)
- ウェブデータマイニング(「データマイニング特集号」)
- HTMLからのテキストの自動切り出しアルゴリズムと実装
- 底節の最小汎化に基づく仮説の発見手法
- スキーマと質問を用いた述語発見による論理プログラムの構成的学習アルゴリズム
- 底節の最小汎化に基づく仮説の発見手法
- 正則な木関係の所属性質問と等価性質問による学習
- 分散記憶型並列計算機における大規模接尾辞配列の構築法
- テキストマイニングを用いたウェブデータからのキーワード獲得
- 分散記憶型並列計算機における大規模接尾辞配列の構築法
- HTMLからのテキストの自動切り出しアルゴリズムと実装
- テキストデータからの高速データマイニング : 探索的文書ブラウジングとウェブデータへの応用(発見科学)
- 細菌検査データからの頻出二部エピソードの抽出 (特集 「諸分野の連携による知識発見」および一般)
- 1.「知識創出学」とは?(北の国から明日のICTに架ける橋,知の創出を支える次世代IT基盤技術-北海道大学グローバルCOEプログラムと北海道内情報通信系研究グループの活動-)
- 2.情報系異分野共同研究プロジェクト(北の国から明日のICTに架ける橋,知の創出を支える次世代IT基盤技術-北海道大学グローバルCOEプログラムと北海道内情報通信系研究グループの活動-)
- 極小出現区間を用いたエピソードマイニングの高速化(データベース・アルゴリズム)
- 極小出現区間を用いたエピソードマイニングの高速化(データベース・アルゴリズム)
- ラベル付きグラフからのウォークの多項式時間学習
- 塩基およびアミノ酸配列における共変異集合を列挙する高速アルゴリズム
- D-019 ビット並列手法に基づく大規模連続ストリームパターン照合(D分野:データベース)
- データインテンシブコンピューティング : その2 頻出アイテム集合発見アルゴリズム(知能コンピューティングとその周辺〔第2回〕)
- 生物配列の局所マルチプルアラインメントの計算困難性
- 大規模幾何データからの高速な極大部分グラフ発見 (特集 「ウェブマイニング」および一般)
- TANE--学習を用いた柔軟な情報抽出ウェブブラウザ (特集 「ウェブマイニング」および一般)
- D_045 大規模文字列ソートのための適応的なデータ分割アルゴリズム(D分野:データベース)
- ゼロサプレス型二分決定グラフを用いたトランザクションデータベースの効率的解析手法(データマイニング,データ工学論文)
- Efficient Discovery of Maximal Two-Dimensional Patterns with Don't-Cares(extended abstract) (テーマ:特集「ウェブデータの知的処理」および一般)
- 深さ優先探索に基づく変数制限つき極大モチーフの高速マイニング (テーマ:「データマイニングと統計数理」および一般)
- ワイルドカードを許した極大モチーフの列挙アルゴリズム
- 大規模データストリームのためのマイニング技術の動向(データ工学論文)
- A Catalog for Prediction-Preserving Reducibility with Membership Queries on Formal Languages (New Developments of Theory of Computation and Algorithms)
- E-007 構文グラフ集合を用いたKey Semanticsマイニング(E.自然言語・文書・ゲーム)
- 大規模木構造データからの頻出無順序木パターン発見アルゴリズム (計算機科学基礎理論の新展開)
- 半構造データマイニングにおけるパターン発見技法
- 大規模木構造データからの頻出部分構造パターン発見アルゴリズム(文字列アルゴリズム)
- 高速な無順序木パターン発見アルゴリズム (人工知能基礎論研究会(第54回)特集「医療及び化学情報マイニング」および一般)
- 半構造データからの効率よい無順序木パターン発見手法(インターネット環境でのデータ工学とディペンダビィリティ及び一般)
- 半構造データからの効率よい無順序木パターン発見手法(インターネット環境でのデータ工学とディペンダビィリティ及び一般)
- 半構造データからの効率よい無順序木パターン発見手法
- 大規模木構造データからの高速な部分構造発見(「21世紀の知識情報科学に向けて」,及び一般)
- 2部クリークを用いたclosed item setの効率的な列挙(「21世紀の知識情報科学に向けて」,及び一般)
- データストリーム処理のための効率良いXPath問合せ機構(セッション4A : 時空間データ・ストリーム)
- データストリーム処理のための効率良いXPath問合せ機構(時空間データ・ストリーム)(「夏のデータベースワークショップ(DBWS2003)」一般)
- インフルエンザウイルスの進化における共変異の変化の解析(セッション7)
- テキストマイニング:ウェブデータからの知識発見を目指して (特集 情報論的学習理論--機械学習のさまざまな形)
- コントラストセットマイニングに基づく順序付きグループ列分割手法 (「生命情報からの知識発見」及び一般)
- グループ列分割に基づくインフルエンザウイルスのアミノ酸置換における時代的変化の解析
- グループ列分割に基づくインフルエンザウイルスのアミノ酸置換における時代的変化の解析
- データマイニング : ウェブデータからの知識発見を目指して
- AIとAI?(編集委員2007年の抱負)
- TK-7-1 知の創出を支える次世代IT基盤拠点(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-1 知の創出を支える次世代IT基盤拠点(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-1 知の創出を支える次世代IT基盤拠点(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-1 知の創出を支える次世代IT基盤拠点(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-1 知の創出を支える次世代IT基盤拠点(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- D-4-2 オンラインXMLストリーム処理のための効率良い木正規表現パターン照合アルゴリズム(D-4.データ工学,一般セッション)
- 位置情報付き個人コンテンツ分類のための線形HMMを用いたイベントクラスタリング(機械学習応用,テキスト・Webマイニング,一般)
- インフルエンザウイルスの抗原変異とバイオインフォマティクス
- 近隣剪定法:進化系統樹を利用した配列リサンプリングアルゴリズム
- 近隣剪定法 : 進化系統樹を利用した配列リサンプリングアルゴリズム (ニューロコンピューティング)
- いきものの不思議 ウイルスはどうやって生き延びているのか? : インフルエンザウイルスの存続様式と進化
- 数理科学はインフルエンザウイルスの変異を予測できるか?(疾患の数理モデル(続))
- 近隣剪定法 : 進化系統樹を利用した配列リサンプリングアルゴリズム(一般,機械学習によるバイオデータマインニング,一般)
- G-024 木構造のランダム生成と学習(バイオ情報学,G分野:生体情報科学)
- 近隣剪定法 : 進化系統樹を利用した配列リサンプリングアルゴリズム