ビットパラレル手法によるアライメントアルゴリズム

• 馬場, 謙介

  九州大学大学院システム情報科学研究院

• 于, 雲青

  九州大学大学院システム情報科学研究院

• 村上, 和彰

  九州大学大学院システム情報科学研究院

書誌事項

タイトル別名

• ビットパラレル シュホウ ニ ヨル アライメント アルゴリズム

抄録

近似文字列照合問題は，二つの文字列と閾値が与えられて，片方の文字列の部分文字列のうち，もう一方の文字列との編集距離が閾値以下となるものを見つける問題である. この問題をビットパラレルと呼ばれる手法により高速に解くアルゴリズムがMyers により提案されているが，出力として編集距離だけではなくアライメントも求める場合には適用できない．本論文では，近似出現に対するアライメントについての正規形の概念を導入し，Myers のアルゴリズムを近似文字列照合に対するアライメント問題へ拡張する

収録刊行物

• 情報処理学会論文誌. 数理モデル化と応用

  情報処理学会論文誌. 数理モデル化と応用 46 (SIG17(TOM13)), 80-87, 2005-12-15

  Information Processing Society of Japan

キーワード

• オリジナル論文

詳細情報

• CRID: 1050017057728655744
• NII論文ID: 110002973638
• NII書誌ID: AA11464803
• ISSN: 18827780
• ISSN: 03875806
• HANDLE: 2324/16872
• NDL書誌ID: 7771189
• Web Site: http://id.nii.ac.jp/1001/00017189/
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I7771189
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles
  • KAKEN