ビットパラレル手法によるアライメントアルゴリズム  [in Japanese] An Alignment Algorithm by Bit-Parallelism  [in Japanese]

Search this Article

Author(s)

Abstract

近似文字列照合問題は, 二つの文字列と閾値が与えられて, 片方の文字列の任意の部分文字列に対してもう一方の文字列との編集距離を計算し, 与えられた閾値以下となるものを見つける問題である.Myersは, ビットパラレル手法により, 近似文字列照合問題を高速に解くアルゴリズムを提案した.しかし, 出力として編集距離ではなくアライメントを求める場合, 単純な方法を適用できず, 高速化が効果的でない場合がある.本論文では, 近似文字列照合問題に対するアライメントを, ビットパラレル手法によって求めるアルゴリズムを提案する.

Approximate matching problem is, given two strings and a parameter, to find all substring of a string whose edit distance with the other string is at most the parameter. Myers introduced an efficient algorithm for approximate matching problem based on bit-parallelism. However, if we need alignment as the answer of the problem, the straightforward method can't be applied. In this paper, an alignment algorithm based on bit-parallelism for approximate matching problem is presented.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 53, 37-40, 2005-03-09

    Information Processing Society of Japan (IPSJ)

References:  5

Codes

  • NII Article ID (NAID)
    110002950934
  • NII NACSIS-CAT ID (NCID)
    AN10505667
  • Text Lang
    JPN
  • Article Type
    ART
  • ISSN
    09196072
  • NDL Article ID
    7319099
  • NDL Source Classification
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL Call No.
    Z14-1121
  • Data Source
    CJP  NDL  NII-ELS 
Page Top