alignment系アルゴリズム

alignment系のアルゴリズムの実装ってどこかに落ちてにゃいかにゃ〜と探してみたけれど，見つからにゃいので自分で作るのにゃ．
Boost1.33.0で確認．VC7.1ではauto_linkを使っているのでライブラリをビルドしていてパスを適切に通していればリンク指定不要．GCCはauto_link対応していないので明示的にlibboost_unit_test_frameworkなんちゃらのリンクが必要．

#include <cstddef>
#include <vector>
#include <iterator>
#include <algorithm>
#include <functional>
#include <boost/range/value_type.hpp>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>

// 2つの配列間のalignmentのうち，最適なalignmentでの一致要素数を返す．
template<
  class SinglePassTraversalReadableIterator0
, class SinglePassTraversalReadableIterator1
, class BinaryPredicate
>
std::size_t alignment_score(
  SinglePassTraversalReadableIterator0 const &first0
, SinglePassTraversalReadableIterator0 const &last0
, SinglePassTraversalReadableIterator1 const &first1
, SinglePassTraversalReadableIterator1 const &last1
, BinaryPredicate pred
)
{
  std::vector<std::size_t> score_vector(std::distance(first0, last0) + 1, 0);

  for(SinglePassTraversalReadableIterator1 curr1(first1);
      curr1 != last1;
      ++curr1)
  {
    std::vector<std::size_t>::size_type index = 0;
    std::size_t old_score = 0;
    for(SinglePassTraversalReadableIterator0 curr0(first0);
        curr0 != last0;
        ++curr0, ++index)
    {
      if(pred(*curr0, *curr1)){
        std::size_t new_score = old_score + 1;
        old_score = score_vector[index + 1];
        score_vector[index + 1] = new_score;
      }
      else{
        std::size_t new_score = std::max(
            score_vector[index], score_vector[index + 1]
          );
        old_score = score_vector[index + 1];
        score_vector[index + 1] = new_score;
      }
    }
  }

  return score_vector.back();
}

template<
  class SinglePassRange0, class SinglePassRange1, class BinaryPredicate
>
std::size_t alignment_score(
  SinglePassRange0 const &r0, SinglePassRange1 const &r1, BinaryPredicate pred
)
{
  return alignment_score(
      boost::begin(r0), boost::end(r0)
    , boost::begin(r1), boost::end(r1)
    , pred
    );
}

template<class SinglePassRange0, class SinglePassRange1>
std::size_t alignment_score(
  SinglePassRange0 const &r0, SinglePassRange1 const &r1
)
{
  return alignment_score(
      boost::begin(r0), boost::end(r0)
    , boost::begin(r1), boost::end(r1)
    , std::equal_to<typename boost::range_value<SinglePassRange0>::type>()
    );
}



// 以上ライブラリコード
// 以下テストコード



#define BOOST_AUTO_TEST_MAIN
#include <boost/test/auto_unit_test.hpp>

#if !defined(BOOST_ALL_NO_LIB)
#define BOOST_LIB_NAME boost_unit_test_framework
#include <boost/config/auto_link.hpp>
#endif


BOOST_AUTO_UNIT_TEST(alignment_score_test)
{
  BOOST_CHECK(alignment_score("GAATTCAGTTA", "GGATCGA") == 6);
  // 最適なalignment（のうちの1つ）は以下で一致要素数6
  //
  // -GAATTCAGTTA
  //  || | | |  |
  // GGA-T-C-G--A
}

dynamic programmingと言えばまずこのアルゴリズムが例として出てくるぐらいのDPの大御所ですにゃ．