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

Last change on this file since 680 was 680, checked in by Jari Häkkinen, 15 years ago

Addresses #153. Introduced yat namespace. Removed alignment namespace. Clean up of code.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 2.2 KB
Line 
1// $Id: Alignment.cc 680 2006-10-11 17:49:03Z jari $
2
3/*
4  Copyright (C) The authors contributing to this file.
5
6  This file is part of the yat library, http://lev.thep.lu.se/trac/yat
7
8  The yat library is free software; you can redistribute it and/or
9  modify it under the terms of the GNU General Public License as
10  published by the Free Software Foundation; either version 2 of the
11  License, or (at your option) any later version.
12
13  The yat library is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  General Public License for more details.
17
18  You should have received a copy of the GNU General Public License
19  along with this program; if not, write to the Free Software
20  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
21  02111-1307, USA.
22*/
23
24#include "Alignment.h"
25#include "matrix.h"
26
27#include <utility>
28#include <vector>
29
30namespace theplu {
31namespace yat {
32namespace utility {
33
34  double NeedlemanWunsch(const utility::matrix& s,
35                         std::vector<std::pair<size_t, size_t> >& path,
36                         const double gap)
37  {
38    utility::matrix m(s.rows()+1,s.columns()+1);
39    // Init upper and left border of matrix
40    for (size_t i=1; i<m.rows(); i++) 
41      m(i,0)=-i*gap;
42    for (size_t i=1; i<m.columns(); i++) 
43      m(0,i)=-i*gap;
44    // choice(i,j) tells us how we came to s(i,j). 1 is diagonal, 2
45    // vertical, and 3 horizontal,
46    utility::matrix choice(m.rows(),m.columns());
47
48    // Calculating NeedlemanWunsch matrix
49    for (size_t i=1; i<m.rows(); i++) 
50      for (size_t j=1; j<m.columns(); j++){ 
51        if (m(i-1,j-1) + s(i-1,j-1) > m(i-1,j)-gap && 
52            m(i-1,j-1) + s(i-1,j-1) > m(i,j-1)-gap){
53          m(i,j)=m(i-1,j-1) + s(i-1,j-1);
54          choice(i,j)=1;
55        }
56        else if (m(i-1,j) > m(i,j-1)){
57          m(i,j)=m(i-1,j)-gap;
58          choice(i,j)=2;
59        }
60        else{
61          m(i,j)=m(i,j-1)-gap;
62          choice(i,j)=3;
63        }
64      }
65    // Going backwards to find best path
66    size_t i = m.rows()-1;
67    size_t j= m.columns()-1;
68    path.resize(0);
69    while (i && j){
70      if (choice(i,j)==1){
71        i--;
72        j--;
73        path.push_back(std::make_pair(i,j));
74      }
75      else if (choice(i,j)==2)
76        i--;
77      else
78        j--;
79    }
80
81    return m(m.rows()-1,m.columns()-1);
82  }
83
84}}} // of namespace utility, yat and theplu
Note: See TracBrowser for help on using the repository browser.