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

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

Addresses #436.

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