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: Ren� Rahn <rene.rahn@fu-berlin.de> 33 // ========================================================================== 34 // Here are defined the strategies for the different alignment algorithms. 35 // All classes are only used to determine the correct computational state 36 // of a particular alignment algorithm depending on its profile at a 37 // particular time. 38 // All classes are only used on a meta-level. 39 // ========================================================================== 40 41 // TODO(holtgrew): Documentation in this header necessary or internal only? 42 43 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_META_INFO_H_ 44 #define SEQAN_INCLUDE_SEQAN_ALIGN_DP_META_INFO_H_ 45 46 namespace seqan { 47 48 // ============================================================================ 49 // Forwards 50 // ============================================================================ 51 52 // ============================================================================ 53 // Tags, Classes, Enums 54 // ============================================================================ 55 56 // ---------------------------------------------------------------------------- 57 // Tag DPInitialColumn 58 // ---------------------------------------------------------------------------- 59 60 // Specifies the first column of the dp matrix. 61 struct DPInitialColumn_; 62 typedef Tag<DPInitialColumn_> DPInitialColumn; 63 64 // ---------------------------------------------------------------------------- 65 // Tag DPInnerColumn 66 // ---------------------------------------------------------------------------- 67 68 // Specifies any inner column of the dp matrix between the first and the last 69 // column. 70 struct DPInnerColumn_; 71 typedef Tag<DPInnerColumn_> DPInnerColumn; 72 73 // ---------------------------------------------------------------------------- 74 // Tag DPFinalColumn 75 // ---------------------------------------------------------------------------- 76 77 // Specifies the last column of a dp matrix. 78 struct DPFinalColumn_; 79 typedef Tag<DPFinalColumn_> DPFinalColumn; 80 81 82 // The TColumnProperty determines the property of the column (if it is initial, inner, or last column) 83 // The TLocation determines how the column is organized in the matrix. 84 // It can have the values: FullColumn, PartialColumnTop, PartialColumnMiddle, PartialColumnBottom. 85 template <typename TColumnProperty_, typename TLocation_> 86 struct MetaColumnDescriptor 87 { 88 typedef TColumnProperty_ TColumnProperty; 89 typedef TLocation_ TLocation; 90 }; 91 92 // ---------------------------------------------------------------------------- 93 // Tag FullColumn 94 // ---------------------------------------------------------------------------- 95 96 // Columns that span over the complete dp-matrix. (Unbanded alignemnts) 97 struct FullColumn_; 98 typedef Tag<FullColumn_> FullColumn; 99 100 // ---------------------------------------------------------------------------- 101 // Tag PartialColumnTop 102 // ---------------------------------------------------------------------------- 103 104 // Columns that begin in the first row, but does not at the last row of the dp-matrix 105 struct PartialColumnTop_; 106 typedef Tag<PartialColumnTop_> PartialColumnTop; 107 108 // ---------------------------------------------------------------------------- 109 // Tag PartialColumnMiddle 110 // ---------------------------------------------------------------------------- 111 112 // Columns that are not attached to the begin or end of the dp-matrix. 113 struct PartialColumnMiddle_; 114 typedef Tag<PartialColumnMiddle_> PartialColumnMiddle; 115 116 // ---------------------------------------------------------------------------- 117 // Tag PartialColumnBottom 118 // ---------------------------------------------------------------------------- 119 120 // Columns that end in the last row of the dp-matrix but do not start in the first row. 121 struct PartialColumnBottom_; 122 typedef Tag<PartialColumnBottom_> PartialColumnBottom; 123 124 125 // The cell specifiers are used to determine the cell of a column. 126 // There are three different cell specifiers used for the first cell, the 127 // inner cell and the last cell of a column. 128 129 // ---------------------------------------------------------------------------- 130 // Tag FirstCell 131 // ---------------------------------------------------------------------------- 132 133 struct FirstCell_; 134 typedef Tag<FirstCell_> FirstCell; 135 136 // ---------------------------------------------------------------------------- 137 // Tag InnerCell 138 // ---------------------------------------------------------------------------- 139 140 struct InnerCell_; 141 typedef Tag<InnerCell_> InnerCell; 142 143 // ---------------------------------------------------------------------------- 144 // Tag LastCell 145 // ---------------------------------------------------------------------------- 146 147 struct LastCell_; 148 typedef Tag<LastCell_> LastCell; 149 150 151 // ---------------------------------------------------------------------------- 152 // Class DPMetaCell_ 153 // ---------------------------------------------------------------------------- 154 155 // Keeps meta-information of a cell in the dp-matrix. It stores the recursion direction 156 // for a particular cell type and whether it can be tracked or not. 157 158 template <typename TDPRecursionDirection, typename TTrackFlag> 159 struct DPMetaCell_ {}; 160 161 // ---------------------------------------------------------------------------- 162 // Class DPMetaColumn_ 163 // ---------------------------------------------------------------------------- 164 165 // Keeps meta-information of an entire column in the dp-matrix. Depending on the chosen 166 // DPProfile and the current column descriptor it selects for the different column locations and 167 // cell specifiers the correct meta-information about how is which cell computed and which cell is 168 // tracked. 169 170 template <typename TDPProfile, typename TColumnDescriptor> 171 struct DPMetaColumn_ {}; 172 173 174 // ---------------------------------------------------------------------------- 175 // Class DPMetaColumn_ [FullColumn] 176 // ---------------------------------------------------------------------------- 177 178 template <typename TDPProfile, typename TColumnType> 179 struct DPMetaColumn_<TDPProfile, MetaColumnDescriptor<TColumnType, FullColumn> > 180 { 181 typedef typename IsLocalAlignment_<TDPProfile>::Type TIsLocal; 182 183 // If InitialColumn -> Zero, Vertical | Zero, Vertical | Zero // Within the algorithm we need to define the first row as only one cell if it is no initial column 184 // If InnerColumn -> Horizontal | Zero, All, All 185 // If FinalColumn -> Horizontal | Zero, All, All 186 187 typedef typename If<Or<IsSameType<TColumnType, DPInitialColumn>, 188 IsFreeEndGap_<TDPProfile, DPFirstRow> >, RecursionDirectionZero, RecursionDirectionHorizontal>::Type TRecursionTypeFirstCell_; 189 typedef typename If<IsSameType<TColumnType, DPInitialColumn>, 190 typename If<IsFreeEndGap_<TDPProfile, DPFirstColumn>, RecursionDirectionZero, RecursionDirectionVertical>::Type, 191 RecursionDirectionAll>::Type TRecursionTypeInnerCell_; 192 typedef typename If<IsSameType<TColumnType, DPInitialColumn>, 193 typename If<IsFreeEndGap_<TDPProfile, DPFirstColumn>, RecursionDirectionZero, RecursionDirectionVertical>::Type, 194 RecursionDirectionAll>::Type TRecursionTypeLastCell_; 195 196 // If Local 197 // If InitialColumn -> True, True, True 198 // If InnerColumn -> True, True, True 199 // If FinalColumn -> True, True, True 200 201 // If Global 202 // If InitialColumn -> False, False, False | True (if DPLastRow) 203 // If InnerColumn -> False, False, False | True (if DPLastRow) 204 // If FinalColumn -> False | True, False | True (if DPLastColumn), True 205 206 typedef typename If<Or<IsLocalAlignment_<TDPProfile>, 207 And<IsSameType<TColumnType, DPFinalColumn>, 208 IsFreeEndGap_<TDPProfile, DPLastColumn> > // check this if he is really entitled to find the maximum here. 209 >, True, False>::Type TrackFlagFirstCell_; 210 typedef typename If<Or<IsLocalAlignment_<TDPProfile>, 211 And<IsSameType<TColumnType, DPFinalColumn>, 212 IsFreeEndGap_<TDPProfile, DPLastColumn> > 213 >, True, False>::Type TrackFlagInnerCell_; 214 typedef typename If<Or<IsLocalAlignment_<TDPProfile>, 215 Or<IsSameType<TColumnType, DPFinalColumn>, 216 IsFreeEndGap_<TDPProfile, DPLastRow> > >, True, False>::Type TrackFlagLastCell_; 217 218 typedef DPMetaCell_<TRecursionTypeFirstCell_, TrackFlagFirstCell_> TFirstCell_; 219 typedef DPMetaCell_<TRecursionTypeInnerCell_, TrackFlagInnerCell_> TInnerCell_; 220 typedef DPMetaCell_<TRecursionTypeLastCell_, TrackFlagLastCell_> TLastCell_; 221 }; 222 223 // ---------------------------------------------------------------------------- 224 // Class DPMetaColumn_ [PartialColumnTop] 225 // ---------------------------------------------------------------------------- 226 227 template <typename TDPProfile, typename TColumnType> 228 struct DPMetaColumn_<TDPProfile, MetaColumnDescriptor<TColumnType, PartialColumnTop> > 229 { 230 typedef typename IsLocalAlignment_<TDPProfile>::Type TIsLocal; 231 232 // How does the recursion directions look like? 233 234 // If InitialColumn -> Zero, Vertical | Zero, Vertical | Zero // Within the algorithm we need to define the first row as only one cell if it is no initial column 235 // If InnerColumn -> Horizontal | Zero, All, LowerBand 236 // If FinalColumn -> Horizontal | Zero, All, LowerBand 237 238 typedef typename If<Or<IsSameType<TColumnType, DPInitialColumn>, 239 IsFreeEndGap_<TDPProfile, DPFirstRow> >, RecursionDirectionZero, RecursionDirectionHorizontal>::Type TRecursionTypeFirstCell_; 240 typedef typename If<IsSameType<TColumnType, DPInitialColumn>, 241 typename If<IsFreeEndGap_<TDPProfile, DPFirstColumn>, RecursionDirectionZero, RecursionDirectionVertical>::Type, 242 RecursionDirectionAll>::Type TRecursionTypeInnerCell_; 243 typedef typename If<IsSameType<TColumnType, DPInitialColumn>, 244 typename If<IsFreeEndGap_<TDPProfile, DPFirstColumn>, RecursionDirectionZero, RecursionDirectionVertical>::Type, 245 RecursionDirectionLowerDiagonal>::Type TRecursionTypeLastCell_; 246 247 // If Local 248 // If InitialColumn -> True, True, True 249 // If InnerColumn -> True, True, True 250 // If FinalColumn -> True, True, True 251 252 // If Global 253 // If InitialColumn -> False, False, False 254 // If InnerColumn -> False, False, False 255 // If FinalColumn -> False | True, False | True, False | True (if DPLastColumn True) 256 257 typedef typename If<Or<IsLocalAlignment_<TDPProfile>, 258 And<IsSameType<TColumnType, DPFinalColumn>, 259 IsFreeEndGap_<TDPProfile, DPLastColumn> > 260 >, True, False>::Type TrackFlagFirstCell_; 261 typedef typename If<Or<IsLocalAlignment_<TDPProfile>, 262 And<IsSameType<TColumnType, DPFinalColumn>, 263 IsFreeEndGap_<TDPProfile, DPLastColumn> > 264 >, True, False>::Type TrackFlagInnerCell_; 265 typedef typename If<Or<IsLocalAlignment_<TDPProfile>, 266 And<IsSameType<TColumnType, DPFinalColumn>, 267 IsFreeEndGap_<TDPProfile, DPLastColumn> > 268 >, True, False>::Type TrackFlagLastCell_; 269 270 typedef DPMetaCell_<TRecursionTypeFirstCell_, TrackFlagFirstCell_> TFirstCell_; 271 typedef DPMetaCell_<TRecursionTypeInnerCell_, TrackFlagInnerCell_> TInnerCell_; 272 typedef DPMetaCell_<TRecursionTypeLastCell_, TrackFlagLastCell_> TLastCell_; 273 }; 274 275 // ---------------------------------------------------------------------------- 276 // Class DPMetaColumn_ [PartialColumnMiddle] 277 // ---------------------------------------------------------------------------- 278 279 template <typename TDPProfile, typename TColumnType> 280 struct DPMetaColumn_<TDPProfile, MetaColumnDescriptor<TColumnType, PartialColumnMiddle> > 281 { 282 typedef typename IsLocalAlignment_<TDPProfile>::Type TIsLocal; 283 284 // If InitialColumn -> Zero, Vertical | Zero, Vertical | Zero // Within the algorithm we need to define the first row as only one cell if it is no initial column 285 // If InnerColumn -> UpperDiagonal, All, LowerDiagonal 286 // If FinalColumn -> UpperDiagonal, All, LowerDiagonal 287 288 typedef typename If<IsSameType<TColumnType, DPInitialColumn>, RecursionDirectionZero, RecursionDirectionUpperDiagonal>::Type TRecursionTypeFirstCell_; 289 typedef typename If<IsSameType<TColumnType, DPInitialColumn>, 290 typename If<IsFreeEndGap_<TDPProfile, DPFirstColumn>, RecursionDirectionZero, RecursionDirectionVertical>::Type, 291 RecursionDirectionAll>::Type TRecursionTypeInnerCell_; 292 typedef typename If<IsSameType<TColumnType, DPInitialColumn>, 293 typename If<IsFreeEndGap_<TDPProfile, DPFirstColumn>, RecursionDirectionZero, RecursionDirectionVertical>::Type, 294 RecursionDirectionLowerDiagonal>::Type TRecursionTypeLastCell_; 295 296 // If Local 297 // If InitialColumn -> True, True, True 298 // If InnerColumn -> True, True, True 299 // If FinalColumn -> True, True, True 300 301 // If Global 302 // If InitialColumn -> False, False, False 303 // If InnerColumn -> False, False, False 304 // If FinalColumn -> False | True, False | True, False | True (if DPLastColumn True) 305 306 typedef typename If<Or<IsLocalAlignment_<TDPProfile>, 307 And<IsSameType<TColumnType, DPFinalColumn>, 308 IsFreeEndGap_<TDPProfile, DPLastColumn> > 309 >, True, False>::Type TrackFlagFirstCell_; 310 typedef typename If<Or<IsLocalAlignment_<TDPProfile>, 311 And<IsSameType<TColumnType, DPFinalColumn>, 312 IsFreeEndGap_<TDPProfile, DPLastColumn> > 313 >, True, False>::Type TrackFlagInnerCell_; 314 typedef typename If<Or<IsLocalAlignment_<TDPProfile>, 315 And<IsSameType<TColumnType, DPFinalColumn>, 316 IsFreeEndGap_<TDPProfile, DPLastColumn> > 317 >, True, False>::Type TrackFlagLastCell_; 318 319 typedef DPMetaCell_<TRecursionTypeFirstCell_, TrackFlagFirstCell_> TFirstCell_; 320 typedef DPMetaCell_<TRecursionTypeInnerCell_, TrackFlagInnerCell_> TInnerCell_; 321 typedef DPMetaCell_<TRecursionTypeLastCell_, TrackFlagLastCell_> TLastCell_; 322 }; 323 324 // ---------------------------------------------------------------------------- 325 // Class DPMetaColumn_ [PartialColumnBottom] 326 // ---------------------------------------------------------------------------- 327 328 template <typename TDPProfile, typename TColumnType> 329 struct DPMetaColumn_<TDPProfile, MetaColumnDescriptor<TColumnType, PartialColumnBottom> > 330 { 331 typedef typename IsLocalAlignment_<TDPProfile>::Type TIsLocal; 332 333 // If InitialColumn -> Zero, Vertical | Zero, Vertical | Zero // Within the algorithm we need to define the first row as only one cell if it is no initial column 334 // If InnerColumn -> UpperDiagonal, All, All 335 // If FinalColumn -> UpperDiagonal, All, All 336 337 typedef typename If<IsSameType<TColumnType, DPInitialColumn>, RecursionDirectionZero, RecursionDirectionUpperDiagonal>::Type TRecursionTypeFirstCell_; 338 typedef typename If<IsSameType<TColumnType, DPInitialColumn>, 339 typename If<IsFreeEndGap_<TDPProfile, DPFirstColumn>, RecursionDirectionZero, RecursionDirectionVertical>::Type, 340 RecursionDirectionAll>::Type TRecursionTypeInnerCell_; 341 typedef typename If<IsSameType<TColumnType, DPInitialColumn>, 342 typename If<IsFreeEndGap_<TDPProfile, DPFirstColumn>, RecursionDirectionZero, RecursionDirectionVertical>::Type, 343 RecursionDirectionAll>::Type TRecursionTypeLastCell_; 344 345 // If Local 346 // If InitialColumn -> True, True, True 347 // If InnerColumn -> True, True, True 348 // If FinalColumn -> True, True, True 349 350 // If Global 351 // If InitialColumn -> False, False, False | True (if DPLastRow) 352 // If InnerColumn -> False, False, False | True (if DPLastRow) 353 // If FinalColumn -> False | True, False | True (if DPLastColumn), True (last is always true) 354 355 typedef typename If<Or<IsLocalAlignment_<TDPProfile>, 356 And<IsSameType<TColumnType, DPFinalColumn>, 357 IsFreeEndGap_<TDPProfile, DPLastColumn> > 358 >, True, False>::Type TrackFlagFirstCell_; 359 typedef typename If<Or<IsLocalAlignment_<TDPProfile>, 360 And<IsSameType<TColumnType, DPFinalColumn>, 361 IsFreeEndGap_<TDPProfile, DPLastColumn> > 362 >, True, False>::Type TrackFlagInnerCell_; 363 typedef typename If<Or<IsLocalAlignment_<TDPProfile>, 364 Or<IsSameType<TColumnType, DPFinalColumn>, 365 IsFreeEndGap_<TDPProfile, DPLastRow> > >, True, False>::Type TrackFlagLastCell_; 366 367 typedef DPMetaCell_<TRecursionTypeFirstCell_, TrackFlagFirstCell_> TFirstCell_; 368 typedef DPMetaCell_<TRecursionTypeInnerCell_, TrackFlagInnerCell_> TInnerCell_; 369 typedef DPMetaCell_<TRecursionTypeLastCell_, TrackFlagLastCell_> TLastCell_; 370 }; 371 372 373 // ---------------------------------------------------------------------------- 374 // Metafunction GetRecursionDirection_ 375 // ---------------------------------------------------------------------------- 376 377 // Returns the type of recursion for a given DPMetaCell object. 378 template <typename TMetaCell> 379 struct GetRecursionDirection_ 380 { 381 typedef Nothing Type; 382 }; 383 384 template <typename TRecursionDirection, typename TTraceFlag> 385 struct GetRecursionDirection_<DPMetaCell_<TRecursionDirection, TTraceFlag> > 386 { 387 typedef TRecursionDirection Type; 388 }; 389 390 // ---------------------------------------------------------------------------- 391 // Metafunction RecursionDirection_ 392 // ---------------------------------------------------------------------------- 393 394 // Returns the type of recursion for a given DPMetaColumn object and a given cell specifier. 395 template <typename TDPMetaColumn, typename TCellDescriptor> 396 struct RecursionDirection_ {}; 397 398 template <typename TDPMetaColumn> 399 struct RecursionDirection_<TDPMetaColumn, FirstCell> 400 { 401 typedef typename GetRecursionDirection_<typename TDPMetaColumn::TFirstCell_>::Type Type; 402 }; 403 404 template <typename TDPMetaColumn> 405 struct RecursionDirection_<TDPMetaColumn, InnerCell> 406 { 407 typedef typename GetRecursionDirection_<typename TDPMetaColumn::TInnerCell_>::Type Type; 408 }; 409 410 template <typename TDPMetaColumn> 411 struct RecursionDirection_<TDPMetaColumn, LastCell> 412 { 413 typedef typename GetRecursionDirection_<typename TDPMetaColumn::TLastCell_>::Type Type; 414 }; 415 416 // ---------------------------------------------------------------------------- 417 // Metafunction IsTrackingEnabled_ 418 // ---------------------------------------------------------------------------- 419 420 // Returns an object that evaluates to true if for a given cell description the 421 // tracking was enabled. Otherwise the object evaluates to false. 422 template <typename TMetaCell> 423 struct IsTrackingEnabled_ : 424 False {}; 425 426 template <typename TRecursionDirection> 427 struct IsTrackingEnabled_<DPMetaCell_<TRecursionDirection, True> >: 428 True {}; 429 430 431 template <typename TDPMetaColumn, typename TCellDescriptor> 432 struct TrackingEnabled_ : 433 False {}; 434 435 template <typename TDPMetaColumn> 436 struct TrackingEnabled_<TDPMetaColumn, FirstCell>: 437 IsTrackingEnabled_<typename TDPMetaColumn::TFirstCell_>{}; 438 439 template <typename TDPMetaColumn> 440 struct TrackingEnabled_<TDPMetaColumn, InnerCell>: 441 IsTrackingEnabled_<typename TDPMetaColumn::TInnerCell_>{}; 442 443 template <typename TDPMetaColumn> 444 struct TrackingEnabled_<TDPMetaColumn, LastCell>: 445 IsTrackingEnabled_<typename TDPMetaColumn::TLastCell_>{}; 446 447 // ============================================================================ 448 // Functions 449 // ============================================================================ 450 451 } // namespace seqan 452 453 #endif // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_META_INFO_H_ 454