source: trunk/yat/utility/Aligner.h @ 2986

Last change on this file since 2986 was 2986, checked in by Peter, 9 years ago

merge 0.10-stable branch into trunk

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 3.8 KB
Line 
1#ifndef _theplu_yat_utility_aligner_
2#define _theplu_yat_utility_aligner_
3
4// $Id: Aligner.h 2986 2013-02-18 08:07:44Z peter $
5
6/*
7  Copyright (C) 2012 Peter Johansson
8  Copyright (C) 2013 Jari Häkkinen
9
10  This file is part of the yat library, http://dev.thep.lu.se/yat
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
14  published by the Free Software Foundation; either version 3 of the
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 yat. If not, see <http://www.gnu.org/licenses/>.
24*/
25
26#include <cstddef>
27#include <vector>
28
29namespace theplu {
30namespace yat {
31namespace utility {
32
33  class Matrix;
34
35  /**
36     \brief Aligning two sequences
37
38     General class aligning two sequences described in a dot-matrix,
39     D, in which \f$ D(i,j) \f$ describes how similar element \c i in
40     the first sequence is with element \c j in the second sequence. A
41     path through this matrix corresponds to an alignment of the two
42     sequences, in which a diagonal step correspoinds to a match
43     between corresponding sequence elements, and a vertical or
44     horizontal step correspond correspond to inserting a gap into one
45     of the sequences.
46
47     \since New in yat 0.9
48   */
49  class Aligner
50  {
51  public:
52    /**
53       Enum used to describe alignment.
54
55       \see alignment
56     */
57    enum direction { none, right, down, diagonal };
58
59    /**
60       \brief Constructor
61
62       Same as Aligner(gap, open_gap, gap, open_gap)
63     */
64    Aligner(double gap=0, double open_gap=0);
65
66    /**
67       \brief constructor
68
69       \param vertical_gap Penalty for extending a vertical gap
70
71       \param open_vertical_gap Penalty for open a vertical gap. Total
72       cost for a vertical gap is open_vertical_gap + N *
73       vertical_gap.
74
75       \param horizon_gap Penalty for extending a horizontal gap
76
77       \param open_horizon_gap Penalty for open a horizontal
78       gap. Total penalty for a horizontal gap is open_horizon_gap + N
79       * horizon_gap.
80     */
81    Aligner(double vertical_gap, double open_vertical_gap,
82            double horizon_gap, double open_horizon_gap);
83
84    /**
85       Initialize a score matrix with \f$ S_{k,0} = -
86       \textrm{open\_vertical\_gap} - k * \textrm{vertical\_gap} \f$
87       and \f$ S_{0,k} = - \textrm{open\_horizon\_gap} - k *
88       \textrm{horizon\_gap} \f$ and align using operator().
89
90       \return most lower right element of score matrix
91     */
92    double needleman_wunsch(const Matrix& d);
93
94    /**
95       Initialize a score matrix with all elements equal to zero,
96       align using operator().
97
98       \return max element in score matrix.
99     */
100    double smith_waterman(const Matrix& d);
101
102    /**
103       \brief calculate score matrix based on the \a dot matrix
104
105       The algorithm calculates a maximum \a score matrix as
106
107       \f$ S_{i,j} = \textrm{max} \{ S_{ij}; S_{i,j-1} - F(\textrm{gap}_V);
108       S_{i-1,j-1} + D_{i-1,j-1}; S_{i-1,j} - F(\textrm{gap}_H) \} \f$
109
110       where \f$ F(\textrm{gap}) \f$ is gap if there was already a
111       gap, and gap + open_gap otherwise.
112
113     */
114    void operator()(const Matrix& dot, Matrix& score);
115
116    /**
117       \brief access cigar element i, j
118
119       If, for example, cigar(i,j) returned Aligner::diagonal, implies
120       that score(i,j) was maximized as score(i-1,j-1) + dot(i-1,
121       j-1), which in turn implies that element i-1 in first sequence
122       was aligned with element j-1 in second sequence.
123    */
124    const direction& alignment(size_t i, size_t j) const;
125
126  private:
127    direction& cigar(size_t i, size_t j);
128
129    size_t columns_;
130    double vertical_gap_;
131    double open_vertical_gap_;
132    double horizon_gap_;
133    double open_horizon_gap_;
134    std::vector<direction> alignment_;
135  };
136
137}}} // of namespace utility, yat, and theplu
138
139#endif
Note: See TracBrowser for help on using the repository browser.