近傍ハッシュ法によるエラー許容頻出パターン列挙(一般セッション3)
スポンサーリンク
概要
- 論文の詳細を見る
ゲノム配列から,ある機能発現に関わる遺伝子を発見したいという要望がある.このような遺伝子は対象となるゲノム配列集合においてエラーを含んだ形で類出する配列パターンの形をとることがしばしばある.本研究では,エラーを含む文字列集合から,ある長さの頻出部分文字列パターンを高速に全列挙するアルゴリズムを提案する.エラーの影響から通常のパターン列挙と異なり,入力文字列には現れないパターンも列挙の対象となる.提案手法ではパターン頻出性の必要条件を利用して最小限の候補パターンをハッシュ格納することにより,高速な全列挙を実現する.
- 一般社団法人情報処理学会の論文
- 2008-06-19
著者
-
小野 廣隆
九州大学システム情報科学研究院
-
小野 廣隆
九州大学
-
漆原 秀子
筑波大学大学院生命環境科学研究科
-
宇野 毅明
国立情報学研究所
-
柳浦 睦憲
名古屋大学大学院 情報科学研究科
-
橋本 英樹
京都大学情報学研究科
-
橋本 英樹
京都大学大学院
-
宇野 毅明
東京工業大学 システム科学専攻
-
宇野 毅明
情報学研究所
-
宇野 毅明
東京工業大学経営工学専攻
-
柳浦 睦憲
名古屋大学
-
橋本 英樹
名古屋大学
-
漆原 秀子
筑波大学・生物科学系
-
宇野 毅明
東京工業大学社会理工学研究科
-
小野 廣隆
九州大学システム情報科学府
-
橋本 英樹
京都大学:(現)中央大学理工学部経営システム工学科
-
Urushihara H
Institute Of Biological Sciences Tsukuba University
-
Urushihara Hideko
Graduate School Of Life And Environmental Sciences University Of Tsukuba
-
漆原 秀子
筑波大学
-
Urushihara Hideko
Institute Of Biological Sciences University Of Tsukuba
-
Urushihara Hideko
Institute Of Biological Science University Of Tsukuba
-
Urushihara Hideko
University Of Tsukuba Institute Of Biological Sciences
-
柳浦 睦憲
名古屋大学情報科学研究科計算機数理科学専攻
-
宇野 毅明
国立情報学研究所:総合研究大学院大学
-
柳浦 睦憲
Department Of Computer Science And Mathematical Informatics Graduate School Of Information Science Nagoya University
-
橋本 英樹
京都大学
関連論文
- 全二分木の簡潔な表現 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 任意のカバー時間を持つ木の構成法 (アルゴリズムと計算機科学の数理的基盤とその応用)
- Multiple Random WalkのCover Timeについて (アルゴリズムと計算機科学の数理的基盤とその応用)
- 高速復元可能な接尾辞配列圧縮法(FIT推薦論文)(情報・システム基礎)
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- 量子アルゴリズムによる近似文字列出現頻度問い合わせ
- メトロポリスウォークの到達時間及び全訪問時間に関するタイトな上界
- 連続確率分布枝重み付きDAGに対する最長路長さ分布の計算 (理論計算機科学の深化と応用)
- Metropolis Walkのcover timeにおけるタイトな上界 (理論計算機科学の深化と応用)
- 2点連結な直並列グラフ上の高速なランダムウォーク (理論計算機科学の深化と応用)
- DS-1-8 Computing the Exact Distribution Function of the Longest Path Length in Directed Acyclic Graphs with Exponentially Distributed Edge Lengths
- 証明書分散問題の近似可能性について
- RA-003 A Counting-Based Approximation the Distribution Function of the Longest Path Length in Directed Acyclic Graphs
- グラフ上の線形Cover Timeランダムウォーク実現の必要条件
- 辺上を移動するロボット1台による最適な多角形探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 確率的な枝重みをもつ有向非巡回グラフにおける最長路長さの分布関数の解析的な計算に関する考察 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 3点系統樹を入力とした系統樹構築の近似アルゴリズムの近似比とその解析 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 局所的な次数情報を用いた無向グラフの探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- グラフ上の線形Cover Timeランダムウォーク実現の必要条件 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 重み付きグラフ上の枝被覆に対する次数均等化と重み最小化 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 局所探索法による熱力学的DNA配列設計の改良 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- DS-1-10 Approximating Distribution of Optimization Problems with Normally Distributed Edge Weights by Approximate Counting
- 負荷分散枝被覆問題に対する最適性とアルゴリズム
- 局所情報を用いたスケールフリーネットワークの探索
- 2-F-11 An O(n log^2 n)-Time Algorithm for L(2,1)-Labeling of Trees
- RA-002 木のL(2,1)-ラベリングのためのO(n log^2 n)時間アルゴリズム(モデル・アルゴリズム・プログラミング,査読付き論文)
- 木のL(2,1)-ラベリングに対するO(n^)時間アルゴリズム
- 最大出次数最小化問題の各種グラフクラスに対する計算複雑さ
- RoboCup サッカーシミュレーションリーグの紹介(ロボカップにおける技術とその産業応用の可能性)
- 木の(p, q)-全ラベリング問題
- 自己安定リーダー選挙MPPにおける領域複雑度の上下界について
- 外平面的グラフの(2,1)-全ラべリング数のタイトな上界
- 全二分木の簡潔な表現
- 高頻度なフレーズの検索が高速な索引
- 最大支配問題
- グラフの最小出次数最大化問題
- 正規分布に従う枝重みをもつグラフにおける最小全域木コストの分布関数の近似手法
- 確率的枝重みを持つグラフ上での最小全域木コストの近似見積り法に関する考察(計算機科学の理論とその応用)
- A-028 ある種の不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- 混合ドミノタイリングの連結性
- トーラス型ネットワーク上の効率的なブロードキャスト方式について
- 木のL(2, 1)-ラベリングに対する線形時間アルゴリズム
- A-023 接尾辞木に対する二分木化と簡潔データ構造による圧縮(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- A-022 圧縮された接尾辞配列を用いた近似文字列照合(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- RA-007 高速復元可能な接尾辞配列圧縮法(モデル・アルゴリズム・プログラミング,査読付き論文)
- 近傍ハッシュ法によるエラー許容頻出パターン列挙(一般セッション3)
- 近傍探索の解合流性に基づく並列局所探索法の考察(計算理論とアルゴリズムの新展開)
- 守備特訓に喘ぐ外野手のための捕球経路問題 (計算機科学基礎理論の新展開)
- 匿名ネットワーク上のリーダー選出問題の空間計算量 (計算機科学基礎理論の新展開)
- データの論理的解析における正関数発見の並列化 (計算機科学基礎理論の新展開)
- 分解可能なしきい関数を用いたデータ解析 (計算機科学基礎理論の新展開)
- 移動物体回収問題 : ロボットに効率良く物体を回収させるアルゴリズムの設計のために(学生/教養のページ)
- k-集合合意問題を解く故障検知器
- 移動物体回収問題
- 動的近傍操作を用いたDNA塩基配列設計
- 隠れマルコフモデルを用いたDNA配列設計
- 負荷分散セミマッチングにおける最適性について
- DS-1-10 DNA構造変化の特徴解析(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- 故障数制限付きリーダー選挙問題に対する故障検知器
- ホーン理論の内包・外包に対する演繹推論
- ブックマーク問題の近似について
- $k$-Set Agreement を解く故障検知器(計算機科学の理論とその応用)
- センサーネットワークにおける省電力高信頼なデータ伝送(計算機科学の理論とその応用)
- 局所探索法に基づくDNA 配列設計手法(計算機科学の理論とその応用)
- 部分文字列の高速復元に適した圧縮データ構造に関する研究(計算機科学の理論とその応用)
- DNA形態変化におけるエネルギー障壁値の高速近似計算 (計算機科学基礎理論とその応用)
- DNA計算における局所探索法による反応障壁近似計算
- DNA計算における局所探索法による反応障壁近似計算
- Minimum Universal Evaluation Tree for Boolean Circuits (Evolutionary Advancement in Fundamental Theories of Computer Science)
- 最大重み付き出次数を最小化するグラフ有向化問題の近似(不)可能性
- 最大出次数を最小化するグラフ有向化について
- ボトムアップ手法を用いた系統樹構築の近似アルゴリズム(計算機科学の理論とその応用)
- 量子アルゴリズムによる近似文字列出現頻度問い合わせ (計算機科学基礎理論とその応用)
- 量子回路における定数段加算器の設計(計算理論)
- Approximating the path-distance-width for $k$-cocomparability graphs (Mathematical Foundations and Applications of Computer Science and Algorithms)
- DS-1-6 MPPモデルにおけるリーダー選挙問題の容量複雑性(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 非同期匿名ロボットによる最適マッチングを用いたパターン形成アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- マッチングを用いたパターン形成アルゴリズム
- 境界上を移動可能なロボット2台による多角形探索(計算機科学の理論とその応用)
- 負荷分散枝被覆問題に対する最適性とアルゴリズム(計算機科学の理論とその応用)
- センサーネットワークにおける省電力高信頼なデータ伝送(計算理論とアルゴリズムの新展開)
- 非同期分散システムにおける故障検知器と故障計数器について(計算理論とアルゴリズムの新展開)
- DNA 分子の濃度と反応速度の関係解析(計算理論とアルゴリズムの新展開)
- ワイヤレスネットワークにおけるエネルギー効率の良いオンラインブロードキャスト
- ワイヤレスネットワークにおけるエネルギー効率の良いオンラインブロードキャスト
- 最大支配問題
- タイル縁に上書きルールを用いた敷き詰め問題
- タイル縁に上書きルールを用いた敷き詰め問題
- 効率の良い罫線描画について
- 文書データベースへの効率的な索引付けとその更新に関する研究
- 分子構造変化のモデル化と反応速度の理論的解析 (計算機科学基礎理論とその応用)
- 進化的ネットワークにおける探索アルゴリズムの提案 (計算機科学基礎理論とその応用)
- データの論理的解析における階層的分解構造について(数理計画(1))
- データの論理的解析における分解構造について(情報・通信)
- 論理的データ解析における階層的分解構造について
- メタ戦略アルゴリズムに対するロバストな並列化 (計算機科学基礎理論の新展開)
- ランダムグラフ上の多種ランダムウォークの全訪問時間 (アルゴリズムと計算理論の新展開)
- On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
- 次数上下界制約付きグラフ向き付けにおけるペナルティ最小化