source: trunk/yat/utility/Alignment.cc @ 875

// $Id: Alignment.cc 875 2007-09-19 00:17:05Z peter $

/*
  Copyright (C) 2004 Jari Häkkinen
  Copyright (C) 2005 Peter Johansson
  Copyright (C) 2006 Jari Häkkinen

  This file is part of the yat library, http://trac.thep.lu.se/trac/yat

  The yat library is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 2 of the
  License, or (at your option) any later version.

  The yat library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  02111-1307, USA.
*/

#include "Alignment.h"
#include "matrix.h"
#include "yat/utility/stl_utility.h"

#include <algorithm>
#include <utility>
#include <vector>

namespace theplu {
namespace yat {
namespace utility {

  double NeedlemanWunsch(const utility::matrix& s,
                         std::vector<std::pair<size_t, size_t> >& path,
                         const double gap)
  {
    utility::matrix m(s.rows()+1,s.columns()+1);
    // Init upper and left border of matrix 
    for (size_t i=1; i<m.rows(); i++) 
      m(i,0)=-i*gap;
    for (size_t i=1; i<m.columns(); i++) 
      m(0,i)=-i*gap;
    // choice(i,j) tells us how we came to s(i,j). 1 is diagonal, 2
    // vertical, and 3 horizontal,
    utility::matrix choice(m.rows(),m.columns());

    // Calculating NeedlemanWunsch matrix
    for (size_t i=1; i<m.rows(); i++) 
      for (size_t j=1; j<m.columns(); j++){ 
        if (m(i-1,j-1) + s(i-1,j-1) > m(i-1,j)-gap && 
            m(i-1,j-1) + s(i-1,j-1) > m(i,j-1)-gap){
          m(i,j)=m(i-1,j-1) + s(i-1,j-1);
          choice(i,j)=1;
        }
        else if (m(i-1,j) > m(i,j-1)){
          m(i,j)=m(i-1,j)-gap;
          choice(i,j)=2;
        }
        else{
          m(i,j)=m(i,j-1)-gap;
          choice(i,j)=3;
        }
      }
    // Going backwards to find best path
    size_t i = m.rows()-1;
    size_t j= m.columns()-1;
    path.resize(0);
    while (i && j){
      if (choice(i,j)==1){
        i--;
        j--;
        path.push_back(std::make_pair(i,j));
      }
      else if (choice(i,j)==2)
        i--;
      else
        j--;
    }

    return m(m.rows()-1,m.columns()-1);
  }


  double ssearch(std::string first, std::string second, double gap, 
                 double open_gap)
  {
    matrix m(first.size(), second.size());
    for (size_t i=0; i<first.size(); ++i)
      for (size_t j=0; j<second.size(); ++j)
        m(i,j) = (first[i]==second[j] ? 1 : 0);
    return SmithWaterman(m, gap, open_gap);
  }


  double SmithWaterman(const utility::matrix& s,
                       double gap, double open_gap)
  {
    enum direction { none, right, down, diagonal };

    // Calculating S-W matrix
    matrix m(s.rows()+1,s.columns()+1);
    matrix array(m);
    for (size_t i=1; i<m.rows(); ++i) 
      for (size_t j=1; j<m.columns(); ++j){ 
        m(i,j)=0;
        array(i,j) = none;
        if (m(i-1,j-1)+s(i-1,j-1)>m(i,j)){
          m(i,j) = m(i-1,j-1)+s(i-1,j-1);
          array(i,j) = diagonal;
        }         
        if (array(i-1,j)==right && m(i-1,j)-gap > m(i,j)){
          m(i,j) = m(i-1,j)-gap;
          array(i,j) = right;
        }         
        if (array(i-1,j)!=right && m(i-1,j)-gap-open_gap > m(i,j)){
          m(i,j) = m(i-1,j)-gap-open_gap;
          array(i,j) = right;
        }         
        if (array(i,j-1)==down && m(i,j-1)-gap > m(i,j)){
          m(i,j) = m(i,j-1)-gap;
          array(i,j) = down;
        }         
        if (array(i,j-1)!=down && m(i,j-1)-gap-open_gap > m(i,j)){
          m(i,j) = m(i,j-1)-gap-open_gap;
          array(i,j) = down;
        }         
      }
    return max(m);
  }

}}} // of namespace utility, yat, and theplu