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

Last change on this file since 867 was 867, checked in by Peter, 14 years ago

adding function doing a SSEARCH between two strings

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