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

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

trac moved to new location.

  • 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 1000 2007-12-23 20:09:15Z jari $
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/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#include "yat/utility/stl_utility.h"
29
30#include <algorithm>
31#include <utility>
32#include <vector>
33
34namespace theplu {
35namespace yat {
36namespace utility {
37
38  double NeedlemanWunsch(const utility::matrix& s,
39                         std::vector<std::pair<size_t, size_t> >& path,
40                         const double gap)
41  {
42    utility::matrix m(s.rows()+1,s.columns()+1);
43    // Init upper and left border of matrix
44    for (size_t i=1; i<m.rows(); i++) 
45      m(i,0)=-i*gap;
46    for (size_t i=1; i<m.columns(); i++) 
47      m(0,i)=-i*gap;
48    // choice(i,j) tells us how we came to s(i,j). 1 is diagonal, 2
49    // vertical, and 3 horizontal,
50    utility::matrix choice(m.rows(),m.columns());
51
52    // Calculating NeedlemanWunsch matrix
53    for (size_t i=1; i<m.rows(); i++) 
54      for (size_t j=1; j<m.columns(); j++){ 
55        if (m(i-1,j-1) + s(i-1,j-1) > m(i-1,j)-gap && 
56            m(i-1,j-1) + s(i-1,j-1) > m(i,j-1)-gap){
57          m(i,j)=m(i-1,j-1) + s(i-1,j-1);
58          choice(i,j)=1;
59        }
60        else if (m(i-1,j) > m(i,j-1)){
61          m(i,j)=m(i-1,j)-gap;
62          choice(i,j)=2;
63        }
64        else{
65          m(i,j)=m(i,j-1)-gap;
66          choice(i,j)=3;
67        }
68      }
69    // Going backwards to find best path
70    size_t i = m.rows()-1;
71    size_t j= m.columns()-1;
72    path.resize(0);
73    while (i && j){
74      if (choice(i,j)==1){
75        i--;
76        j--;
77        path.push_back(std::make_pair(i,j));
78      }
79      else if (choice(i,j)==2)
80        i--;
81      else
82        j--;
83    }
84
85    return m(m.rows()-1,m.columns()-1);
86  }
87
88
89  double ssearch(std::string first, std::string second, double gap, 
90                 double open_gap)
91  {
92    matrix m(first.size(), second.size());
93    for (size_t i=0; i<first.size(); ++i)
94      for (size_t j=0; j<second.size(); ++j)
95        m(i,j) = (first[i]==second[j] ? 1 : 0);
96    return SmithWaterman(m, gap, open_gap);
97  }
98
99
100  double SmithWaterman(const utility::matrix& s,
101                       double gap, double open_gap)
102  {
103    enum direction { none, right, down, diagonal };
104
105    // Calculating S-W matrix
106    matrix m(s.rows()+1,s.columns()+1);
107    matrix array(m);
108    for (size_t i=1; i<m.rows(); ++i) 
109      for (size_t j=1; j<m.columns(); ++j){ 
110        m(i,j)=0;
111        array(i,j) = none;
112        if (m(i-1,j-1)+s(i-1,j-1)>m(i,j)){
113          m(i,j) = m(i-1,j-1)+s(i-1,j-1);
114          array(i,j) = diagonal;
115        }         
116        if (array(i-1,j)==right && m(i-1,j)-gap > m(i,j)){
117          m(i,j) = m(i-1,j)-gap;
118          array(i,j) = right;
119        }         
120        if (array(i-1,j)!=right && m(i-1,j)-gap-open_gap > m(i,j)){
121          m(i,j) = m(i-1,j)-gap-open_gap;
122          array(i,j) = right;
123        }         
124        if (array(i,j-1)==down && m(i,j-1)-gap > m(i,j)){
125          m(i,j) = m(i,j-1)-gap;
126          array(i,j) = down;
127        }         
128        if (array(i,j-1)!=down && m(i,j-1)-gap-open_gap > m(i,j)){
129          m(i,j) = m(i,j-1)-gap-open_gap;
130          array(i,j) = down;
131        }         
132      }
133    return max(m);
134  }
135
136}}} // of namespace utility, yat, and theplu
Note: See TracBrowser for help on using the repository browser.