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 class stores the band information as well as the meta-inforation, 35 // whether a band was selected or not. 36 // ========================================================================== 37 38 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_BAND_H_ 39 #define SEQAN_INCLUDE_SEQAN_ALIGN_DP_BAND_H_ 40 41 namespace seqan 42 { 43 44 // ============================================================================ 45 // Forwards 46 // ============================================================================ 47 48 // ============================================================================ 49 // Tags, Classes, Enums 50 // ============================================================================ 51 52 /*! 53 * @defgroup DPBandSwitch 54 * @brief Tags used to switch between banded and unbanded alignment. 55 * 56 * @tag DPBandSwitch#BandOn 57 * @brief Switches banded alignment on. 58 * @headerfile <seqan/align.h> 59 * @signature struct BandOn_; 60 * @signature typedef Tag<BandOn_> BandOn; 61 * 62 * @tag DPBandSwitch#BandOff 63 * @brief Switches banded alignment off. 64 * @headerfile <seqan/align.h> 65 * @signature struct BandOff_; 66 * @signature typedef Tag<BandOff_> BandOff; 67 */ 68 69 // ---------------------------------------------------------------------------- 70 // Tag BandOff 71 // ---------------------------------------------------------------------------- 72 73 // Used when computing unbanded alignments. 74 struct BandOff_; 75 typedef Tag<BandOff_> BandOff; 76 77 // ---------------------------------------------------------------------------- 78 // Tag BandOn 79 // ---------------------------------------------------------------------------- 80 81 // Used when computing banded alignments. 82 struct BandOn_; 83 typedef Tag<BandOn_> BandOn; 84 85 // ---------------------------------------------------------------------------- 86 // Class DPBandConfig 87 // ---------------------------------------------------------------------------- 88 89 /*! 90 * @class DPBandConfig 91 * @headerfile <seqan/align.h> 92 * @brief Simple class to configure banded alignments. 93 * 94 * @signature template <typename TSwitch> 95 * class DPBandConfig<TSwitch>; 96 * 97 * @tparam TSwitch Tag to switch between banded and unbanded alignments. 98 * One of @link DPBandSwitch @endlink. Defaults to @link DPBandSwitch#BandOff @endlink. 99 * 100 * To compute banded alignments use @link DPBand @endlink as a shortcut for the <tt>DPBandConfig</tt> with 101 * band switched on. 102 */ 103 104 // Simple band class. 105 template <typename TSpec = BandOff> 106 struct DPBandConfig {}; 107 108 // ---------------------------------------------------------------------------- 109 // Class DPBandConfig [BandOff] 110 // ---------------------------------------------------------------------------- 111 112 // The specialization when using no band. 113 // Per default the member variables _lowerDiagonal and _upperDiagonal are 114 // always 0. 115 template <> 116 struct DPBandConfig<BandOff> 117 { 118 typedef int TPosition; 119 }; 120 121 // ---------------------------------------------------------------------------- 122 // Class DPBandConfig [BandOn] 123 // ---------------------------------------------------------------------------- 124 125 // The specialization when using a band. 126 // On construction the diagonals are set to 0. 127 template <> 128 struct DPBandConfig<BandOn> 129 { 130 typedef int TPosition; 131 132 int _lowerDiagonal; 133 int _upperDiagonal; 134 135 /*! 136 * @fn DPBandConfig::DPBandConfig 137 * @brief Constructor. 138 * 139 * @signature DPBandConfig<TSwitch>(); 140 * @signature DPBandConfig<BandOn>(lowerDiag, upperDiag); 141 * 142 * @tparam TSwitch Tag to switch between banded and unbanded alignments. One of @link DPBandSwitch @endlink. 143 * The second constructor is only supported when @link DPBandConfig @endlink is specialized with 144 * @link DPBandSwitch#BandOn @endlink. 145 * 146 * @param lowerDiag The value for the lower diagonal of the band. 147 * @param upperDiag The value for the upper diagonal of the band. 148 * 149 * A negative value for the diagonals indicates an intersection of the diagonal with the vertical sequence (y-axis) 150 * and a positive value indicates an intersection with the horizontal sequence (x-axis). 151 * The value of the lower diagonal has to compare less or equal to the value of the upper diagonal. 152 */ 153 154 DPBandConfig() : 155 _lowerDiagonal(0), _upperDiagonal(0) {} 156 157 DPBandConfig(int lowerDiagonal, int upperDiagonal) : 158 _lowerDiagonal(lowerDiagonal), _upperDiagonal(upperDiagonal) 159 { 160 SEQAN_ASSERT_LEQ(lowerDiagonal, upperDiagonal); 161 } 162 }; 163 164 /*! 165 * @typedef DPBand 166 * @headerfile <seqan/align.h> 167 * @brief Global typedef used for @link DPBandConfig @endlink specialized with @link DPBandSwitch#BandOn @endlink. 168 * 169 * @signature typedef DPBandConfig<BandOn> DPBand; 170 */ 171 172 // Typedef for Band. 173 typedef DPBandConfig<BandOn> DPBand; 174 175 // ============================================================================ 176 // Metafunctions 177 // ============================================================================ 178 179 /*! 180 * @mfn DPBandConfig#Position 181 * @headerfile <seqan/align.h> 182 * @brief Metafunction returning the position type. 183 * 184 * @signature typename Position<T>::Type; 185 * 186 * @tparam T The type @link DPBandConfig @endlink to query the position type for. 187 * @return TPosition The position type. 188 */ 189 190 // ---------------------------------------------------------------------------- 191 // Metafunction Position 192 // ---------------------------------------------------------------------------- 193 194 template <typename T> 195 struct Position<DPBandConfig<T> > 196 { 197 typedef typename DPBandConfig<T>::TPosition Type; 198 }; 199 200 template <typename T> 201 struct Position<DPBandConfig<T> const>: 202 Position<DPBandConfig<T> >{}; 203 204 // ---------------------------------------------------------------------------- 205 // Metafunction Size 206 // ---------------------------------------------------------------------------- 207 208 /*! 209 * @mfn DPBandConfig#Size 210 * @headerfile <seqan/align.h> 211 * @brief Metafunction returning the size type. 212 * 213 * @signature typename Size<T>::Type; 214 * 215 * @tparam T The type @link DPBandConfig @endlink to query the size type for. 216 * @return TSize The size type. 217 */ 218 219 template <typename T> 220 struct Size<DPBandConfig<T> > 221 { 222 typedef unsigned Type; 223 }; 224 225 226 template <typename T> 227 struct Size<DPBandConfig<T> const>: 228 Size<DPBandConfig<T> >{}; 229 230 // ============================================================================ 231 // Functions 232 // ============================================================================ 233 234 // ---------------------------------------------------------------------------- 235 // Function setLowerDiagonal 236 // ---------------------------------------------------------------------------- 237 238 /*! 239 * @fn DPBandConfig#setLowerDiagonal 240 * @headerfile <seqan/align.h> 241 * @brief Sets the value of the lower diagonal. 242 * 243 * @signature setLowerDiagonal(obj, val); 244 * 245 * @param obj The object of type @link DPBandConfig @endlink to set the lower diagonal for. 246 * @param val The new value for the lower diagonal. 247 * 248 * @note If the band is switched off, this function defaults to no-op. 249 */ 250 251 inline void 252 setLowerDiagonal(DPBandConfig<BandOff> & /*dpBand*/, int /*newLowerDiagonal*/) 253 { 254 //no-op 255 } 256 257 inline void 258 setLowerDiagonal(DPBandConfig<BandOn> & dpBand, int newLowerDiagonal) 259 { 260 dpBand._lowerDiagonal = newLowerDiagonal; 261 } 262 263 // ---------------------------------------------------------------------------- 264 // Function lowerDiagonal 265 // ---------------------------------------------------------------------------- 266 267 /*! 268 * @fn DPBandConfig#lowerDiagonal 269 * @headerfile <seqan/align.h> 270 * @brief Returns the value of the lower diagonal. 271 * 272 * @signature TPosition lowerDiagonal(obj); 273 * 274 * @param obj The object of type @link DPBandConfig @endlink to query the lower diagonal for. 275 * 276 * @note If the band is switched off this function always returns 0. 277 * @return TPosition The value of the lower diagonal. 278 */ 279 280 inline Position<DPBandConfig<BandOff> >::Type 281 lowerDiagonal(DPBandConfig<BandOff> const & /*dpBand*/) 282 { 283 return 0; 284 } 285 286 template <typename TSwitch> 287 inline typename Position<DPBandConfig<BandOff> >::Type 288 lowerDiagonal(DPBandConfig<TSwitch> const & dpBand) 289 { 290 return dpBand._lowerDiagonal; 291 } 292 293 // ---------------------------------------------------------------------------- 294 // Function setUpperDiagonal 295 // ---------------------------------------------------------------------------- 296 297 /*! 298 * @fn DPBandConfig#setUpperDiagonal 299 * @headerfile <seqan/align.h> 300 * @brief Sets the value of the upper diagonal. 301 * 302 * @signature setUpperDiagonal(obj, val); 303 * 304 * @param obj The object of type @link DPBandConfig @endlink to set the upper diagonal for. 305 * @param val The new value for the upper diagonal. 306 * 307 * @note If the band is switched off, this function defaults to no-op. 308 */ 309 310 inline void 311 setUpperDiagonal(DPBandConfig<BandOff> & /*dpBand*/, int /*newUpperDiagonal*/) 312 { 313 //no-op 314 } 315 316 inline void 317 setUpperDiagonal(DPBandConfig<BandOn> & dpBand, int newUpperDiagonal) 318 { 319 dpBand._upperDiagonal = newUpperDiagonal; 320 } 321 322 // ---------------------------------------------------------------------------- 323 // Function upperDiagonal 324 // ---------------------------------------------------------------------------- 325 326 /*! 327 * @fn DPBandConfig#upperDiagonal 328 * @headerfile <seqan/align.h> 329 * @brief Returns the value of the upper diagonal. 330 * 331 * @signature TPosition upperDiagonal(obj); 332 * 333 * @param obj The object of type @link DPBandConfig @endlink to query the upper diagonal for. 334 * 335 * @note If the band is switched off this function always returns 0. 336 * @return TPosition The value of the upper diagonal. 337 */ 338 339 inline Position<DPBandConfig<BandOff> >::Type 340 upperDiagonal(DPBandConfig<BandOff> const & /*dpBand*/) 341 { 342 return 0; 343 } 344 345 template <typename TSwitch> 346 inline typename Position<DPBandConfig<BandOn> >::Type 347 upperDiagonal(DPBandConfig<TSwitch> const & dpBand) 348 { 349 return dpBand._upperDiagonal; 350 } 351 352 // ---------------------------------------------------------------------------- 353 // Function bandSize() 354 // ---------------------------------------------------------------------------- 355 356 /*! 357 * @fn DPBandConfig#bandSize 358 * @headerfile <seqan/align.h> 359 * @brief Returns the size of the band. 360 * 361 * @signature TSize bandSize(obj); 362 * 363 * @param obj The object of type @link DPBandConfig @endlink to query the band size for. 364 * 365 * @note If the band is switched off this function always returns 0. 366 * @return TSize The number of diagonals covered by the band. 367 */ 368 369 inline Size<DPBandConfig<BandOff> >::Type 370 bandSize(DPBandConfig<BandOff> const &) 371 { 372 return 0; 373 } 374 375 template <typename TSwitch> 376 inline typename Size<DPBandConfig<TSwitch> >::Type 377 bandSize(DPBandConfig<TSwitch> const & band) 378 { 379 return upperDiagonal(band) - lowerDiagonal(band) + 1; 380 } 381 382 } // namespace seqan 383 384 #endif // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_BAND_H_ 385