source: trunk/yat/utility/Alignment.h

Last change on this file was 4207, checked in by Peter, 4 weeks ago

update copyright statements

  • 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 4207 2022-08-26 04:36:28Z 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, 2022 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  class MatrixBase;
41
42  ///
43  /// Function performing alignment following the Needleman-Wunch
44  /// algorithm. The algorithm starts from the dot-matrix, \a s, where
45  /// \f$ s_{ij} \f$ describes how well element \f$ i \f$ in the first
46  /// sequence match to element \f$ j \f$ in the second sequence. A
47  /// path through this matrix corresponds to an alignment of the two
48  /// sequences, in which a diagonal step over a matrix element
49  /// corresponds to a match between the corresponding sequnce
50  /// elements and a vertical or a horizontal step corresponds to
51  /// inserting a gap in one of the sequnces. The function maximizes
52  /// \f$ \sum s_{ij}-n \f$ \a gap, where the first sum goes over all
53  /// matches and the second term is a penalty term for inserting
54  /// \f$ n \f$ gaps. Default is to have the \a gap cost set to zero. The
55  /// vector \a path contains information about which elements that
56  /// were matched. If the first element in the first sequence was
57  /// matched to the first element in the second sequence, the last
58  /// element in \a path is pair(0,0).
59  ///
60  /// @return the global maximum alignment score.
61  ///
62  /// \see Aligner
63  ///
64  double NeedlemanWunsch(const MatrixBase& s,
65                         std::vector<std::pair<size_t, size_t> >& path,
66                         const double gap);
67
68  /**
69     \brief Local alignment following the Smith-Waterman
70     algorithm.
71
72     Instead of looking at each sequence in its entirety the S-W algorithm
73     compares segment of all possible lengths (LOCAL alignment) and chooses
74     whichever maximises the similarity measure.
75
76     \return the similarity score that maximizes \f$ \sum_{i,j}
77     A_{ij}s_{ij} - L*gap - N*open\textunderscore gap\f$, where \f$
78     A_{ij} \f$ is unity if element \a i in first sequence is aligned
79     against element \a j in second sequence (zero otherwise); \a L is total
80     length of gaps; and \a N is number of gaps.
81
82     \param s score matrix in which element \f$(i,j)\f$ is the score between
83     element \f$i\f$ in first sequence and element \f$j\f$ in second sequence.
84     \param gap cost for having a gap (insertion or deletion)
85     \param open_gap cost for open up a gap in sequence, in other words, for a
86     gap of length L the total cost is open_gap + L*gap.
87
88     \deprecated Provided for backward compatibility with 0.8 API. Use
89     Aligner::smith_waterman() instead.
90   */
91  double SmithWaterman(const utility::Matrix& s,
92                       double gap, double open_gap) YAT_DEPRECATE;
93
94  /**
95     SSearch does a rigorous Smith-Waterman search for similarity between
96     sequences. For long sequences this may be very expensive (both in time and
97     space) and BLAST or FASTA is preferable.
98
99     Function calculates a score matrix with elements \f$ s_{ij} \f$
100     equal 1.0 when first[i] == second[j] and minus \a mismatch
101     otherwise.
102
103     @return SmithWaterman score
104
105     \since parameter mismatch available since yat 0.9
106
107     \see Aligner
108   */
109  double ssearch(std::string first, std::string second, double gap,
110                 double open_gap, double mismatch=0.0);
111
112}}} // of namespace utility, yat, and theplu
113
114#endif
Note: See TracBrowser for help on using the repository browser.