可変長ギャップ付き文字列に対する近似マッチング・アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
DNA配列やアミノ酸配列においては、あるパターンの後に数十文字のギャップがあってから別なパターンが現れる場合がある。そのような文字列を検索するためには指定された範囲長の任意文字列とマッチすることのできる記号を含んだパターンに対する近似マッチングが必要となる。本稿では、そのための動的計画法に基づくO(mn log n)時間アルゴリズム、および、Landau-Vishkinアルゴリズムに基づくO((k+log n)gn)時間アルゴリズムを示す。なお、mはパターン長、nはテキスト長、gは可変長ギャップ記号の個数である。
- 一般社団法人情報処理学会の論文
- 1995-01-23
著者
関連論文
- 最小キーおよび最適部分構造スクリーンの近似
- 二つの点集合の最大共通部分点集合を求めるランダマイズド・アルゴリズム
- 二次元配列間の距離について
- タンパク質立体構造の折れ線による近似とその構造マッチングへの応用
- 可変長ギャップ付き文字列に対する近似マッチング・アルゴリズム
- タンパク質立体構造に対する部分構造検索およびアラインメント・アルゴリズム
- 高次元点集合の合同性判定について
- Don't Care記号つき文字列に対する近似マッチング・アルゴリズム
- 複数の点集合の最大共通部分集合の近似可能性について