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 
35 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_SETUP_H_
36 #define SEQAN_INCLUDE_SEQAN_ALIGN_DP_SETUP_H_
37 
38 namespace seqan {
39 
40 // ============================================================================
41 // Forwards
42 // ============================================================================
43 
44 // ============================================================================
45 // Tags, Classes, Enums
46 // ============================================================================
47 
48 
49 // ============================================================================
50 // Metafunctions
51 // ============================================================================
52 
53 // ----------------------------------------------------------------------------
54 // SubstituteAlignConfig_
55 // ----------------------------------------------------------------------------
56 
57 template <typename TAlignConfig>
58 struct SubstituteAlignConfig_;
59 
60 // 0000
61 template <typename TSpec>
62 struct SubstituteAlignConfig_<AlignConfig<false, false, false, false, TSpec> >
63 {
64     typedef FreeEndGaps_<False, False, False, False> Type;
65 };
66 
67 // 0001
68 template <typename TSpec>
69 struct SubstituteAlignConfig_<AlignConfig<false, false, false, true, TSpec> >
70 {
71     typedef FreeEndGaps_<False, False, True, False> Type;
72 };
73 
74 // 0010
75 template <typename TSpec>
76 struct SubstituteAlignConfig_<AlignConfig<false, false, true, false, TSpec> >
77 {
78     typedef FreeEndGaps_<False, False, False, True> Type;
79 };
80 
81 
82 // 0011
83 template <typename TSpec>
84 struct SubstituteAlignConfig_<AlignConfig<false, false, true, true, TSpec> >
85 {
86     typedef FreeEndGaps_<False, False, True, True> Type;
87 };
88 
89 
90 // 0100
91 template <typename TSpec>
92 struct SubstituteAlignConfig_<AlignConfig<false, true, false, false, TSpec> >
93 {
94     typedef FreeEndGaps_<False, True, False, False> Type;
95 };
96 
97 
98 // 0101
99 template <typename TSpec>
100 struct SubstituteAlignConfig_<AlignConfig<false, true, false, true, TSpec> >
101 {
102     typedef FreeEndGaps_<False, True, True, False> Type;
103 };
104 
105 
106 // 0110
107 template <typename TSpec>
108 struct SubstituteAlignConfig_<AlignConfig<false, true, true, false, TSpec> >
109 {
110     typedef FreeEndGaps_<False, True, False, True> Type;
111 };
112 
113 
114 // 0111
115 template <typename TSpec>
116 struct SubstituteAlignConfig_<AlignConfig<false, true, true, true, TSpec> >
117 {
118     typedef FreeEndGaps_<False, True, True, True> Type;
119 };
120 
121 
122 // 1000
123 template <typename TSpec>
124 struct SubstituteAlignConfig_<AlignConfig<true, false, false, false, TSpec> >
125 {
126     typedef FreeEndGaps_<True, False, False, False> Type;
127 };
128 
129 
130 // 1001
131 template <typename TSpec>
132 struct SubstituteAlignConfig_<AlignConfig<true, false, false, true, TSpec> >
133 {
134     typedef FreeEndGaps_<True, False, True, False> Type;
135 };
136 
137 
138 // 1010
139 template <typename TSpec>
140 struct SubstituteAlignConfig_<AlignConfig<true, false, true, false, TSpec> >
141 {
142     typedef FreeEndGaps_<True, False, False, True> Type;
143 };
144 
145 
146 // 1011
147 template <typename TSpec>
148 struct SubstituteAlignConfig_<AlignConfig<true, false, true, true, TSpec> >
149 {
150     typedef FreeEndGaps_<True, False, True, True> Type;
151 };
152 
153 
154 // 1100
155 template <typename TSpec>
156 struct SubstituteAlignConfig_<AlignConfig<true, true, false, false, TSpec> >
157 {
158     typedef FreeEndGaps_<True, True, False, False> Type;
159 };
160 
161 
162 // 1101
163 template <typename TSpec>
164 struct SubstituteAlignConfig_<AlignConfig<true, true, false, true, TSpec> >
165 {
166     typedef FreeEndGaps_<True, True, True, False> Type;
167 };
168 
169 
170 // 1110
171 template <typename TSpec>
172 struct SubstituteAlignConfig_<AlignConfig<true, true, true, false, TSpec> >
173 {
174     typedef FreeEndGaps_<True, True, False, True> Type;
175 };
176 
177 // 1111
178 template <typename TSpec>
179 struct SubstituteAlignConfig_<AlignConfig<true, true, true, true, TSpec> >
180 {
181     typedef FreeEndGaps_<True, True, True, True> Type;
182 };
183 
184 // ----------------------------------------------------------------------------
185 // Metafunction SubstituteAlgoTag_
186 // ----------------------------------------------------------------------------
187 
188 // NOTE(rmaerker): Needed to substitute the global alingment algo tags to the correct gap model.
189 template <typename TTag>
190 struct SubstituteAlgoTag_
191 {
192     typedef TTag Type;
193 };
194 
195 template <>
196 struct SubstituteAlgoTag_<NeedlemanWunsch>
197 {
198     typedef LinearGaps Type;
199 };
200 
201 template <>
202 struct SubstituteAlgoTag_<Gotoh>
203 {
204     typedef AffineGaps Type;
205 };
206 
207 // ----------------------------------------------------------------------------
208 // SetUpAlignmentProfile
209 // ----------------------------------------------------------------------------
210 
211 template <typename TDPType, typename TAlignConfig, typename TTraceSwitch, typename TGapCosts>
212 struct SetupAlignmentProfile_;
213 
214 // Profile for Needleman-Wunsch algorithm.
215 template <typename TFreeEndGaps, typename TGapCosts, typename TTraceSwitch>
216 struct SetupAlignmentProfile_<DPGlobal, TFreeEndGaps, TGapCosts, TTraceSwitch>
217 {
218     typedef DPProfile_<GlobalAlignment_<TFreeEndGaps>, TGapCosts, TTraceSwitch> Type;
219 };
220 
221 // Profile for Smith-Waterman algorithm.
222 template <typename TFreeEndGaps, typename TGapCosts, typename TTraceSwitch>
223 struct SetupAlignmentProfile_<DPLocal, TFreeEndGaps, TGapCosts, TTraceSwitch>
224 {
225     typedef DPProfile_<LocalAlignment_<>, TGapCosts, TTraceSwitch> Type;
226 };
227 
228 // Profile for Waterman-Eggert algorithm
229 template <typename TFreeEndGaps, typename TGapCosts, typename TTraceSwitch>
230 struct SetupAlignmentProfile_<DPLocalEnumerate, TFreeEndGaps, TGapCosts, TTraceSwitch>
231 {
232     typedef DPProfile_<LocalAlignment_<SuboptimalAlignment>, TGapCosts, TracebackOn<TracebackConfig_<SingleTrace, GapsLeft> > > Type;
233 };
234 
235 
236 // ============================================================================
237 // Functions
238 // ============================================================================
239 
240 // ----------------------------------------------------------------------------
241 // Function _usesAffineGaps()
242 // ----------------------------------------------------------------------------
243 
244 template <typename TScoringScheme, typename TSeqH, typename TSeqV>
245 inline bool
246 _usesAffineGaps(TScoringScheme const & scoringScheme,
247                 TSeqH const & seqH,
248                 TSeqV const & seqV)
249 {
250     typedef typename SequenceEntryForScore<TScoringScheme, TSeqH>::Type TSequenceHEntry;
251     typedef typename SequenceEntryForScore<TScoringScheme, TSeqV>::Type TSequenceVEntry;
252 
253     TSequenceHEntry seqHEntry = sequenceEntryForScore(scoringScheme, seqH, 0);
254     TSequenceVEntry seqVEntry = sequenceEntryForScore(scoringScheme, seqV, 0);
255 
256     return (scoreGapExtendHorizontal(scoringScheme, seqHEntry, seqVEntry) !=
257             scoreGapOpenHorizontal(scoringScheme, seqHEntry, seqVEntry)) ||
258            (scoreGapExtendVertical(scoringScheme, seqHEntry, seqVEntry) !=
259                scoreGapOpenVertical(scoringScheme, seqHEntry, seqVEntry));
260 }
261 
262 // ----------------------------------------------------------------------------
263 // Function _setUpAndRunAlignment()
264 // ----------------------------------------------------------------------------
265 
266 template <typename TScoreValue, typename TDPScoutStateSpec, typename TTraceSegment, typename TSpec,
267           typename TSequenceH, typename TSequenceV, typename TScoreValue2, typename TScoreSpec, typename TDPType,
268           typename TBand, typename TFreeEndGaps, typename TTraceConfig>
269 typename Value<Score<TScoreValue2, TScoreSpec> >::Type
270 _setUpAndRunAlignment(DPContext<TScoreValue, AffineGaps> & dpContext,
271                       String<TTraceSegment, TSpec> & traceSegments,
272                       DPScoutState_<TDPScoutStateSpec> & dpScoutState,
273                       TSequenceH const & seqH,
274                       TSequenceV const & seqV,
275                       Score<TScoreValue2, TScoreSpec> const & scoringScheme,
276                       AlignConfig2<TDPType, TBand, TFreeEndGaps, TTraceConfig> const & alignConfig)
277 {
278     SEQAN_ASSERT_GEQ(length(seqH), 1u);
279     SEQAN_ASSERT_GEQ(length(seqV), 1u);
280 
281     typedef typename SetupAlignmentProfile_<TDPType, TFreeEndGaps, AffineGaps, TTraceConfig>::Type TDPProfile;
282     return _computeAlignment(dpContext, traceSegments, dpScoutState, seqH, seqV, scoringScheme, alignConfig._band,
283                              TDPProfile());
284 }
285 
286 template <typename TScoreValue, typename TDPScoutStateSpec, typename TTraceSegment, typename TSpec,
287           typename TSequenceH, typename TSequenceV, typename TScoreValue2, typename TScoreSpec, typename TDPType,
288           typename TBand, typename TFreeEndGaps, typename TTraceConfig>
289 typename Value<Score<TScoreValue2, TScoreSpec> >::Type
290 _setUpAndRunAlignment(DPContext<TScoreValue, LinearGaps> & dpContext,
291                       String<TTraceSegment, TSpec> & traceSegments,
292                       DPScoutState_<TDPScoutStateSpec> & dpScoutState,
293                       TSequenceH const & seqH,
294                       TSequenceV const & seqV,
295                       Score<TScoreValue2, TScoreSpec> const & scoringScheme,
296                       AlignConfig2<TDPType, TBand, TFreeEndGaps, TTraceConfig> const & alignConfig)
297 {
298     SEQAN_ASSERT_GEQ(length(seqH), 1u);
299     SEQAN_ASSERT_GEQ(length(seqV), 1u);
300 
301     typedef typename SetupAlignmentProfile_<TDPType, TFreeEndGaps, LinearGaps, TTraceConfig>::Type TDPProfile;
302     return _computeAlignment(dpContext, traceSegments, dpScoutState, seqH, seqV, scoringScheme, alignConfig._band,
303                              TDPProfile());
304 }
305 
306 template <typename TScoreValue, typename TDPScoutStateSpec, typename TTraceSegment, typename TSpec,
307           typename TSequenceH, typename TSequenceV, typename TScoreValue2, typename TScoreSpec, typename TDPType,
308           typename TBand, typename TFreeEndGaps, typename TTraceConfig>
309 typename Value<Score<TScoreValue2, TScoreSpec> >::Type
310 _setUpAndRunAlignment(DPContext<TScoreValue, DynamicGaps> & dpContext,
311                       String<TTraceSegment, TSpec> & traceSegments,
312                       DPScoutState_<TDPScoutStateSpec> & dpScoutState,
313                       TSequenceH const & seqH,
314                       TSequenceV const & seqV,
315                       Score<TScoreValue2, TScoreSpec> const & scoringScheme,
316                       AlignConfig2<TDPType, TBand, TFreeEndGaps, TTraceConfig> const & alignConfig)
317 {
318     SEQAN_ASSERT_GEQ(length(seqH), 1u);
319     SEQAN_ASSERT_GEQ(length(seqV), 1u);
320 
321     typedef typename SetupAlignmentProfile_<TDPType, TFreeEndGaps, DynamicGaps, TTraceConfig>::Type TDPProfile;
322     return _computeAlignment(dpContext, traceSegments, dpScoutState, seqH, seqV, scoringScheme, alignConfig._band,
323                              TDPProfile());
324 }
325 
326 template <typename TTraceSegment, typename TSpec, typename TDPScoutStateSpec,
327           typename TSequenceH, typename TSequenceV, typename TScoreValue2, typename TScoreSpec, typename TDPType,
328           typename TBand, typename TFreeEndGaps, typename TTraceConfig, typename TGapModel>
329 typename Value<Score<TScoreValue2, TScoreSpec> >::Type
330 _setUpAndRunAlignment(String<TTraceSegment, TSpec> & traceSegments,
331                       DPScoutState_<TDPScoutStateSpec> & dpScoutState,
332                       TSequenceH const & seqH,
333                       TSequenceV const & seqV,
334                       Score<TScoreValue2, TScoreSpec> const & scoringScheme,
335                       AlignConfig2<TDPType, TBand, TFreeEndGaps, TTraceConfig> const & alignConfig,
336                       TGapModel const & /**/)
337 {
338     if (IsSameType<TGapModel, LinearGaps>::VALUE)
339     {
340         DPContext<TScoreValue2, LinearGaps> dpContext;
341         return _setUpAndRunAlignment(dpContext, traceSegments, dpScoutState, seqH, seqV, scoringScheme, alignConfig);
342     }
343     else if (IsSameType<TGapModel, AffineGaps>::VALUE)
344     {
345         DPContext<TScoreValue2, AffineGaps> dpContext;
346         return _setUpAndRunAlignment(dpContext, traceSegments, dpScoutState, seqH, seqV, scoringScheme, alignConfig);
347     }
348     else
349     {
350         DPContext<TScoreValue2, DynamicGaps> dpContext;
351         return _setUpAndRunAlignment(dpContext, traceSegments, dpScoutState, seqH, seqV, scoringScheme, alignConfig);
352     }
353 }
354 
355 template <typename TTraceSegment, typename TSpec, typename TDPScoutStateSpec,
356           typename TSequenceH, typename TSequenceV, typename TScoreValue2, typename TScoreSpec, typename TDPType,
357           typename TBand, typename TFreeEndGaps, typename TTraceConfig>
358 typename Value<Score<TScoreValue2, TScoreSpec> >::Type
359 _setUpAndRunAlignment(String<TTraceSegment, TSpec> & traceSegments,
360                       DPScoutState_<TDPScoutStateSpec> & dpScoutState,
361                       TSequenceH const & seqH,
362                       TSequenceV const & seqV,
363                       Score<TScoreValue2, TScoreSpec> const & scoringScheme,
364                       AlignConfig2<TDPType, TBand, TFreeEndGaps, TTraceConfig> const & alignConfig)
365 {
366     if (_usesAffineGaps(scoringScheme, seqH, seqV))
367         return _setUpAndRunAlignment(traceSegments, dpScoutState, seqH, seqV, scoringScheme, alignConfig, AffineGaps());
368     else
369         return _setUpAndRunAlignment(traceSegments, dpScoutState, seqH, seqV, scoringScheme, alignConfig, LinearGaps());
370 }
371 
372 }  // namespace seqan
373 
374 #endif  // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_SETUP_H_
375