<学術雑誌論文>
ビットパラレル手法によるアライメントアルゴリズム

作成者
本文言語
出版者
発行日
収録物名
出版タイプ
アクセス権
関連URI
概要 近似文字列照合問題は,二つの文字列と閾値が与えられて,片方の文字列の部分文字列のうち,もう一方の文字列との編集距離が閾値以下となるものを見つける問題である. この問題をビットパラレルと呼ばれる手法により高速に解くアルゴリズムがMyers により提案されているが,出力として編集距離だけではなくアライメントも求める場合には適用できない.本論文では,近似出現に対するアライメントについての正規形の概念を導...入し,Myers のアルゴリズムを近似文字列照合に対するアライメント問題へ拡張する
Approximate matching problem is, given two stringsand a parameter, to find all substring of a stringwhose edit distance with the other string is at mostthe parameter. Myers introduced an efficient algorithmbased on bit-parallelism for approximate matchingproblem. However, if alignment of strings is requiredas the answer of the problem, the algorithmcan not be applied straightforwardly. In this paper, an idea of normalization of alignment is introduced and the algorithm by Myers is expanded to alignment problem.
続きを見る

本文情報を非表示

baba1 pdf 110 KB 232  

詳細

レコードID
査読有無
関連情報
ISSN
NCID
登録日 2010.04.08
更新日 2020.11.27

この資料を見た人はこんな資料も見ています