1 // ==========================================================================
2 // SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2015, Knut Reinert, FU Berlin
5 // All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions are met:
9 //
10 // * Redistributions of source code must retain the above copyright
11 // notice, this list of conditions and the following disclaimer.
12 // * Redistributions in binary form must reproduce the above copyright
13 // notice, this list of conditions and the following disclaimer in the
14 // documentation and/or other materials provided with the distribution.
15 // * Neither the name of Knut Reinert or the FU Berlin nor the names of
16 // its contributors may be used to endorse or promote products derived
17 // from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
29 // DAMAGE.
30 //
31 // ==========================================================================
32 // Author: Rene Rahn <rene.rahn@fu-berlin.de>
33 // ==========================================================================
34 // Defines the recursion formula for the dp-alignment algorithms.
35 // ==========================================================================
36
37 // TODO(holtgrew): Documentation in this header necessary or internal only?
38
39 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_FORMULA_H_
40 #define SEQAN_INCLUDE_SEQAN_ALIGN_DP_FORMULA_H_
41
42 namespace seqan {
43
44 // ============================================================================
45 // Forwards
46 // ============================================================================
47
48 // ============================================================================
49 // Tags, Classes, Enums
50 // ============================================================================
51
52 // ----------------------------------------------------------------------------
53 // Tag RecursionDirectionDiagonal
54 // ----------------------------------------------------------------------------
55
56 struct RecursionDirectionDiagonal_;
57 typedef Tag<RecursionDirectionDiagonal_> RecursionDirectionDiagonal;
58
59 // ----------------------------------------------------------------------------
60 // Tag RecursionDirectionHorizontal
61 // ----------------------------------------------------------------------------
62
63 struct RecursionDirectionHorizontal_;
64 typedef Tag<RecursionDirectionHorizontal_> RecursionDirectionHorizontal;
65
66 // ----------------------------------------------------------------------------
67 // Tag RecursionDirectionVertical
68 // ----------------------------------------------------------------------------
69
70 struct RecursionDirectionVertical_;
71 typedef Tag<RecursionDirectionVertical_> RecursionDirectionVertical;
72
73 // ----------------------------------------------------------------------------
74 // Tag RecursionDirectionAll
75 // ----------------------------------------------------------------------------
76
77 struct RecursionDirectionAll_;
78 typedef Tag<RecursionDirectionAll_> RecursionDirectionAll;
79
80 // ----------------------------------------------------------------------------
81 // Tag RecursionDirectionUpperDiagonal
82 // ----------------------------------------------------------------------------
83
84 struct RecursionDirectionUpperDiagonal_;
85 typedef Tag<RecursionDirectionUpperDiagonal_> RecursionDirectionUpperDiagonal;
86
87 // ----------------------------------------------------------------------------
88 // Tag RecursionDirectionLowerDiagonal
89 // ----------------------------------------------------------------------------
90
91 struct RecursionDirectionLowerDiagonal_;
92 typedef Tag<RecursionDirectionLowerDiagonal_> RecursionDirectionLowerDiagonal;
93
94 // ----------------------------------------------------------------------------
95 // Tag RecursionDirectionZero
96 // ----------------------------------------------------------------------------
97
98 struct RecursionDirectionZero_;
99 typedef Tag<RecursionDirectionZero_> RecursionDirectionZero;
100
101 // ============================================================================
102 // Metafunctions
103 // ============================================================================
104
105 // ============================================================================
106 // Functions
107 // ============================================================================
108
109 // ----------------------------------------------------------------------------
110 // Function _conditionalOrOnEquality()
111 // ----------------------------------------------------------------------------
112
113 // Function used to compare two trace values and to add a given state to the result
114 // value if they are equal using a bit-or operation.
115 template <typename TTraceValue, typename TScoreValue>
116 inline void
_conditionalOrOnEquality(TTraceValue & target,TScoreValue const & leftComp,TScoreValue const & rightComp,TTraceValue state)117 _conditionalOrOnEquality(TTraceValue & target,
118 TScoreValue const & leftComp,
119 TScoreValue const & rightComp,
120 TTraceValue state)
121 {
122 if (leftComp == rightComp)
123 target |= state;
124 }
125
126 // ----------------------------------------------------------------------------
127 // Function _conditionalOrOnInequality()
128 // ----------------------------------------------------------------------------
129
130 // Function used to compare two trace values and to add a given state to the result
131 // value if they are equal using a bit-or operation.
132 template <typename TTraceValue, typename TScoreValue>
133 inline void
_conditionalOrOnInequality(TTraceValue & target,TScoreValue const & leftComp,TScoreValue const & rightComp,TTraceValue state)134 _conditionalOrOnInequality(TTraceValue & target,
135 TScoreValue const & leftComp,
136 TScoreValue const & rightComp,
137 TTraceValue state)
138 {
139 if (leftComp != rightComp)
140 target |= state;
141 }
142
143 // ----------------------------------------------------------------------------
144 // Function _computeScore
145 // ----------------------------------------------------------------------------
146
147 template <typename TScoreValue, typename TGapCosts, typename TSequenceHValue, typename TSequenceVValue,
148 typename TScoringScheme, typename TRecursionDirection, typename TDPProfile>
149 inline typename TraceBitMap_::TTraceValue
_computeScore(DPCell_<TScoreValue,TGapCosts> & activeCell,DPCell_<TScoreValue,TGapCosts> const & previousDiagonal,DPCell_<TScoreValue,TGapCosts> const & previousHorizontal,DPCell_<TScoreValue,TGapCosts> const & previousVertical,TSequenceHValue const & seqHVal,TSequenceVValue const & seqVVal,TScoringScheme const & scoringScheme,TRecursionDirection const & recDir,TDPProfile const & dpProfile)150 _computeScore(DPCell_<TScoreValue, TGapCosts> & activeCell,
151 DPCell_<TScoreValue, TGapCosts> const & previousDiagonal,
152 DPCell_<TScoreValue, TGapCosts> const & previousHorizontal,
153 DPCell_<TScoreValue, TGapCosts> const & previousVertical,
154 TSequenceHValue const & seqHVal,
155 TSequenceVValue const & seqVVal,
156 TScoringScheme const & scoringScheme,
157 TRecursionDirection const & recDir,
158 TDPProfile const & dpProfile)
159 {
160 typedef typename TraceBitMap_::TTraceValue TTraceValue;
161
162 TTraceValue traceDir = _doComputeScore(activeCell, previousDiagonal, previousHorizontal, previousVertical, seqHVal,
163 seqVVal, scoringScheme, recDir, dpProfile);
164 if (IsLocalAlignment_<TDPProfile>::VALUE)
165 if (activeCell._score <= 0)
166 {
167 _setScoreOfCell(activeCell, static_cast<TScoreValue>(0));
168 _setHorizontalScoreOfCell(activeCell, static_cast<TScoreValue>(0));
169 _setVerticalScoreOfCell(activeCell, static_cast<TScoreValue>(0));
170 return TraceBitMap_::NONE;
171 }
172
173 return traceDir;
174 }
175
176 // ----------------------------------------------------------------------------
177 // Function _doComputeScore [RecursionDirectionDiagonal]
178 // ----------------------------------------------------------------------------
179
180 template <typename TScoreValue, typename TGapCosts, typename TSequenceHValue, typename TSequenceVValue, typename TScoringScheme,
181 typename TDPProfile>
182 inline typename TraceBitMap_::TTraceValue
_doComputeScore(DPCell_<TScoreValue,TGapCosts> & activeCell,DPCell_<TScoreValue,TGapCosts> const & previousDiagonal,DPCell_<TScoreValue,TGapCosts> const &,DPCell_<TScoreValue,TGapCosts> const &,TSequenceHValue const & seqHVal,TSequenceVValue const & seqVVal,TScoringScheme const & scoringScheme,RecursionDirectionDiagonal const &,TDPProfile const &)183 _doComputeScore(DPCell_<TScoreValue, TGapCosts> & activeCell,
184 DPCell_<TScoreValue, TGapCosts> const & previousDiagonal,
185 DPCell_<TScoreValue, TGapCosts> const & /*previousHorizontal*/,
186 DPCell_<TScoreValue, TGapCosts> const & /*previousVertical*/,
187 TSequenceHValue const & seqHVal,
188 TSequenceVValue const & seqVVal,
189 TScoringScheme const & scoringScheme,
190 RecursionDirectionDiagonal const &,
191 TDPProfile const &)
192 {
193 activeCell._score = _scoreOfCell(previousDiagonal) + score(scoringScheme, seqHVal, seqVVal);
194 setGapExtension(activeCell, False(), False());
195 if (!IsTracebackEnabled_<TDPProfile>::VALUE)
196 return TraceBitMap_::NONE;
197
198 return TraceBitMap_::DIAGONAL;
199 }
200
201 // ----------------------------------------------------------------------------
202 // Function _doComputeScore [RecursionDirectionZero]
203 // ----------------------------------------------------------------------------
204
205 template <typename TScoreValue, typename TGapCosts, typename TSequenceHValue, typename TSequenceVValue, typename TScoringScheme,
206 typename TAlgoTag, typename TTraceFlag>
207 inline typename TraceBitMap_::TTraceValue
_doComputeScore(DPCell_<TScoreValue,TGapCosts> & activeCell,DPCell_<TScoreValue,TGapCosts> const &,DPCell_<TScoreValue,TGapCosts> const &,DPCell_<TScoreValue,TGapCosts> const &,TSequenceHValue const &,TSequenceVValue const &,TScoringScheme const &,RecursionDirectionZero const &,DPProfile_<TAlgoTag,TGapCosts,TTraceFlag> const &)208 _doComputeScore(DPCell_<TScoreValue, TGapCosts> & activeCell,
209 DPCell_<TScoreValue, TGapCosts> const & /*previousDiagonal*/,
210 DPCell_<TScoreValue, TGapCosts> const & /*previousHorizontal*/,
211 DPCell_<TScoreValue, TGapCosts> const & /*previousVertical*/,
212 TSequenceHValue const & /*seqHVal*/,
213 TSequenceVValue const & /*seqVVal*/,
214 TScoringScheme const & /*scoringScheme*/,
215 RecursionDirectionZero const &,
216 DPProfile_<TAlgoTag, TGapCosts, TTraceFlag> const &)
217 {
218 _scoreOfCell(activeCell) = 0;
219 return TraceBitMap_::NONE;
220 }
221
222 } // namespace seqan
223
224 #endif // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_FORMULA_H_
225