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 // This header contains all tags, structures and meta-functions that are 35 // used to define the meta-profile of an alignment algorithm. 36 // With the meta-profile the sort of alignment can be selected such as 37 // a global or a local alignment. It further structures the different 38 // specializations of global and local alignments or selects the gap cost 39 // function, or enables or disables the trace-back function. 40 // ========================================================================== 41 42 // TODO(holtgrew): Documentation in this header necessary or internal only? 43 44 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_PROFILE_H_ 45 #define SEQAN_INCLUDE_SEQAN_ALIGN_DP_PROFILE_H_ 46 47 namespace seqan { 48 49 // ============================================================================ 50 // Forwards 51 // ============================================================================ 52 53 // ============================================================================ 54 // Tags, Classes, Enums 55 // ============================================================================ 56 57 // ---------------------------------------------------------------------------- 58 // Class FreeEndGaps_ 59 // ---------------------------------------------------------------------------- 60 61 // Used to determine which end-gaps are free. 62 template <typename TInitGapsHorizontal = False, typename TInitGapsVertical = False, typename TEndGapsHorizontal = False, 63 typename TEndGapsVertical = False> 64 struct FreeEndGaps_ {}; 65 66 // ---------------------------------------------------------------------------- 67 // Class SplitBreakpointAlignment 68 // ---------------------------------------------------------------------------- 69 // TODO(rmaerker): maybe in a different header 70 // Used to specify the global alignment for split breakpoint computation. 71 struct AlignmentSplitBreakpoint_; 72 typedef Tag<AlignmentSplitBreakpoint_> SplitBreakpointAlignment; 73 74 // ---------------------------------------------------------------------------- 75 // Class GlobalAlignment_ 76 // ---------------------------------------------------------------------------- 77 78 // This is used to select global alignments. The default is the standard global 79 // dp-algorithm. 80 // 81 // Note, all global alignments have to be specialized versions of GlobalAlignment_<> 82 template <typename TSpec = FreeEndGaps_<> > 83 struct GlobalAlignment_; 84 85 typedef GlobalAlignment_<> DPGlobal; 86 87 // ---------------------------------------------------------------------------- 88 // Class SuboptimalAlignment 89 // ---------------------------------------------------------------------------- 90 91 // TODO(rmaerker): maybe in a different header 92 // Used to specify the WatermanEggert algorithm. 93 struct AlignmentSuboptimal_; 94 typedef Tag<AlignmentSuboptimal_> SuboptimalAlignment; 95 96 // ---------------------------------------------------------------------------- 97 // Class LocalAlignment_ 98 // ---------------------------------------------------------------------------- 99 100 // This is used to select local alignments. The default is the standard local 101 // dp-algorithm. 102 // 103 // Note, all local alignments have to be specialized versions of LocalAlignment_<> 104 105 template <typename TSpec = Default> 106 struct LocalAlignment_; 107 108 typedef LocalAlignment_<> DPLocal; 109 typedef LocalAlignment_<SuboptimalAlignment> DPLocalEnumerate; 110 111 // ---------------------------------------------------------------------------- 112 // Class TraceBitMap_ 113 // ---------------------------------------------------------------------------- 114 115 // Used to globally ditinguish different traceback directions and the underlying 116 // type to store the values. 117 struct TraceBitMap_ 118 { 119 typedef uint8_t TTraceValue; 120 static const TTraceValue NONE = 0u; //0000000 121 static const TTraceValue DIAGONAL = 1u; //0000001 122 static const TTraceValue HORIZONTAL = 2u; //0000010 123 static const TTraceValue VERTICAL = 4u; //0000100 124 static const TTraceValue HORIZONTAL_OPEN = 8u; //0001000 125 static const TTraceValue VERTICAL_OPEN = 16u; //0010000 126 static const TTraceValue MAX_FROM_HORIZONTAL_MATRIX = 32u; //0100000 127 static const TTraceValue MAX_FROM_VERTICAL_MATRIX = 64u; //1000000 128 static const TTraceValue NO_VERTICAL_TRACEBACK = ~(VERTICAL | VERTICAL_OPEN); 129 static const TTraceValue NO_HORIZONTAL_TRACEBACK = ~(HORIZONTAL | HORIZONTAL_OPEN); 130 }; 131 132 // ---------------------------------------------------------------------------- 133 // Tag GapsLeft 134 // ---------------------------------------------------------------------------- 135 136 struct GapsLeft_; 137 typedef Tag<GapsLeft_> GapsLeft; 138 139 // ---------------------------------------------------------------------------- 140 // Tag GapsRight 141 // ---------------------------------------------------------------------------- 142 143 struct GapsRight_; 144 typedef Tag<GapsRight_> GapsRight; 145 146 147 // ---------------------------------------------------------------------------- 148 // Tag SingleTrace 149 // ---------------------------------------------------------------------------- 150 151 struct SingleTrace_; 152 typedef Tag<SingleTrace_> SingleTrace; 153 154 // ---------------------------------------------------------------------------- 155 // Tag CompleteTrace 156 // ---------------------------------------------------------------------------- 157 158 struct CompleteTrace_; 159 typedef Tag<CompleteTrace_> CompleteTrace; 160 161 // ---------------------------------------------------------------------------- 162 // Tag TracebackConfig_ 163 // ---------------------------------------------------------------------------- 164 165 template <typename TTracesSpec, typename TGapsPlacement> 166 struct TracebackConfig_ {}; 167 168 // ---------------------------------------------------------------------------- 169 // Tag TracebackOn 170 // ---------------------------------------------------------------------------- 171 172 template <typename TSpec = TracebackConfig_<CompleteTrace, GapsLeft> > 173 struct TracebackOn {}; 174 175 // ---------------------------------------------------------------------------- 176 // Tag TracebackOff 177 // ---------------------------------------------------------------------------- 178 179 struct TracebackOff_ {}; 180 typedef Tag<TracebackOff_> TracebackOff; 181 182 // ---------------------------------------------------------------------------- 183 // Tag LinearGaps 184 // ---------------------------------------------------------------------------- 185 186 struct LinearGaps_; 187 typedef Tag<LinearGaps_> LinearGaps; 188 189 // ---------------------------------------------------------------------------- 190 // Tag AffineGaps 191 // ---------------------------------------------------------------------------- 192 193 struct AffineGaps_; 194 typedef Tag<AffineGaps_> AffineGaps; 195 196 // ---------------------------------------------------------------------------- 197 // Tag DynamicGaps 198 // ---------------------------------------------------------------------------- 199 200 /*! 201 * @tag AlignmentAlgorithmTags#DynamicGaps 202 * @headerfile <seqan/align.h> 203 * @brief Tag for selecting dynamic gap cost model. This tag can be used for all standard DP algorithms. 204 * 205 * @signature struct DynamicGaps_; 206 * @signature typedef Tag<DynamicGaps_> DynamicGaps; 207 */ 208 209 struct DynamicGaps_; 210 typedef Tag<DynamicGaps_> DynamicGaps; 211 212 // ---------------------------------------------------------------------------- 213 // Class DPProfile 214 // ---------------------------------------------------------------------------- 215 216 // This meta-object takes three types to be specialized. 217 // 218 // TAlignment: The type to select the pairwise alignment algorithm. 219 // TGapCosts: The gap cost function (LinearGaps or AffineGaps). 220 // TTraceback: The traceback switch (TracebackOn or TracebackOff). 221 template <typename TAlignment, typename TGapCosts, typename TTraceback> 222 struct DPProfile_ {}; 223 224 225 // ---------------------------------------------------------------------------- 226 // Tag DPFirstRow 227 // ---------------------------------------------------------------------------- 228 229 // These tags are used to specify the four locations of a dp-matrix where 230 // free gaps can occur. 231 struct DPFirstRow_; 232 typedef Tag<DPFirstRow_> DPFirstRow; 233 234 // ---------------------------------------------------------------------------- 235 // Tag DPFirstColumn 236 // ---------------------------------------------------------------------------- 237 238 struct DPFirstColumn_; 239 typedef Tag<DPFirstColumn_> DPFirstColumn; 240 241 // ---------------------------------------------------------------------------- 242 // Tag DPLastRow 243 // ---------------------------------------------------------------------------- 244 245 struct DPLastRow_; 246 typedef Tag<DPLastRow_> DPLastRow; 247 248 // ---------------------------------------------------------------------------- 249 // Tag DPLastColumn 250 // ---------------------------------------------------------------------------- 251 252 struct DPLastColumn_; 253 typedef Tag<DPLastColumn_> DPLastColumn; 254 255 template <typename TDPType, typename TBand, typename TFreeEndGaps = FreeEndGaps_<False, False, False, False>, 256 typename TTraceConfig = TracebackOn<TracebackConfig_<SingleTrace, GapsLeft> > > 257 class AlignConfig2 258 { 259 public: 260 TBand _band; 261 AlignConfig2()262 AlignConfig2() : _band() 263 {} 264 265 template <typename TPosition> AlignConfig2(TPosition const & lDiag,TPosition const & uDiag)266 AlignConfig2(TPosition const & lDiag, TPosition const & uDiag) : _band(lDiag, uDiag) 267 {} 268 }; 269 270 // ============================================================================ 271 // Metafunctions 272 // ============================================================================ 273 274 // ---------------------------------------------------------------------------- 275 // Metafunction IsGlobalAlignment 276 // ---------------------------------------------------------------------------- 277 278 // Checks if the dp profile is a global alignment. 279 template <typename T> 280 struct IsGlobalAlignment_ : 281 False {}; 282 283 template <typename TSpec> 284 struct IsGlobalAlignment_<GlobalAlignment_<TSpec> >: 285 True {}; 286 287 template <typename TSpec> 288 struct IsGlobalAlignment_<GlobalAlignment_<TSpec> const>: 289 True {}; 290 291 template <typename TAlgoSpec, typename TGapCosts, typename TTraceFlag> 292 struct IsGlobalAlignment_<DPProfile_<TAlgoSpec, TGapCosts, TTraceFlag> >: 293 IsGlobalAlignment_<TAlgoSpec>{}; 294 295 template <typename TAlgoSpec, typename TGapCosts, typename TTraceFlag> 296 struct IsGlobalAlignment_<DPProfile_<TAlgoSpec, TGapCosts, TTraceFlag> const>: 297 IsGlobalAlignment_<TAlgoSpec>{}; 298 299 // ---------------------------------------------------------------------------- 300 // Metafunction TraceTail_ 301 // ---------------------------------------------------------------------------- 302 303 // define whether to include the 'tail' of an alignment in the trace 304 template <typename TSpec> 305 struct TraceTail_ : 306 IsGlobalAlignment_<TSpec>{}; 307 308 // ---------------------------------------------------------------------------- 309 // Metafunction TraceHead_ 310 // ---------------------------------------------------------------------------- 311 312 // define whether to include the 'head' of an alignment in the trace 313 template <typename TSpec> 314 struct TraceHead_ : 315 IsGlobalAlignment_<TSpec>{}; 316 317 // ---------------------------------------------------------------------------- 318 // Metafunction HasTerminationCriterium_ 319 // ---------------------------------------------------------------------------- 320 321 // check whether an algorithm has an early termination criterium 322 // if an algorithm has this, it will get a DPscout that can be terminated 323 // see dp_scout.h for more info 324 template <typename TSpec> 325 struct HasTerminationCriterium_ : 326 False {}; 327 328 // ---------------------------------------------------------------------------- 329 // Metafunction IsLocalAlignment_ 330 // ---------------------------------------------------------------------------- 331 332 // Checks if the dp profile is a local alignment. 333 template <typename T> 334 struct IsLocalAlignment_ : 335 False {}; 336 337 template <typename TSpec> 338 struct IsLocalAlignment_<LocalAlignment_<TSpec> >: 339 True {}; 340 341 template <typename TSpec> 342 struct IsLocalAlignment_<LocalAlignment_<TSpec> const>: 343 True {}; 344 345 template <typename TAlgoSpec, typename TGapCosts, typename TTraceFlag> 346 struct IsLocalAlignment_<DPProfile_<TAlgoSpec, TGapCosts, TTraceFlag> >: 347 IsLocalAlignment_<TAlgoSpec>{}; 348 349 template <typename TAlgoSpec, typename TGapCosts, typename TTraceFlag> 350 struct IsLocalAlignment_<DPProfile_<TAlgoSpec, TGapCosts, TTraceFlag> const>: 351 IsLocalAlignment_<TAlgoSpec>{}; 352 353 // ---------------------------------------------------------------------------- 354 // Metafunction IsTracebackEnabled_ 355 // ---------------------------------------------------------------------------- 356 357 // Checks if the trace-back for the current dp profile is enabled. 358 template <typename T> 359 struct IsTracebackEnabled_ : 360 False {}; 361 362 template <typename TTracebackConfig> 363 struct IsTracebackEnabled_<TracebackOn<TTracebackConfig> >: 364 True {}; 365 366 template <typename TTracebackConfig> 367 struct IsTracebackEnabled_<TracebackOn<TTracebackConfig> const>: 368 True {}; 369 370 template <typename TAlgoSpec, typename TGapCosts, typename TTraceFlag> 371 struct IsTracebackEnabled_<DPProfile_<TAlgoSpec, TGapCosts, TTraceFlag> >: 372 IsTracebackEnabled_<TTraceFlag>{}; 373 374 template <typename TAlgoSpec, typename TGapCosts, typename TTraceFlag> 375 struct IsTracebackEnabled_<DPProfile_<TAlgoSpec, TGapCosts, TTraceFlag> const>: 376 IsTracebackEnabled_<TTraceFlag>{}; 377 378 // ---------------------------------------------------------------------------- 379 // Metafunction IsGapsLeft_ 380 // ---------------------------------------------------------------------------- 381 382 template <typename TTraceConfig> 383 struct IsGapsLeft_ : False{}; 384 385 template <typename TTraceSpec> 386 struct IsGapsLeft_<TracebackOn<TracebackConfig_<TTraceSpec, GapsLeft > > > 387 : True{}; 388 389 template <typename TAlgorithm, typename TGapSpec, typename TTraceConfig> 390 struct IsGapsLeft_<DPProfile_<TAlgorithm, TGapSpec, TTraceConfig> > 391 : IsGapsLeft_<TTraceConfig>{}; 392 393 // ---------------------------------------------------------------------------- 394 // Metafunction IsSingleTrace_ 395 // ---------------------------------------------------------------------------- 396 397 template <typename TTraceConfig> 398 struct IsSingleTrace_ : False{}; 399 400 template <typename TGapsPlacement> 401 struct IsSingleTrace_<TracebackOn<TracebackConfig_<SingleTrace, TGapsPlacement> > > 402 : True{}; 403 404 template <typename TAlgorithm, typename TGapSpec, typename TTraceConfig> 405 struct IsSingleTrace_<DPProfile_<TAlgorithm, TGapSpec, TTraceConfig> > 406 : IsSingleTrace_<TTraceConfig>{}; 407 408 // ---------------------------------------------------------------------------- 409 // Metafunction IsFreeEndGap_ 410 // ---------------------------------------------------------------------------- 411 412 // Checks if for the current dp profile and a given gap location the algorithm uses free gaps. 413 template <typename TAlignmentSpec, typename TDPSide> 414 struct IsFreeEndGap_ : 415 False {}; 416 417 template <typename TAlignmentSpec, typename TGapSpec, typename TTracebackSpec, typename TDPSide> 418 struct IsFreeEndGap_<DPProfile_<TAlignmentSpec, TGapSpec, TTracebackSpec> const, TDPSide>: 419 IsFreeEndGap_<TAlignmentSpec, TDPSide>{}; 420 421 template <typename TAlignmentSpec, typename TGapSpec, typename TTracebackSpec, typename TDPSide> 422 struct IsFreeEndGap_<DPProfile_<TAlignmentSpec, TGapSpec, TTracebackSpec>, TDPSide>: 423 IsFreeEndGap_<TAlignmentSpec, TDPSide>{}; 424 425 template <typename TLocalSpec, typename TDPSide> 426 struct IsFreeEndGap_<LocalAlignment_<TLocalSpec> const, TDPSide>: 427 True 428 {}; 429 430 template <typename TLocalSpec, typename TDPSide> 431 struct IsFreeEndGap_<LocalAlignment_<TLocalSpec>, TDPSide>: 432 True 433 {}; 434 435 template <typename TFreeEndGaps, typename TDPSide> 436 struct IsFreeEndGap_<GlobalAlignment_<TFreeEndGaps> const, TDPSide>: 437 IsFreeEndGap_<TFreeEndGaps, TDPSide> 438 {}; 439 440 template <typename TFreeEndGaps, typename TDPSide> 441 struct IsFreeEndGap_<GlobalAlignment_<TFreeEndGaps>, TDPSide>: 442 IsFreeEndGap_<TFreeEndGaps const, TDPSide> 443 {}; 444 445 template <typename TFirstColumn, typename TLastRow, typename TLastColumn> 446 struct IsFreeEndGap_<FreeEndGaps_<True, TFirstColumn, TLastRow, TLastColumn>, DPFirstRow>: 447 True 448 {}; 449 450 template <typename TFirstColumn, typename TLastRow, typename TLastColumn> 451 struct IsFreeEndGap_<FreeEndGaps_<True, TFirstColumn, TLastRow, TLastColumn> const, DPFirstRow>: 452 True 453 {}; 454 455 template <typename TFirstRow, typename TLastRow, typename TLastColumn> 456 struct IsFreeEndGap_<FreeEndGaps_<TFirstRow, True, TLastRow, TLastColumn>, DPFirstColumn>: 457 True 458 {}; 459 460 template <typename TFirstRow, typename TLastRow, typename TLastColumn> 461 struct IsFreeEndGap_<FreeEndGaps_<TFirstRow, True, TLastRow, TLastColumn> const, DPFirstColumn>: 462 True 463 {}; 464 465 template <typename TFirstRow, typename TFirstColumn, typename TLastColumn> 466 struct IsFreeEndGap_<FreeEndGaps_<TFirstRow, TFirstColumn, True, TLastColumn>, DPLastRow>: 467 True 468 {}; 469 470 template <typename TFirstRow, typename TFirstColumn, typename TLastColumn> 471 struct IsFreeEndGap_<FreeEndGaps_<TFirstRow, TFirstColumn, True, TLastColumn> const, DPLastRow>: 472 True 473 {}; 474 475 template <typename TFirstRow, typename TFirstColumn, typename TLastRow> 476 struct IsFreeEndGap_<FreeEndGaps_<TFirstRow, TFirstColumn, TLastRow, True>, DPLastColumn>: 477 True 478 {}; 479 480 template <typename TFirstRow, typename TFirstColumn, typename TLastRow> 481 struct IsFreeEndGap_<FreeEndGaps_<TFirstRow, TFirstColumn, TLastRow, True> const, DPLastColumn>: 482 True 483 {}; 484 485 // ============================================================================ 486 // Functions 487 // ============================================================================ 488 489 } // namespace seqan 490 491 #endif // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_PROFILE_H_ 492