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 // Declares the DPCell, which is used to substitute the score of each cell. 35 // Thus, we are able to add additional features to an alignment cell such as 36 // a flag to indicate if it is forbidden or not. Or to store two additional 37 // scores necessary for the affine gap function. 38 // ========================================================================== 39 40 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_CELL_H_ 41 #define SEQAN_INCLUDE_SEQAN_ALIGN_DP_CELL_H_ 42 43 namespace seqan { 44 45 // ============================================================================ 46 // Forwards 47 // ============================================================================ 48 49 // ============================================================================ 50 // Tags, Classes, Enums 51 // ============================================================================ 52 53 // ---------------------------------------------------------------------------- 54 // Class DPCell_ 55 // ---------------------------------------------------------------------------- 56 57 // Used to store the score of a particular cell of the score matrix. 58 // It can be specialized for linear and affine gap costs. 59 // For affine gap costs it stores the values of all three matrices at a particular 60 // position of the matrix. 61 template <typename TScoreValue, typename TGapCosts> 62 class DPCell_; 63 64 // ============================================================================ 65 // Metafunctions 66 // ============================================================================ 67 68 // ---------------------------------------------------------------------------- 69 // Metafunction Value 70 // ---------------------------------------------------------------------------- 71 72 template <typename TScoreValue, typename TGapCostFunction> 73 struct Value<DPCell_<TScoreValue, TGapCostFunction> > 74 { 75 typedef TScoreValue Type; 76 }; 77 78 template <typename TScoreValue, typename TGapCostFunction> 79 struct Value<DPCell_<TScoreValue, TGapCostFunction> const> 80 { 81 typedef TScoreValue const Type; 82 }; 83 84 // ---------------------------------------------------------------------------- 85 // Metafunction Reference 86 // ---------------------------------------------------------------------------- 87 88 template <typename TScoreValue, typename TGapCostFunction> 89 struct Reference<DPCell_<TScoreValue, TGapCostFunction> > 90 { 91 typedef TScoreValue & Type; 92 }; 93 94 template <typename TScoreValue, typename TGapCostFunction> 95 struct Reference<DPCell_<TScoreValue, TGapCostFunction> const> 96 { 97 typedef TScoreValue const & Type; 98 }; 99 100 // ---------------------------------------------------------------------------- 101 // Metafunction DPCellDefaultInfinity 102 // ---------------------------------------------------------------------------- 103 104 // Defines the default infinity value for a DPCell. 105 template <typename T> 106 struct DPCellDefaultInfinity 107 { 108 static const int VALUE; 109 }; 110 111 template <typename T> 112 const int DPCellDefaultInfinity<T>::VALUE = MinValue<int>::VALUE; 113 114 // We use the min value of the score type and shift it one bits to the left. This way we can use "infinity" without 115 // checking for it during the computation. 116 template <typename TScoreValue, typename TGapCostFunction> 117 struct DPCellDefaultInfinity<DPCell_<TScoreValue, TGapCostFunction> > 118 { 119 static const TScoreValue VALUE; 120 }; 121 122 template <typename TScoreValue, typename TGapCostFunction> 123 const TScoreValue DPCellDefaultInfinity<DPCell_<TScoreValue, TGapCostFunction> >::VALUE = MinValue<TScoreValue>::VALUE / 2; 124 125 template <typename TScoreValue, typename TGapCostFunction> 126 struct DPCellDefaultInfinity<DPCell_<TScoreValue, TGapCostFunction> const> : 127 public DPCellDefaultInfinity<DPCell_<TScoreValue, TGapCostFunction> >{}; 128 129 // ============================================================================ 130 // Functions 131 // ============================================================================ 132 133 // ---------------------------------------------------------------------------- 134 // Function _scoreOfCell 135 // ---------------------------------------------------------------------------- 136 137 // Returns the score value for a given cell. 138 template <typename TScoreValue, typename TGapCosts> 139 inline typename Reference<DPCell_<TScoreValue, TGapCosts> >::Type 140 _scoreOfCell(DPCell_<TScoreValue, TGapCosts> & dpCell) 141 { 142 return dpCell._score; 143 } 144 145 template <typename TScoreValue, typename TGapCosts> 146 inline typename Reference<DPCell_<TScoreValue, TGapCosts> const>::Type 147 _scoreOfCell(DPCell_<TScoreValue, TGapCosts> const & dpCell) 148 { 149 return dpCell._score; 150 } 151 152 // ---------------------------------------------------------------------------- 153 // Function _setScoreOfCell 154 // ---------------------------------------------------------------------------- 155 156 template <typename TScoreValue, typename TGapCosts> 157 inline void 158 _setScoreOfCell(DPCell_<TScoreValue, TGapCosts> & dpCell, TScoreValue const & newScore) 159 { 160 dpCell._score = newScore; 161 } 162 163 // ---------------------------------------------------------------------------- 164 // Function _verticalScoreOfCell() 165 // ---------------------------------------------------------------------------- 166 167 // Returns the score of the matrix for vertical-gaps of the given cell. 168 template <typename TScoreValue, typename TGapSpec> 169 inline typename Reference<DPCell_<TScoreValue, TGapSpec> >::Type 170 _verticalScoreOfCell(DPCell_<TScoreValue, TGapSpec> & dpCell) 171 { 172 return dpCell._score; 173 } 174 175 template <typename TScoreValue, typename TGapSpec> 176 inline typename Reference<DPCell_<TScoreValue, TGapSpec> const>::Type 177 _verticalScoreOfCell(DPCell_<TScoreValue, TGapSpec> const & dpCell) 178 { 179 return dpCell._score; 180 } 181 182 // ---------------------------------------------------------------------------- 183 // Function _setVerticalScoreOfCell() 184 // ---------------------------------------------------------------------------- 185 186 // Returns the score of the matrix for vertical-gaps of the given cell. 187 template <typename TScoreValue, typename TGapSpec> 188 inline void 189 _setVerticalScoreOfCell(DPCell_<TScoreValue, TGapSpec> & /*dpCell*/, TScoreValue const & /*newVerticalScore*/) 190 { 191 // no-op 192 } 193 194 // ---------------------------------------------------------------------------- 195 // Function _horizontalScoreOfCell() 196 // ---------------------------------------------------------------------------- 197 198 // Returns the score of the matrix for horizontal-gaps of the given cell. 199 template <typename TScoreValue, typename TGapSpec> 200 inline typename Reference<DPCell_<TScoreValue, TGapSpec> >::Type 201 _horizontalScoreOfCell(DPCell_<TScoreValue, TGapSpec> & dpCell) 202 { 203 return dpCell._score; 204 } 205 206 template <typename TScoreValue, typename TGapSpec> 207 inline typename Reference<DPCell_<TScoreValue, TGapSpec> const>::Type 208 _horizontalScoreOfCell(DPCell_<TScoreValue, TGapSpec> const & dpCell) 209 { 210 return dpCell._score; 211 } 212 213 // ---------------------------------------------------------------------------- 214 // Function _setHorizontalScoreOfCell() 215 // ---------------------------------------------------------------------------- 216 217 // Returns the score of the matrix for vertical-gaps of the given cell. 218 template <typename TScoreValue, typename TGapSpec> 219 inline void 220 _setHorizontalScoreOfCell(DPCell_<TScoreValue, TGapSpec> & /*dpCell*/, TScoreValue const & /*newHorizontalScore*/) 221 { 222 // no-op 223 } 224 225 // ---------------------------------------------------------------------------- 226 // Function setGapExtension() 227 // ---------------------------------------------------------------------------- 228 229 template <typename TScoreValue, typename TGapSpec, typename TF1, typename TF2> 230 inline void 231 setGapExtension(DPCell_<TScoreValue, TGapSpec> & /*dpCell*/, TF1 , TF2) 232 { 233 // no-op 234 } 235 236 } // namespace seqan 237 238 #endif // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_CELL_H_ 239