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