1 // ========================================================================== 2 // SeqAn - The Library for Sequence Analysis 3 // ========================================================================== 4 // Copyright (c) 2006-2018, 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: Hannes Hauswedell <hauswedell@mi.fu-berlin.de> 33 // ========================================================================== 34 // This file contains routines to extend an existing Align object 35 // ========================================================================== 36 37 #ifndef INCLUDE_SEQAN_ALIGN_DP_SCOUT_EXTEND_H_ 38 #define INCLUDE_SEQAN_ALIGN_DP_SCOUT_EXTEND_H_ 39 40 namespace seqan { 41 42 // ============================================================================ 43 // Forwards 44 // ============================================================================ 45 46 // ============================================================================ 47 // Tags, Classes, Enums 48 // ============================================================================ 49 50 // ---------------------------------------------------------------------------- 51 // Tag XDropScout. 52 // ---------------------------------------------------------------------------- 53 54 template <typename TScoreValue> 55 struct XDrop_ 56 { 57 }; 58 59 // ---------------------------------------------------------------------------- 60 // Class DPScoutState_ 61 // ---------------------------------------------------------------------------- 62 63 template <typename TScoreValue> 64 class DPScoutState_<Terminator_<XDrop_<TScoreValue> > > 65 { 66 public: 67 TScoreValue const terminationThreshold; 68 TScoreValue columnMax; 69 DPScoutState_()70 DPScoutState_() : 71 terminationThreshold(std::numeric_limits<TScoreValue>::max()), 72 columnMax(std::numeric_limits<TScoreValue>::min()) 73 { 74 } 75 DPScoutState_(TScoreValue const & _terminationThreshold)76 DPScoutState_(TScoreValue const & _terminationThreshold) : 77 terminationThreshold(_terminationThreshold), 78 columnMax(std::numeric_limits<TScoreValue>::min()) 79 { 80 } 81 }; 82 83 84 // ============================================================================ 85 // Metafunctions 86 // ============================================================================ 87 88 // overrides for AligExtend XDrop case 89 template <typename TScoreValue> 90 struct HasTerminationCriterium_<AlignExtend_<XDrop_<TScoreValue> > > : True {}; 91 92 template <typename TScoreValue, typename TSpec> 93 struct ScoutSpecForAlignmentAlgorithm_<AlignExtend_<XDrop_<TScoreValue> >, DPScoutState_<TSpec> > 94 { 95 typedef Terminator_<XDrop_<TScoreValue> > Type; 96 }; 97 98 template <typename TScoreValue, typename TSpec> 99 struct ScoutSpecForAlignmentAlgorithm_<AlignExtend_<XDrop_<TScoreValue> > const, DPScoutState_<TSpec> > 100 { 101 typedef Terminator_<XDrop_<TScoreValue> > Type; 102 }; 103 104 template <typename TDPCell> 105 struct ScoutStateSpecForScout_< 106 DPScout_< 107 TDPCell, Terminator_<XDrop_< typename Value<TDPCell>::Type> > > > 108 { 109 typedef Terminator_<XDrop_<typename Value<TDPCell>::Type> > Type; 110 }; 111 112 // ============================================================================ 113 // Functions 114 // ============================================================================ 115 116 // ---------------------------------------------------------------------------- 117 // Function _scoutBestScore() [DPScout_] 118 // ---------------------------------------------------------------------------- 119 120 // NOTE: The original code here used Value<TDPCell>::Type instead of TDPCellValue but this caused ambiguous call 121 // errors in MSVC. 122 123 template <typename TDPCell, typename TTraceMatrixNavigator, typename TDPCellValue, typename TIsLastColumn> 124 inline void 125 _scoutBestScore(DPScout_<TDPCell, Terminator_<XDrop_<TDPCellValue> > > & dpScout, 126 TDPCell const & activeCell, 127 TTraceMatrixNavigator const & navigator, 128 TIsLastColumn const & /**/, 129 False const & /*IsLastRow*/) 130 { 131 typedef typename Value<TDPCell>::Type TScoreValue; 132 typedef XDrop_<TScoreValue> TXDrop; 133 typedef DPScout_<TDPCell, Terminator_<TXDrop> > TDPScout; 134 typedef typename TDPScout::TBase TParent; 135 136 // global maximum 137 _scoutBestScore(static_cast<TParent &>( dpScout ), activeCell, navigator); 138 139 // column maximum 140 dpScout.state->columnMax = _max(dpScout.state->columnMax, _scoreOfCell(activeCell)); 141 } 142 143 template <typename TDPCell, typename TTraceMatrixNavigator, typename TDPCellValue, typename TIsLastColumn> 144 inline void 145 _scoutBestScore(DPScout_<TDPCell, Terminator_<XDrop_<TDPCellValue> > > & dpScout, 146 TDPCell const & activeCell, 147 TTraceMatrixNavigator const & navigator, 148 TIsLastColumn const & /**/, 149 True const & /*IsLastRow*/) 150 { 151 typedef typename Value<TDPCell>::Type TScoreValue; 152 153 _scoutBestScore(dpScout, activeCell, navigator, TIsLastColumn(), False()); 154 155 // check termination condition 156 if (_scoreOfCell(dpScout._maxScore) - dpScout.state->columnMax >= dpScout.state->terminationThreshold) 157 terminateScout(dpScout); 158 else // reset columMax at end of column 159 dpScout.state->columnMax = std::numeric_limits<TScoreValue>::min(); 160 } 161 162 // ---------------------------------------------------------------------------- 163 // Function _scoutBestScore() [DPScout_] 164 // ---------------------------------------------------------------------------- 165 166 // Computes the score and tracks it if enabled. 167 template <typename TDPScout, typename TTraceMatrixNavigator, 168 typename TDPCell, 169 typename TScoreValue, typename TGapCosts, 170 typename TSequenceHValue, typename TSequenceVValue, typename TScoringScheme, typename TColumnDescriptor, 171 typename TCellDescriptor, typename TTraceback> 172 inline void 173 _computeCell(TDPScout & scout, 174 TTraceMatrixNavigator & traceMatrixNavigator, 175 TDPCell & current, 176 TDPCell & diagonal, 177 TDPCell const & horizontal, 178 TDPCell & vertical, 179 TSequenceHValue const & seqHVal, 180 TSequenceVValue const & seqVVal, 181 TScoringScheme const & scoringScheme, 182 TColumnDescriptor const &, 183 TCellDescriptor const &, // One of FirstCell, InnerCell or LastCell. 184 DPProfile_<AlignExtend_<XDrop_<TScoreValue> >, TGapCosts, 185 TTraceback> const &) 186 { 187 typedef DPProfile_<AlignExtend_<XDrop_<TScoreValue> >, TGapCosts, TTraceback> TDPProfile; 188 typedef DPMetaColumn_<TDPProfile, TColumnDescriptor> TMetaColumn; 189 190 assignValue(traceMatrixNavigator, _computeScore(current, diagonal, horizontal, vertical, 191 seqHVal, seqVVal, scoringScheme, 192 typename RecursionDirection_<TMetaColumn, TCellDescriptor>::Type(), 193 TDPProfile())); 194 if (TrackingEnabled_<TMetaColumn, TCellDescriptor>::VALUE) 195 { 196 typedef typename IsSameType< typename TColumnDescriptor::TColumnProperty, DPFinalColumn>::Type TIsLastColumn; 197 198 // the following is the only change to the regular _computeCell: 199 // for the evaluation of the termination criterium we treat 200 // all lastCells as lastRows 201 _setVerticalScoreOfCell(current, _verticalScoreOfCell(vertical)); 202 typedef typename IsSameType<TCellDescriptor, LastCell>::Type TIsLastRow; 203 _scoutBestScore(scout, current, traceMatrixNavigator, TIsLastColumn(), TIsLastRow()); 204 } 205 } 206 207 } // namespace seqan 208 209 #endif // #ifndef INCLUDE_SEQAN_ALIGN_DP_SCOUT_EXTEND_H_ 210