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 methods to compute the score when using linear gap costs.
35 // ==========================================================================
36
37 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_FORMULA_LINEAR_H_
38 #define SEQAN_INCLUDE_SEQAN_ALIGN_DP_FORMULA_LINEAR_H_
39
40 namespace seqan {
41
42 // ============================================================================
43 // Forwards
44 // ============================================================================
45
46 // ============================================================================
47 // Tags, Classes, Enums
48 // ============================================================================
49
50 // ============================================================================
51 // Metafunctions
52 // ============================================================================
53
54 // ============================================================================
55 // Functions
56 // ============================================================================
57
58 // ----------------------------------------------------------------------------
59 // Function _computeTraceLinear [RecursionDirectionAll]
60 // ----------------------------------------------------------------------------
61
62 template <typename TScoreValue>
63 inline TraceBitMap_::TTraceValue
_computeTraceLinear(TScoreValue const & globalMax,TScoreValue const & diagScore,TScoreValue const & horiScore,TScoreValue const & vertiScore,RecursionDirectionAll const &)64 _computeTraceLinear(TScoreValue const & globalMax,
65 TScoreValue const & diagScore,
66 TScoreValue const & horiScore,
67 TScoreValue const & vertiScore,
68 RecursionDirectionAll const &)
69 {
70 typename TraceBitMap_::TTraceValue traceValue(TraceBitMap_::NONE);
71
72 _conditionalOrOnEquality(traceValue, globalMax, diagScore, TraceBitMap_::DIAGONAL);
73 _conditionalOrOnEquality(traceValue, globalMax, horiScore, TraceBitMap_::HORIZONTAL);
74 _conditionalOrOnEquality(traceValue, globalMax, vertiScore, TraceBitMap_::VERTICAL);
75 return traceValue;
76 }
77
78 // ----------------------------------------------------------------------------
79 // Function _computeTraceLinear [RecursionDirectionUpperDiagonal]
80 // ----------------------------------------------------------------------------
81
82 template <typename TScoreValue>
83 inline TraceBitMap_::TTraceValue
_computeTraceLinear(TScoreValue const & globalMax,TScoreValue const & diagScore,TScoreValue const & horiScore,TScoreValue const &,RecursionDirectionUpperDiagonal const &)84 _computeTraceLinear(TScoreValue const & globalMax,
85 TScoreValue const & diagScore,
86 TScoreValue const & horiScore,
87 TScoreValue const &,
88 RecursionDirectionUpperDiagonal const &)
89 {
90 typename TraceBitMap_::TTraceValue traceValue(TraceBitMap_::NONE);
91
92 _conditionalOrOnEquality(traceValue, globalMax, diagScore, TraceBitMap_::DIAGONAL);
93 _conditionalOrOnEquality(traceValue, globalMax, horiScore, TraceBitMap_::HORIZONTAL);
94 return traceValue;
95 }
96
97 // ----------------------------------------------------------------------------
98 // Function _computeTraceLinear [RecursionDirectionLowerDiagonal]
99 // ----------------------------------------------------------------------------
100
101 template <typename TScoreValue>
102 inline TraceBitMap_::TTraceValue
_computeTraceLinear(TScoreValue const & globalMax,TScoreValue const & diagScore,TScoreValue const &,TScoreValue const & vertiScore,RecursionDirectionLowerDiagonal const &)103 _computeTraceLinear(TScoreValue const & globalMax,
104 TScoreValue const & diagScore,
105 TScoreValue const &,
106 TScoreValue const & vertiScore,
107 RecursionDirectionLowerDiagonal const &)
108 {
109 typename TraceBitMap_::TTraceValue traceValue(TraceBitMap_::NONE);
110 _conditionalOrOnEquality(traceValue, globalMax, diagScore, TraceBitMap_::DIAGONAL);
111 _conditionalOrOnEquality(traceValue, globalMax, vertiScore, TraceBitMap_::VERTICAL);
112 return traceValue;
113 }
114
115 // ----------------------------------------------------------------------------
116 // Function _internalComputeScore()
117 // ----------------------------------------------------------------------------
118
119 template <typename TScoreValue, typename TTraceValueL, typename TTraceValueR>
120 inline typename TraceBitMap_::TTraceValue
_internalComputeScore(DPCell_<TScoreValue,LinearGaps> & activeCell,TScoreValue const & rightCompare,TTraceValueL,TTraceValueR,TracebackOff const &)121 _internalComputeScore(DPCell_<TScoreValue, LinearGaps> & activeCell,
122 TScoreValue const & rightCompare,
123 TTraceValueL,
124 TTraceValueR,
125 TracebackOff const &)
126 {
127 if (activeCell._score < rightCompare)
128 activeCell._score = rightCompare;
129 return TraceBitMap_::NONE;
130 }
131
132 template <typename TScoreValue, typename TTraceValueL, typename TTraceValueR, typename TGapsPlacement>
133 inline typename TraceBitMap_::TTraceValue
_internalComputeScore(DPCell_<TScoreValue,LinearGaps> & activeCell,TScoreValue const & rightCompare,TTraceValueL leftTrace,TTraceValueR rightTrace,TracebackOn<TracebackConfig_<SingleTrace,TGapsPlacement>> const &)134 _internalComputeScore(DPCell_<TScoreValue, LinearGaps> & activeCell,
135 TScoreValue const & rightCompare,
136 TTraceValueL leftTrace,
137 TTraceValueR rightTrace,
138 TracebackOn<TracebackConfig_<SingleTrace, TGapsPlacement> > const &)
139 {
140 if (activeCell._score < rightCompare)
141 {
142 activeCell._score = rightCompare;
143 return rightTrace;
144 }
145 return leftTrace;
146 }
147
148 template <typename TScoreValue, typename TTraceValueL, typename TTraceValueR, typename TGapsPlacement>
149 inline typename TraceBitMap_::TTraceValue
_internalComputeScore(DPCell_<TScoreValue,LinearGaps> & activeCell,TScoreValue const & rightCompare,TTraceValueL leftTrace,TTraceValueR rightTrace,TracebackOn<TracebackConfig_<CompleteTrace,TGapsPlacement>> const &)150 _internalComputeScore(DPCell_<TScoreValue, LinearGaps> & activeCell,
151 TScoreValue const & rightCompare,
152 TTraceValueL leftTrace,
153 TTraceValueR rightTrace,
154 TracebackOn<TracebackConfig_<CompleteTrace, TGapsPlacement> > const &)
155 {
156 if (activeCell._score <= rightCompare)
157 {
158 if (activeCell._score == rightCompare)
159 return leftTrace | rightTrace;
160 activeCell._score = rightCompare;
161 return rightTrace;
162 }
163 return leftTrace;
164 }
165
166 // ----------------------------------------------------------------------------
167 // Function _doComputeScore [RecursionDirectionAll, LinearGaps]
168 // ----------------------------------------------------------------------------
169
170 template <typename TScoreValue, typename TSequenceHValue, typename TSequenceVValue, typename TScoringScheme,
171 typename TAlgorithm, typename TTracebackConfig>
172 inline typename TraceBitMap_::TTraceValue
_doComputeScore(DPCell_<TScoreValue,LinearGaps> & activeCell,DPCell_<TScoreValue,LinearGaps> const & previousDiagonal,DPCell_<TScoreValue,LinearGaps> const & previousHorizontal,DPCell_<TScoreValue,LinearGaps> const & previousVertical,TSequenceHValue const & seqHVal,TSequenceVValue const & seqVVal,TScoringScheme const & scoringScheme,RecursionDirectionAll const &,DPProfile_<TAlgorithm,LinearGaps,TTracebackConfig> const &)173 _doComputeScore(DPCell_<TScoreValue, LinearGaps> & activeCell,
174 DPCell_<TScoreValue, LinearGaps> const & previousDiagonal,
175 DPCell_<TScoreValue, LinearGaps> const & previousHorizontal,
176 DPCell_<TScoreValue, LinearGaps> const & previousVertical,
177 TSequenceHValue const & seqHVal,
178 TSequenceVValue const & seqVVal,
179 TScoringScheme const & scoringScheme,
180 RecursionDirectionAll const &,
181 DPProfile_<TAlgorithm, LinearGaps, TTracebackConfig> const &)
182 {
183 typedef typename TraceBitMap_::TTraceValue TTraceValue;
184 activeCell._score = _scoreOfCell(previousDiagonal) + score(scoringScheme, seqHVal, seqVVal);
185
186 TScoreValue tmpScore = _scoreOfCell(previousVertical) + scoreGapExtendVertical(scoringScheme, seqHVal, seqVVal);
187
188 TTraceValue tv = _internalComputeScore(activeCell, tmpScore, TraceBitMap_::DIAGONAL, TraceBitMap_::VERTICAL | TraceBitMap_::MAX_FROM_VERTICAL_MATRIX, TTracebackConfig());
189 tmpScore = _scoreOfCell(previousHorizontal) + scoreGapExtendHorizontal(scoringScheme, seqHVal, seqVVal);
190 return _internalComputeScore(activeCell, tmpScore, tv, TraceBitMap_::HORIZONTAL | TraceBitMap_::MAX_FROM_HORIZONTAL_MATRIX, TTracebackConfig());
191 }
192
193 // ----------------------------------------------------------------------------
194 // Function _doComputeScore [RecursionDirectionUpperDiagonal, LinearGaps]
195 // ----------------------------------------------------------------------------
196
197 template <typename TScoreValue, typename TSequenceHValue, typename TSequenceVValue, typename TScoringScheme,
198 typename TAlgorithm, typename TTracebackConfig>
199 inline typename TraceBitMap_::TTraceValue
_doComputeScore(DPCell_<TScoreValue,LinearGaps> & activeCell,DPCell_<TScoreValue,LinearGaps> const & previousDiagonal,DPCell_<TScoreValue,LinearGaps> const & previousHorizontal,DPCell_<TScoreValue,LinearGaps> const &,TSequenceHValue const & seqHVal,TSequenceVValue const & seqVVal,TScoringScheme const & scoringScheme,RecursionDirectionUpperDiagonal const &,DPProfile_<TAlgorithm,LinearGaps,TTracebackConfig> const &)200 _doComputeScore(DPCell_<TScoreValue, LinearGaps> & activeCell,
201 DPCell_<TScoreValue, LinearGaps> const & previousDiagonal,
202 DPCell_<TScoreValue, LinearGaps> const & previousHorizontal,
203 DPCell_<TScoreValue, LinearGaps> const & /*previousVertical*/,
204 TSequenceHValue const & seqHVal,
205 TSequenceVValue const & seqVVal,
206 TScoringScheme const & scoringScheme,
207 RecursionDirectionUpperDiagonal const &,
208 DPProfile_<TAlgorithm, LinearGaps, TTracebackConfig> const &)
209 {
210 activeCell._score = _scoreOfCell(previousDiagonal) + score(scoringScheme, seqHVal, seqVVal);
211 TScoreValue tmpScore = _scoreOfCell(previousHorizontal)
212 + scoreGapExtendHorizontal(scoringScheme, seqHVal, seqVVal);
213
214 return _internalComputeScore(activeCell, tmpScore, TraceBitMap_::DIAGONAL, TraceBitMap_::HORIZONTAL | TraceBitMap_::MAX_FROM_HORIZONTAL_MATRIX, TTracebackConfig());
215 }
216
217 // ----------------------------------------------------------------------------
218 // Function _doComputeScore [RecursionDirectionLowerDiagonal, LinearGaps]
219 // ----------------------------------------------------------------------------
220
221 template <typename TScoreValue, typename TSequenceHValue, typename TSequenceVValue, typename TScoringScheme,
222 typename TAlgorithm, typename TTracebackConfig>
223 inline typename TraceBitMap_::TTraceValue
_doComputeScore(DPCell_<TScoreValue,LinearGaps> & activeCell,DPCell_<TScoreValue,LinearGaps> const & previousDiagonal,DPCell_<TScoreValue,LinearGaps> const &,DPCell_<TScoreValue,LinearGaps> const & previousVertical,TSequenceHValue const & seqHVal,TSequenceVValue const & seqVVal,TScoringScheme const & scoringScheme,RecursionDirectionLowerDiagonal const &,DPProfile_<TAlgorithm,LinearGaps,TTracebackConfig> const &)224 _doComputeScore(DPCell_<TScoreValue, LinearGaps> & activeCell,
225 DPCell_<TScoreValue, LinearGaps> const & previousDiagonal,
226 DPCell_<TScoreValue, LinearGaps> const & /*previousHorizontal*/,
227 DPCell_<TScoreValue, LinearGaps> const & previousVertical,
228 TSequenceHValue const & seqHVal,
229 TSequenceVValue const & seqVVal,
230 TScoringScheme const & scoringScheme,
231 RecursionDirectionLowerDiagonal const &,
232 DPProfile_<TAlgorithm, LinearGaps, TTracebackConfig> const &)
233 {
234 activeCell._score = _scoreOfCell(previousDiagonal) + score(scoringScheme, seqHVal, seqVVal);
235 TScoreValue tmpScore = _scoreOfCell(previousVertical)
236 + scoreGapExtendVertical(scoringScheme, seqHVal, seqVVal);
237
238 return _internalComputeScore(activeCell, tmpScore, TraceBitMap_::DIAGONAL, TraceBitMap_::VERTICAL | TraceBitMap_::MAX_FROM_VERTICAL_MATRIX, TTracebackConfig());
239 }
240
241 // ----------------------------------------------------------------------------
242 // Function _doComputeScore [RecursionDirectionHorizontal]
243 // ----------------------------------------------------------------------------
244
245 template <typename TScoreValue, typename TSequenceHValue, typename TSequenceVValue, typename TScoringScheme,
246 typename TAlgorithm, typename TTracebackConfig>
247 inline typename TraceBitMap_::TTraceValue
_doComputeScore(DPCell_<TScoreValue,LinearGaps> & activeCell,DPCell_<TScoreValue,LinearGaps> const &,DPCell_<TScoreValue,LinearGaps> const & previousHorizontal,DPCell_<TScoreValue,LinearGaps> const &,TSequenceHValue const & seqHVal,TSequenceVValue const & seqVVal,TScoringScheme const & scoringScheme,RecursionDirectionHorizontal const &,DPProfile_<TAlgorithm,LinearGaps,TTracebackConfig> const &)248 _doComputeScore(DPCell_<TScoreValue, LinearGaps> & activeCell,
249 DPCell_<TScoreValue, LinearGaps> const & /*previousDiagonal*/,
250 DPCell_<TScoreValue, LinearGaps> const & previousHorizontal,
251 DPCell_<TScoreValue, LinearGaps> const & /*previousVertical*/,
252 TSequenceHValue const & seqHVal,
253 TSequenceVValue const & seqVVal,
254 TScoringScheme const & scoringScheme,
255 RecursionDirectionHorizontal const &,
256 DPProfile_<TAlgorithm, LinearGaps, TTracebackConfig> const &)
257 {
258 activeCell._score = _scoreOfCell(previousHorizontal)
259 + scoreGapExtendHorizontal(scoringScheme, seqHVal, seqVVal);
260
261 if (!IsTracebackEnabled_<TTracebackConfig>::VALUE)
262 return TraceBitMap_::NONE;
263
264 return TraceBitMap_::HORIZONTAL | TraceBitMap_::MAX_FROM_HORIZONTAL_MATRIX;
265 }
266
267 // ----------------------------------------------------------------------------
268 // Function _doComputeScore [RecursionDirectionVertical]
269 // ----------------------------------------------------------------------------
270
271 template <typename TScoreValue, typename TSequenceHValue, typename TSequenceVValue, typename TScoringScheme,
272 typename TAlgorithm, typename TTracebackConfig>
273 inline typename TraceBitMap_::TTraceValue
_doComputeScore(DPCell_<TScoreValue,LinearGaps> & activeCell,DPCell_<TScoreValue,LinearGaps> const &,DPCell_<TScoreValue,LinearGaps> const &,DPCell_<TScoreValue,LinearGaps> const & previousVertical,TSequenceHValue const & seqHVal,TSequenceVValue const & seqVVal,TScoringScheme const & scoringScheme,RecursionDirectionVertical const &,DPProfile_<TAlgorithm,LinearGaps,TTracebackConfig> const &)274 _doComputeScore(DPCell_<TScoreValue, LinearGaps> & activeCell,
275 DPCell_<TScoreValue, LinearGaps> const & /*previousDiagonal*/,
276 DPCell_<TScoreValue, LinearGaps> const & /*previousHorizontal*/,
277 DPCell_<TScoreValue, LinearGaps> const & previousVertical,
278 TSequenceHValue const & seqHVal,
279 TSequenceVValue const & seqVVal,
280 TScoringScheme const & scoringScheme,
281 RecursionDirectionVertical const &,
282 DPProfile_<TAlgorithm, LinearGaps, TTracebackConfig> const &)
283 {
284 activeCell._score = _scoreOfCell(previousVertical)
285 + scoreGapExtendVertical(scoringScheme, seqHVal, seqVVal);
286
287 if (!IsTracebackEnabled_<TTracebackConfig>::VALUE)
288 return TraceBitMap_::NONE;
289
290 return TraceBitMap_::VERTICAL | TraceBitMap_::MAX_FROM_VERTICAL_MATRIX;
291 }
292
293 } // namespace seqan
294
295 #endif // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_FORMULA_LINEAR_H_
296