Run-Length FM-Index - koki
FM-index は検索対象のテキストから予め索引を構築しておくことで，テキストに含まれる任意のパターン文字列の個数を数えるクエリ$ \mathrm{count} を，テキストのサイズに依らず高速に実行できるデータ構造です．加えて，suffix array や inverse suffix array の一部を追加で保持しておくことで，パターンの位置の列挙 $ \mathrm{locate}やテキストの復元 $ \mathrm{extract}といったクエリを高速に実行することができます（自己索引）． 主要な応用としてゲノム解析（例：HISAT2）などが挙げられます．身近なところでは，arXiv をコーパスとした高速な英文コロケーション検索を提供する Hyper Collocation でも用いられています（解説）． FM-Index に関しては，高速文字列解析の世界 や 簡潔データ構造
2020.08.10 シークエンサーのデータを解析するとき、リードをリファレンス配列にマッピングすることが第一歩である。一般にシークエンサーのリードは数百万個以上で、また、リファレンス配列の塩基数は数億にも及ぶ。これらの数百万のリードを、数億塩基からなるリファレンス配列にマッピングする際に、高速な文字列検索アルゴリズムが必要される。このようなアルゴリズムとして、FM index がある。実際に、現在のマッピングプログラムのほとんどは、FM index アルゴリズムを中心に使用してマッピングを行なっている。なお、FM index は完全一致でしか検索できない。そのため、ほとんどのプログラムでは、まずリードの一部分だけをリファレンスに対して完全一致で検索する。そして、完全一致でヒットした箇所で、リードの残った部分をリファレンスに対して Smith-Waterman アルゴリズムでアライメントを
この記事はISer Advent Calendar 2019の1日目として書かれました。 最近ライブラリの剪定をしているときに「そういえばWavelet Matrix実装してないなぁ」と思ったので実装してみたら想像以上にシンプルで驚いたのでそれについての軽い解説を書きました。競プロ方面への応用については色んな方が記事を書いているので、後半ではWavelet Matrixの全文検索への応用としてFM-indexの話をします。 Wavelet Matrixとは Wavelet Tree 完備辞書(簡潔ビットベクトル) Wavelet Treeの計算量 Wavelet Matrix 各クエリの実装 FM-indexとは Suffix Array Burrows Wheeler 変換 LF mapping FM-index 実装 性能の比較 感想 Wavelet Matrixとは データ構造を知る
FM-Indexのことが懐かしくなったので実装してみました。 github.com 高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 作者:岡野原 大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本 ３種類のビットベクトルの作りかた ビットベクトルに対してrankとselectを高速に処理したいが、そのための補助データの大きさはビット長Nに対してo(N)であって欲しい、という状況がまずあったとします。それを叶える方法はいくつかあります。 １ 以下は最も基本的な方法です。ビットが密 (0と1の出現頻度に大きな差がない) で、出現位置がバラバラなときに使います。 ・ビット列を大ブロックと小ブロックに分ける。 ・最初から各大ブロックまでのrank値を事前計算する。 ・各大ブロック内の最初から各小ブロックまでのrank値も事前計算
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
FM index | アラインメントプログラムでよく使われる文字列検索アルゴリズム
Wavelet MatrixとFM-index - okura diary
FM-Indexのことが懐かしくなったので実装してみた - ubiquitinブログ