Hirschberg’s algorithm とは

コンピュータサイエンスでは、Hirschbergのアルゴリズムは、発明者Dan Hirschbergにちなんで命名され、2つの文字列間の最適な配列アライメントを見つける動的プログラミングアルゴリズムです。最適性は、ある文字列を他の文字列に変更するために必要な挿入、置換、削除、およびnullアクションのコストの合計と定義されたLevenshtein距離で測定されます。 Hirschbergのアルゴリズムは、分割と征服を使用するNeedleman-Wunschアルゴリズムのより空間効率の良いバージョンとして簡単に説明されています。 Hirschbergのアルゴリズムは、DNAおよびタンパク質配列の最大のグローバルアラインメントを見出すために、計算上の生物学において一般に使用されている。