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: Manuel Holtgrewe <manuel.holtgrewe@fu-berlin.de>
33 // Author: Tobias Rausch <rausch@embl.de>
34 // ==========================================================================
35 // AlignTraceback object for storing the alignment traceback results.
36 //
37 // The _pump* functions for converting from AlignTrace to Gaps and Fragment
38 // String objects are defined where Gaps / the Alignment Graph spec is
39 // defined.
40 // ==========================================================================
41 
42 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_ALIGN_TRACEBACK_H_
43 #define SEQAN_INCLUDE_SEQAN_ALIGN_ALIGN_TRACEBACK_H_
44 
45 namespace seqan {
46 
47 // ============================================================================
48 // Forwards
49 // ============================================================================
50 
51 // ============================================================================
52 // Tags, Classes, Enums
53 // ============================================================================
54 
55 // ----------------------------------------------------------------------------
56 // Specialization TraceBack
57 // ----------------------------------------------------------------------------
58 
59 // TODO(holtgrew): Mark as internal with underscore?
60 
61 /*!
62  * @typedef TraceBack
63  * @headerfile <seqan/align.h>
64  * @brief Traceback value.
65  *
66  * @signature struct TraceBack_;
67  * @signature typedef SimpleType<unsigned char, TraceBack_> TraceBack.
68  *
69  * The ValueSize of <tt>TraceBack</tt> is 3.  The values are defined in the following way:
70  *
71  * <ul>
72  *   <li>0 - Diagonal Move</li>
73  *   <li>1 - Horizontal Move</li>
74  *   <li>2 - Vertical Move</li>
75  * </ul>
76  */
77 
78 struct TraceBack_ {};
79 typedef SimpleType<unsigned char, TraceBack_> TraceBack;
80 
81 template <> struct ValueSize<TraceBack>
82 {
83     typedef __uint8 Type;
84     static const Type VALUE = 3;
85 };
86 
87 template <> struct BitsPerValue<TraceBack>
88 {
89     typedef __uint8 Type;
90     static const Type VALUE = 2;
91 };
92 
93 // ----------------------------------------------------------------------------
94 // Helper Class AlignTraceback
95 // ----------------------------------------------------------------------------
96 
97 // TODO(holtgrew): Mark as internal with underscore?
98 
99 /*!
100  * @class AlignTraceback
101  * @headerfile <seqan/align.h>
102  * @brief Data structure for storing alignment traceback.
103  *
104  * @signature template <typename TSize>
105  *            struct AlignTraceback;
106  *
107  * @tparam TSize Size type to use in the traceback.
108  */
109 
110 /*!
111  * @var TSizes AlignTraceback::sizes
112  * @brief The traceback lengths.
113  */
114 
115 /*!
116  * @var TLengths AlignTraceback::tsv
117  * @brief The traceback lengths.
118  */
119 
120 template <typename TSize>
121 struct AlignTraceback
122 {
123     // Run lengths in the align matrix.
124     String<TSize> sizes;
125     // Trace values: 0 = diagonal, 1 = horizontal, 2 = vertical.
126     String<TraceBack> tvs;
127 };
128 
129 // ============================================================================
130 // Metafunctions
131 // ============================================================================
132 
133 // ============================================================================
134 // Functions
135 // ============================================================================
136 
137 // ----------------------------------------------------------------------------
138 // Function _alignTracePrint()
139 // ----------------------------------------------------------------------------
140 
141 // _alignTracePrint: this function is called by various alignment algorithm to build up the alignment during traceback
142 
143 template <typename TSize, typename TSequenceH, typename TSequenceV, typename TId, typename TPos, typename TTraceValue>
144 inline void
145 _alignTracePrint(AlignTraceback<TSize> & tb,
146                  TSequenceH const &,
147                  TSequenceV const &,
148                  TId const,
149                  TPos const,
150                  TId const,
151                  TPos const,
152                  TPos const segLen,
153                  TTraceValue const tv)
154 {
155     appendValue(tb.sizes, segLen);
156     appendValue(tb.tvs, tv);
157 }
158 
159 }  // namespace seqan
160 
161 #endif  // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_ALIGN_TRACEBACK_H_
162