ビットパラレル手法によるアライメントアルゴリズム
こっちのPDFのほうがフォントがきれい
著者情報が削られている
Abstract
>近似文字列照合問題は，2 つの文字列と閾値が与えられて，片方の文字列の部分文字列のうち，もう一方の文字列との編集距離が閾値以下となるものを見つける問題である．この問題をビットパラレルと呼ばれる手法により高速に解くアルゴリズムがMyers により提案されているが，出力として編集距離だけではなくアライメントも求める場合には適用できない．本論文では，近似出現に対するアライメントについての正規形の概念を導入し，Myers のアルゴリズムを近似文字列照合に対するアライメント問題へ拡張する．
著者
Myersのbit-parallel法を拡張してSESを求められるようにしたalgorithmっぽい
編集転写という言葉でも言い表されているな
DP行列の定義が読んだだけではわからなかった
編集グラフに相当する概念か？
これ以上は紙にちゃんと書いて考えないとダメだな
2022-02-02
05:34:18 ちゃんと読みたくなってきた
active読書用project
目次
序論
準備
近似出現に対するアライメント
アルゴリズム
動的計画法に基づく単純なアルゴリズム
ビットパラレル手法によるアルゴリズム
ビットパラレル手法はMyersのbit-parallel法のこと
アライメントアルゴリズムへの拡張
実験
結論
参考文献
Bit-parallel sequence-to-graph alignmentという最近の論文も見つけた
#2022-11-06 09:50:58
#2022-11-02 18:01:00
#2022-02-02 05:34:41
#2022-01-31 14:08:32