source: trunk/yat/utility/Alignment.h

Last change on this file was 3210, checked in by Peter, 7 years ago

update copyright years

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 4.1 KB
Line 
1#ifndef _theplu_yat_utility_alignment_
2#define _theplu_yat_utility_alignment_
3
4// $Id: Alignment.h 3210 2014-05-05 06:10:02Z peter $
5
6/*
7  Copyright (C) 2004 Jari Häkkinen, Peter Johansson
8  Copyright (C) 2005 Peter Johansson
9  Copyright (C) 2006 Jari Häkkinen
10  Copyright (C) 2007, 2008 Jari Häkkinen, Peter Johansson
11  Copyright (C) 2012, 2014 Peter Johansson
12
13  This file is part of the yat library, http://dev.thep.lu.se/yat
14
15  The yat library is free software; you can redistribute it and/or
16  modify it under the terms of the GNU General Public License as
17  published by the Free Software Foundation; either version 3 of the
18  License, or (at your option) any later version.
19
20  The yat library is distributed in the hope that it will be useful,
21  but WITHOUT ANY WARRANTY; without even the implied warranty of
22  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
23  General Public License for more details.
24
25  You should have received a copy of the GNU General Public License
26  along with yat. If not, see <http://www.gnu.org/licenses/>.
27*/
28
29#include "deprecate.h"
30
31#include <string>
32#include <utility>
33#include <vector>
34
35namespace theplu {
36namespace yat {
37namespace utility {
38
39  class Matrix;
40
41  ///
42  /// Function performing alignment following the Needleman-Wunch
43  /// algorithm. The algorithm starts from the dot-matrix, \a s, where
44  /// \f$ s_{ij} \f$ describes how well element \f$ i \f$ in the first
45  /// sequence match to element \f$ j \f$ in the second sequence. A
46  /// path through this matrix corresponds to an alignment of the two
47  /// sequences, in which a diagonal step over a matrix element
48  /// corresponds to a match between the corresponding sequnce
49  /// elements and a vertical or a horizontal step corresponds to
50  /// inserting a gap in one of the sequnces. The function maximizes
51  /// \f$ \sum s_{ij}-n \f$ \a gap, where the first sum goes over all
52  /// matches and the second term is a penalty term for inserting
53  /// \f$ n \f$ gaps. Default is to have the \a gap cost set to zero. The
54  /// vector \a path contains information about which elements that
55  /// were matched. If the first element in the first sequence was
56  /// matched to the first element in the second sequence, the last
57  /// element in \a path is pair(0,0).
58  ///
59  /// @return the global maximum alignment score.
60  ///
61  /// \see Aligner
62  ///
63  double NeedlemanWunsch(const utility::Matrix& s,
64                         std::vector<std::pair<size_t, size_t> >& path,
65                         const double gap);
66
67  /**
68     \brief Local alignment following the Smith-Waterman
69     algorithm.
70
71     Instead of looking at each sequence in its entirety the S-W algorithm
72     compares segment of all possible lengths (LOCAL alignment) and chooses
73     whichever maximises the similarity measure.
74
75     \return the similarity score that maximizes \f$ \sum_{i,j}
76     A_{ij}s_{ij} - L*gap - N*open\textunderscore gap\f$, where \f$
77     A_{ij} \f$ is unity if element \a i in first sequence is aligned
78     against element \a j in second sequence (zero otherwise); \a L is total
79     length of gaps; and \a N is number of gaps.
80
81     \param s score matrix in which element \f$(i,j)\f$ is the score between
82     element \f$i\f$ in first sequence and element \f$j\f$ in second sequence.
83     \param gap cost for having a gap (insertion or deletion)
84     \param open_gap cost for open up a gap in sequence, in other words, for a
85     gap of length L the total cost is open_gap + L*gap.
86
87     \deprecated Provided for backward compatibility with 0.8 API. Use
88     Aligner::smith_waterman() instead.
89   */
90  double SmithWaterman(const utility::Matrix& s,
91                       double gap, double open_gap) YAT_DEPRECATE;
92
93  /**
94     SSearch does a rigorous Smith-Waterman search for similarity between
95     sequences. For long sequences this may be very expensive (both in time and
96     space) and BLAST or FASTA is preferable.
97
98     Function calculates a score matrix with elements \f$ s_{ij} \f$
99     equal 1.0 when first[i] == second[j] and minus \a mismatch
100     otherwise.
101
102     @return SmithWaterman score
103
104     \since parameter mismatch available since yat 0.9
105
106     \see Aligner
107   */
108  double ssearch(std::string first, std::string second, double gap,
109                 double open_gap, double mismatch=0.0);
110
111}}} // of namespace utility, yat, and theplu
112
113#endif
Note: See TracBrowser for help on using the repository browser.