Burrows-Wheeler

Exact-matchとINexact-match、バックトラッキング

Exact-match BW行列は辞書式順序で並んでいる これを利用する あるクエリー配列の末尾の1文字を見て、その文字がBW行列の左端に来ている行を選択する それを満足する行数を数える(それらは固まって存在している) 次いで、クエリー配列の末尾から1、2文字…

Last-first mappingとBW行列から元の文字列を復元すること

#元の文字列 > T [1] "g" "c" "a" "c" "c" "c" # BW行列 > sortedM [,1] [,2] [,3] [,4] [,5] [,6] [,7] [1,] "$" "g" "c" "a" "c" "c" "c" [2,] "a" "c" "c" "c" "$" "g" "c" [3,] "c" "$" "g" "c" "a" "c" "c" [4,] "c" "a" "c" "c" "c" "$" "g" [5,] "c" …

Burrows-Wheeler index

Burrows-Wheeler変換(BWT)はBWTに基づくインデックス方法を用いる 大規模テキストの検索に向く 少メモリで実行可能なことを特徴とする 圧縮技術・塩基配列処理に応用されている BWインデックスを説明する 文字列"acaacg"にBWインデックスを付ける "a,t,g,c"…