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: Rene Rahn <rene.rahn@fu-berlin.de> 33 // ========================================================================== 34 // 35 // The TraceSegment structure is used to store the traceback in a common 36 // structure such that we can easiely adapt them afterwards in the 37 // user-defined structure, such as Align or AlignmentGraph objects. 38 // ========================================================================== 39 40 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_TRACE_SEGMENT_H_ 41 #define SEQAN_INCLUDE_SEQAN_ALIGN_DP_TRACE_SEGMENT_H_ 42 43 namespace seqan { 44 45 // ============================================================================ 46 // Forwards 47 // ============================================================================ 48 49 // ============================================================================ 50 // Tags, Classes, Enums 51 // ============================================================================ 52 53 // ---------------------------------------------------------------------------- 54 // Class TraceSegment 55 // ---------------------------------------------------------------------------- 56 57 // TraceSegments are used as a common interface to all structures that can represent an alignment. 58 // 59 // See alignment_dp_traceback_adaptor.h to find methods for adaption. 60 template <typename TPosition, typename TSize> 61 class TraceSegment_ 62 { 63 public: 64 typedef typename TraceBitMap_<>::Type TTraceValue; 65 66 TPosition _horizontalBeginPos; // the begin position in horizontal dimension 67 TPosition _verticalBeginPos; // the begin position in vertical dimension 68 TSize _length; // the length of the segment 69 TTraceValue _traceValue; // the trace direction 70 TraceSegment_()71 TraceSegment_() : 72 _horizontalBeginPos(0), _verticalBeginPos(0), _length(0), _traceValue(TraceBitMap_<TTraceValue>::NONE){} 73 TraceSegment_(TraceSegment_ const & other)74 TraceSegment_(TraceSegment_ const & other) : 75 _horizontalBeginPos(other._horizontalBeginPos), 76 _verticalBeginPos(other._verticalBeginPos), 77 _length(other._length), 78 _traceValue(other._traceValue) {} 79 TraceSegment_(TPosition const & horizontalBeginPos,TPosition const & verticalBeginPos,TSize const & length,TTraceValue const & traceValue)80 TraceSegment_(TPosition const & horizontalBeginPos, TPosition const & verticalBeginPos, TSize const & length, 81 TTraceValue const & traceValue) : 82 _horizontalBeginPos(horizontalBeginPos), 83 _verticalBeginPos(verticalBeginPos), 84 _length(length), 85 _traceValue(traceValue) {} 86 87 TraceSegment_ & 88 operator=(TraceSegment_ const & other) 89 { 90 if (this != &other) 91 { 92 _horizontalBeginPos = other._horizontalBeginPos; 93 _verticalBeginPos = other._verticalBeginPos; 94 _length = other._length; 95 _traceValue = other._traceValue; 96 } 97 return *this; 98 } 99 100 }; 101 102 103 // ============================================================================ 104 // Metafunctions 105 // ============================================================================ 106 107 // ---------------------------------------------------------------------------- 108 // Metafunction Position 109 // ---------------------------------------------------------------------------- 110 111 template <typename TPosition, typename TSize> 112 struct Position<TraceSegment_<TPosition, TSize> > 113 { 114 typedef TPosition Type; 115 }; 116 117 template <typename TPosition, typename TSize> 118 struct Position<TraceSegment_<TPosition, TSize> const>: 119 Position<TraceSegment_<TPosition, TSize> >{}; 120 121 // ---------------------------------------------------------------------------- 122 // Metafunction Size 123 // ---------------------------------------------------------------------------- 124 125 template <typename TPosition, typename TSize> 126 struct Size<TraceSegment_<TPosition, TSize> > 127 { 128 typedef TSize Type; 129 }; 130 131 template <typename TPosition, typename TSize> 132 struct Size<TraceSegment_<TPosition, TSize> const>: 133 Size<TraceSegment_<TPosition, TSize> >{}; 134 135 // ============================================================================ 136 // Functions 137 // ============================================================================ 138 139 // ---------------------------------------------------------------------------- 140 // Function _getBeginHorizontal() 141 // ---------------------------------------------------------------------------- 142 143 // The begin position of the segment in horizontal dimension. 144 template <typename TPosition, typename TSize> 145 inline TPosition 146 _getBeginHorizontal(TraceSegment_<TPosition, TSize> const & traceSegment) 147 { 148 return traceSegment._horizontalBeginPos; 149 } 150 151 // ---------------------------------------------------------------------------- 152 // Function _getBeginVertical() 153 // ---------------------------------------------------------------------------- 154 155 // The begin position of the segment in vertical dimension. 156 template <typename TPosition, typename TSize> 157 inline TPosition 158 _getBeginVertical(TraceSegment_<TPosition, TSize> const & traceSegment) 159 { 160 return traceSegment._verticalBeginPos; 161 } 162 163 // ---------------------------------------------------------------------------- 164 // Function _getEndHorizontal() 165 // ---------------------------------------------------------------------------- 166 167 // The end position of the segment in horizontal dimension. 168 template <typename TPosition, typename TSize> 169 inline TPosition 170 _getEndHorizontal(TraceSegment_<TPosition, TSize> const & traceSegment) 171 { 172 typedef typename std::remove_const<decltype(traceSegment._traceValue)>::type TTraceValue; 173 if (traceSegment._traceValue & (TraceBitMap_<TTraceValue>::HORIZONTAL | TraceBitMap_<TTraceValue>::DIAGONAL)) 174 { 175 return traceSegment._horizontalBeginPos + traceSegment._length; 176 } 177 return traceSegment._horizontalBeginPos; 178 } 179 180 // ---------------------------------------------------------------------------- 181 // Function _getEndVertical() 182 // ---------------------------------------------------------------------------- 183 184 // The end position of the segment in vertical dimension. 185 template <typename TPosition, typename TSize> 186 inline TPosition 187 _getEndVertical(TraceSegment_<TPosition, TSize> const & traceSegment) 188 { 189 typedef typename std::remove_const<decltype(traceSegment._traceValue)>::type TTraceValue; 190 if (traceSegment._traceValue & (TraceBitMap_<TTraceValue>::VERTICAL | TraceBitMap_<TTraceValue>::DIAGONAL)) 191 { 192 return traceSegment._verticalBeginPos + traceSegment._length; 193 } 194 return traceSegment._verticalBeginPos; 195 } 196 197 // ---------------------------------------------------------------------------- 198 // Function _getTraceValue() 199 // ---------------------------------------------------------------------------- 200 201 // The end position of the segment in vertical dimension. 202 template <typename TPosition, typename TSize> 203 inline typename TraceSegment_<TPosition, TSize>::TTraceValue 204 _getTraceValue(TraceSegment_<TPosition, TSize> const & traceSegment) 205 { 206 return traceSegment._traceValue; 207 } 208 209 // ---------------------------------------------------------------------------- 210 // Function length() 211 // ---------------------------------------------------------------------------- 212 213 // The length of the segment. 214 template <typename TPosition, typename TSize> 215 inline TSize 216 length(TraceSegment_<TPosition, TSize> const & traceSegment) 217 { 218 return traceSegment._length; 219 } 220 221 // ---------------------------------------------------------------------------- 222 // Function _setLength() 223 // ---------------------------------------------------------------------------- 224 225 // The length of the segment. 226 template <typename TPosition, typename TSize> 227 inline void 228 _setLength(TraceSegment_<TPosition, TSize> & traceSegment, TSize newLength) 229 { 230 traceSegment._length = newLength; 231 } 232 233 // ---------------------------------------------------------------------------- 234 // Function _translateTraceValue() 235 // ---------------------------------------------------------------------------- 236 237 // Translates the trace value into a human-readable format. 238 // 239 // Note, used for debugging reasons only. 240 template <typename TTraceValue> 241 String<char> _translateTraceValue(TTraceValue const & traceValue) 242 { 243 String<char> transcript; 244 245 if ((traceValue & TraceBitMap_<TTraceValue>::DIAGONAL) == TraceBitMap_<TTraceValue>::DIAGONAL) 246 append(transcript, 'D'); 247 if ((traceValue & TraceBitMap_<TTraceValue>::VERTICAL) == TraceBitMap_<TTraceValue>::VERTICAL) 248 append(transcript, 'V'); 249 if ((traceValue & TraceBitMap_<TTraceValue>::HORIZONTAL) == TraceBitMap_<TTraceValue>::HORIZONTAL) 250 append(transcript, 'H'); 251 if ((traceValue & TraceBitMap_<TTraceValue>::VERTICAL_OPEN) == TraceBitMap_<TTraceValue>::VERTICAL_OPEN) 252 append(transcript, 'v'); 253 if ((traceValue & TraceBitMap_<TTraceValue>::HORIZONTAL_OPEN) == TraceBitMap_<TTraceValue>::HORIZONTAL_OPEN) 254 append(transcript, 'h'); 255 if ((traceValue & TraceBitMap_<TTraceValue>::MAX_FROM_VERTICAL_MATRIX) == TraceBitMap_<TTraceValue>::MAX_FROM_VERTICAL_MATRIX) 256 append(transcript, '|'); 257 if ((traceValue & TraceBitMap_<TTraceValue>::MAX_FROM_HORIZONTAL_MATRIX) == TraceBitMap_<TTraceValue>::MAX_FROM_HORIZONTAL_MATRIX) 258 append(transcript, '-'); 259 260 if ((traceValue) == TraceBitMap_<TTraceValue>::NONE) 261 append(transcript, '0'); 262 return transcript; 263 } 264 265 // ---------------------------------------------------------------------------- 266 // Function oerpator<<() 267 // ---------------------------------------------------------------------------- 268 269 template <typename TStream, typename TSize, typename TPosition> 270 TStream & operator<<(TStream & stream, TraceSegment_<TSize, TPosition> const & traceSegment) 271 { 272 stream << _translateTraceValue(traceSegment._traceValue) << "-"; 273 stream << "(" << traceSegment._horizontalBeginPos << ", " << traceSegment._verticalBeginPos << ", " << 274 traceSegment._length << ")"; 275 return stream; 276 } 277 278 // ---------------------------------------------------------------------------- 279 // Function oerpator==() 280 // ---------------------------------------------------------------------------- 281 282 template <typename TPosition, typename TSize> 283 inline bool operator==(TraceSegment_<TPosition, TSize> const & left, TraceSegment_<TPosition, TSize> const & right) 284 { 285 if (left._horizontalBeginPos != right._horizontalBeginPos) 286 return false; 287 288 if (left._verticalBeginPos != right._verticalBeginPos) 289 return false; 290 291 if (left._length != right._length) 292 return false; 293 294 if (left._traceValue != right._traceValue) 295 return false; 296 297 return true; 298 } 299 300 // ---------------------------------------------------------------------------- 301 // Function oerpator!=() 302 // ---------------------------------------------------------------------------- 303 304 template <typename TPosition, typename TSize> 305 inline bool operator!=(TraceSegment_<TPosition, TSize> const & left, TraceSegment_<TPosition, TSize> const & right) 306 { 307 return !(left == right); 308 } 309 310 // ---------------------------------------------------------------------------- 311 // Function recordSegment() 312 // ---------------------------------------------------------------------------- 313 314 // Records a segment given the horizontal and vertical begin position, the length, 315 // and the corrsponding trace value. 316 // 317 // The first parameter is the container the segment is recorded to. 318 template <typename TTraceSegments, typename TPositionH, typename TPositionV, typename TSize, typename TTraceValue> 319 inline void _recordSegment(TTraceSegments & traceSegments, 320 TPositionH const & horizontalBeginPos, 321 TPositionV const & verticalBeginPos, 322 TSize const & segmentLength, 323 TTraceValue const & traceValue) 324 { 325 typedef typename Value<TTraceSegments>::Type TTraceSegment; 326 327 if (segmentLength == 0) 328 return; // we don't store empty segments 329 330 if (traceValue & TraceBitMap_<TTraceValue>::DIAGONAL) 331 appendValue(traceSegments, TTraceSegment(horizontalBeginPos, verticalBeginPos, segmentLength, TraceBitMap_<TTraceValue>::DIAGONAL)); 332 else if (traceValue & TraceBitMap_<TTraceValue>::VERTICAL) 333 appendValue(traceSegments, TTraceSegment(horizontalBeginPos, verticalBeginPos, segmentLength, TraceBitMap_<TTraceValue>::VERTICAL)); 334 else if (traceValue & TraceBitMap_<TTraceValue>::HORIZONTAL) 335 appendValue(traceSegments, TTraceSegment(horizontalBeginPos, verticalBeginPos, segmentLength, TraceBitMap_<TTraceValue>::HORIZONTAL)); 336 // everything else is not tracked. 337 } 338 339 } // namespace seqan 340 341 #endif // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_TRACE_SEGMENT_H_ 342