ワイルドカードを許した極大モチーフの列挙アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
モチーフとは定数文字と一文字ワイルドカードoからなるABoBoBCのような文字列である.極大モチーフ列挙問題とは, 与えられた文字列上に指定回数以上出現し, しかもより長いモチーフに含まれないようなモチーフをすべて列挙する問題であり, 分子生物学や時系列解析に広い応用をもつ.本論文では, ワイルドカードをもつモチーフの族に対して, 入力文字列長の多項式領域と多項式遅延時間を達成する効率よい極大モチーフ列挙アルゴリズムを与える.具体的には, このアルゴリズムは, 極大モチーフに対する全域木上の深さ優先探索を用いて, すべての極大モチーフを一つあたりO(mn^2)時間とO(lm)領域を用いて列挙する.ここに, nは入力文字列の長さであり, 列挙される極大モチーフxに対して, m=|L(x)|はxの入力文字列中の出現数であり, l=|x|はxの長さである.さらに, 頻出および極大モチーフ数の下限を与え, 単純な列挙方式の限界を示す.
- 2005-09-08
著者
-
有村 博紀
北海道大学大学院情報科学研究科
-
宇野 毅明
国立情報学研究所
-
宇野 毅明
東京工業大学 システム科学専攻
-
宇野 毅明
情報学研究所
-
宇野 毅明
東京工業大学システム科学
-
有村 博紀
北海道大学
-
宇野 毅明
国立情報学研
-
宇野 毅明
国立情報学研究所:総合研究大学院大学
関連論文
- 木の最適ラベリング問題とその進化系統樹への応用
- 弦グラフおよび弦二部グラフのクラスにおけるマッチングの数え上げ
- 木の均一分割問題
- 接尾辞木を用いた圧縮尺度計算による効率よいスパムポスト検出手法(ポスターセッション,iDBフォーラム2008(招待講演・ポスター英語ディスカッション))
- 極小出現を用いた頻出多部エピソードの効率のよい発見アルゴリズム (特集 「知見の創出を目指した情報技術」および一般)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム (コンピュータシステム)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム (VLSI設計技術)
- 数値データからの意外な回帰結合ルールの発見
- XQUBE:具体例と演示からのXQuery問合せ構築のための視覚言語(セッション6c:問合せ処理・インデクシング)
- 最短路高速検索のための階層メッシュ疎化法
- An EM algorithm for inferring geographic transmission probability tables from a large phylogenetic tree (特集 「ベイジアン・ネットワーク」および一般)
- D-4-18 高速ストリーム処理のための文字列パターン照合手法とそのFPGA設計(D-4. データ工学,一般セッション)
- 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)」一般)
- テキストマイニング:ウェブデータからの知識発見を目指して (特集 情報論的学習理論--機械学習のさまざまな形)
- データマイニング : ウェブデータからの知識発見を目指して
- 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マイニング,一般)
- タグとキーワードの関係を利用したテキストマイニング (人工知能基礎論研究会(第46回) 知識ベースシステム研究会(第54回) 合同研究会 テーマ:「アクティブマイニング」および一般)
- タグとキーワードの関係を利用したテキストマイニング (人工知能基礎論研究会(第46回) 知識ベースシステム研究会(第54回) 合同研究会 テーマ:「アクティブマイニング」および一般)
- 1. データストリームのためのマイニング技術(最新!データマイニング手法)
- 分類階層を考慮したパタン照合アルゴリズム (特集 オントロジー)
- テキストマイニング基盤技術(「テキストマイニング」)
- 木の変換規則の例からの学習 (小特集 「発見科学」及び一般演題)
- 飽和集合列挙アルゴリズムを用いた大規模データベースからのルール発見手法 (特集 計算推論--モデリング・数理・アルゴリズム)
- 大規模系列データから代表的な頻出エピソードを発見するための効率よいアルゴリズム (特集「人工知能における論理の新たな展開」)
- 飽和系列パターンの多項式時間列挙アルゴリズム
- 飽和系列パターンの多項式時間列挙アルゴリズム
- 計算学習理論における学習(機械学習,それが人に及ばざる理由)
- TD-1-7 ウェブデータからの高速テキストマイニング
- Webマイニング(「テキストマイニング」)
- 木に含まれる限定サイズ部分木の列挙 (コンピュテーション)
- 系列二分決定グラフを操作するための豊富な演算体系の構築 (Theoretical Foundations of Computing)
- 長大な拡張文字列パターンに対する大規模文字列照合の高速化
- 疎な接尾辞木構築のWord RAM上の高速化
- 超辺の縮約を許した非巡回部分超グラフの効率よい列挙
- 非対称で個体差がある関係データ分析のための機会調整型無限関係モデル(ベイズ統計モデル,統計推理,データベース,一般)