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

Last change on this file since 1797 was 1797, checked in by Peter, 13 years ago

updating copyright statements

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 3.6 KB
Line 
1// $Id: Alignment.cc 1797 2009-02-12 18:07:10Z peter $
2
3/*
4  Copyright (C) 2004 Jari Häkkinen
5  Copyright (C) 2005 Peter Johansson
6  Copyright (C) 2006 Jari Häkkinen
7  Copyright (C) 2007, 2008 Jari Häkkinen, Peter Johansson
8
9  This file is part of the yat library, http://dev.thep.lu.se/yat
10
11  The yat library is free software; you can redistribute it and/or
12  modify it under the terms of the GNU General Public License as
13  published by the Free Software Foundation; either version 3 of the
14  License, or (at your option) any later version.
15
16  The yat library is distributed in the hope that it will be useful,
17  but WITHOUT ANY WARRANTY; without even the implied warranty of
18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19  General Public License for more details.
20
21  You should have received a copy of the GNU General Public License
22  along with yat. If not, see <http://www.gnu.org/licenses/>.
23*/
24
25#include "Alignment.h"
26#include "Matrix.h"
27#include "stl_utility.h"
28
29#include <algorithm>
30#include <utility>
31#include <vector>
32
33namespace theplu {
34namespace yat {
35namespace utility {
36
37  double NeedlemanWunsch(const utility::Matrix& s,
38                         std::vector<std::pair<size_t, size_t> >& path,
39                         const double gap)
40  {
41    utility::Matrix m(s.rows()+1,s.columns()+1);
42    // Init upper and left border of matrix
43    for (size_t i=1; i<m.rows(); i++) 
44      m(i,0)=-i*gap;
45    for (size_t i=1; i<m.columns(); i++) 
46      m(0,i)=-i*gap;
47    // choice(i,j) tells us how we came to s(i,j). 1 is diagonal, 2
48    // vertical, and 3 horizontal,
49    utility::Matrix choice(m.rows(),m.columns());
50
51    // Calculating NeedlemanWunsch matrix
52    for (size_t i=1; i<m.rows(); i++) 
53      for (size_t j=1; j<m.columns(); j++){ 
54        if (m(i-1,j-1) + s(i-1,j-1) > m(i-1,j)-gap && 
55            m(i-1,j-1) + s(i-1,j-1) > m(i,j-1)-gap){
56          m(i,j)=m(i-1,j-1) + s(i-1,j-1);
57          choice(i,j)=1;
58        }
59        else if (m(i-1,j) > m(i,j-1)){
60          m(i,j)=m(i-1,j)-gap;
61          choice(i,j)=2;
62        }
63        else{
64          m(i,j)=m(i,j-1)-gap;
65          choice(i,j)=3;
66        }
67      }
68    // Going backwards to find best path
69    size_t i = m.rows()-1;
70    size_t j= m.columns()-1;
71    path.resize(0);
72    while (i && j){
73      if (choice(i,j)==1){
74        i--;
75        j--;
76        path.push_back(std::make_pair(i,j));
77      }
78      else if (choice(i,j)==2)
79        i--;
80      else
81        j--;
82    }
83
84    return m(m.rows()-1,m.columns()-1);
85  }
86
87
88  double ssearch(std::string first, std::string second, double gap, 
89                 double open_gap)
90  {
91    Matrix m(first.size(), second.size());
92    for (size_t i=0; i<first.size(); ++i)
93      for (size_t j=0; j<second.size(); ++j)
94        m(i,j) = (first[i]==second[j] ? 1 : 0);
95    return SmithWaterman(m, gap, open_gap);
96  }
97
98
99  double SmithWaterman(const utility::Matrix& s,
100                       double gap, double open_gap)
101  {
102    enum direction { none, right, down, diagonal };
103
104    // Calculating S-W matrix
105    Matrix m(s.rows()+1,s.columns()+1);
106    Matrix array(m);
107    for (size_t i=1; i<m.rows(); ++i) 
108      for (size_t j=1; j<m.columns(); ++j){ 
109        m(i,j)=0;
110        array(i,j) = none;
111        if (m(i-1,j-1)+s(i-1,j-1)>m(i,j)){
112          m(i,j) = m(i-1,j-1)+s(i-1,j-1);
113          array(i,j) = diagonal;
114        }         
115        if (array(i-1,j)==right && m(i-1,j)-gap > m(i,j)){
116          m(i,j) = m(i-1,j)-gap;
117          array(i,j) = right;
118        }         
119        if (array(i-1,j)!=right && m(i-1,j)-gap-open_gap > m(i,j)){
120          m(i,j) = m(i-1,j)-gap-open_gap;
121          array(i,j) = right;
122        }         
123        if (array(i,j-1)==down && m(i,j-1)-gap > m(i,j)){
124          m(i,j) = m(i,j-1)-gap;
125          array(i,j) = down;
126        }         
127        if (array(i,j-1)!=down && m(i,j-1)-gap-open_gap > m(i,j)){
128          m(i,j) = m(i,j-1)-gap-open_gap;
129          array(i,j) = down;
130        }         
131      }
132    return max(m);
133  }
134
135}}} // of namespace utility, yat, and theplu
Note: See TracBrowser for help on using the repository browser.