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 // Global alignment interface for journaled strings.
35 // ==========================================================================
36
37 #ifndef INCLUDE_SEQAN_JOURNALED_SET_JOURNAL_ALIGNMENT_INTERFACE_H_
38 #define INCLUDE_SEQAN_JOURNALED_SET_JOURNAL_ALIGNMENT_INTERFACE_H_
39
40 namespace seqan {
41
42 // ============================================================================
43 // Forwards
44 // ============================================================================
45
46 // ============================================================================
47 // Tags, Classes, Enums
48 // ============================================================================
49
50 // ============================================================================
51 // Metafunctions
52 // ============================================================================
53
54 // ============================================================================
55 // Functions
56 // ============================================================================
57
58 // ----------------------------------------------------------------------------
59 // Function globalAlignment() [unbanded, String<Journaled<> >]
60 // ----------------------------------------------------------------------------
61
62 // Full interface.
63
64 template <typename TValue, typename THostSpec, typename TJournalSpec,
65 typename TBuffSpec, typename TReference, typename TSource,
66 typename TScoreValue, typename TScoreSpec,
67 bool TOP, bool LEFT, bool RIGHT, bool BOTTOM, typename TACSpec,
68 typename TAlgoTag>
globalAlignment(String<TValue,Journaled<THostSpec,TJournalSpec,TBuffSpec>> & journaledString,TReference const & reference,TSource const & source,Score<TScoreValue,TScoreSpec> const & scoringScheme,AlignConfig<TOP,LEFT,RIGHT,BOTTOM,TACSpec> const &,TAlgoTag const &)69 TScoreValue globalAlignment(String<TValue, Journaled<THostSpec, TJournalSpec, TBuffSpec> > & journaledString,
70 TReference const & reference,
71 TSource const & source,
72 Score<TScoreValue, TScoreSpec> const & scoringScheme,
73 AlignConfig<TOP, LEFT, RIGHT, BOTTOM, TACSpec> const & /*alignConfig*/,
74 TAlgoTag const & /*tag*/)
75 {
76 typedef String<TValue, Journaled<THostSpec, TJournalSpec, TBuffSpec> > TJournalString;
77 typedef typename Position<TJournalString>::Type TPosition;
78 typedef typename Size<TJournalString>::Type TSize;
79 typedef TraceSegment_<TPosition, TSize> TTraceSegment;
80 typedef AlignConfig<TOP, LEFT, RIGHT, BOTTOM, TACSpec> TAlignConfig;
81 typedef typename SubstituteAlignConfig_<TAlignConfig>::Type TFreeEndGaps;
82 typedef AlignConfig2<DPGlobal, DPBandConfig<BandOff>, TFreeEndGaps, TracebackOn<TracebackConfig_<SingleTrace, GapsLeft> > > TDPConfig;
83
84 String<TTraceSegment> traceSegments;
85 DPScoutState_<Default> dpScoutState;
86 // We need to do that in order to build journal strings from two simple sequences.
87 TScoreValue res = _setUpAndRunAlignment(traceSegments, dpScoutState, reference, source, scoringScheme, TDPConfig(),
88 IsSameType<TAlgoTag, NeedlemanWunsch>());
89 _adaptTraceSegmentsTo(journaledString, reference, source, traceSegments);
90 return res;
91 }
92
93 // Interface without AlignConfig<>.
94
95 template <typename TValue, typename THostSpec, typename TJournalSpec,
96 typename TBuffSpec, typename TReference, typename TSource,
97 typename TScoreValue, typename TScoreSpec,
98 typename TAlgoTag>
globalAlignment(String<TValue,Journaled<THostSpec,TJournalSpec,TBuffSpec>> & journaledString,TReference const & reference,TSource const & source,Score<TScoreValue,TScoreSpec> const & scoringScheme,TAlgoTag const & algoTag)99 TScoreValue globalAlignment(String<TValue, Journaled<THostSpec, TJournalSpec, TBuffSpec> > & journaledString,
100 TReference const & reference,
101 TSource const & source,
102 Score<TScoreValue, TScoreSpec> const & scoringScheme,
103 TAlgoTag const & algoTag)
104 {
105 AlignConfig<> alignConfig;
106 return globalAlignment(journaledString, reference, source, scoringScheme, alignConfig, algoTag);
107 }
108
109 // Interface without algorithm tag.
110
111 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBuffSpec,
112 typename TReference, typename TSource,
113 typename TScoreValue, typename TScoreSpec,
114 bool TOP, bool LEFT, bool RIGHT, bool BOTTOM, typename TACSpec>
globalAlignment(String<TValue,Journaled<THostSpec,TJournalSpec,TBuffSpec>> & journaledString,TReference const & reference,TSource const & source,Score<TScoreValue,TScoreSpec> const & scoringScheme,AlignConfig<TOP,LEFT,RIGHT,BOTTOM,TACSpec> const & alignConfig)115 TScoreValue globalAlignment(String<TValue, Journaled<THostSpec, TJournalSpec, TBuffSpec> > & journaledString,
116 TReference const & reference,
117 TSource const & source,
118 Score<TScoreValue, TScoreSpec> const & scoringScheme,
119 AlignConfig<TOP, LEFT, RIGHT, BOTTOM, TACSpec> const & alignConfig)
120 {
121 typedef typename SequenceEntryForScore<Score<TScoreValue, TScoreSpec>, TReference>::Type TReferenceEntryForScore;
122 typedef typename SequenceEntryForScore<Score<TScoreValue, TScoreSpec>, TSource>::Type TSourceEntryForScore;
123
124 TReferenceEntryForScore entryRef = sequenceEntryForScore(scoringScheme, reference, 0);
125 TSourceEntryForScore entrySource = sequenceEntryForScore(scoringScheme, source, 0);
126 if (scoreGapOpenHorizontal(scoringScheme, entryRef, entrySource) ==
127 scoreGapExtendHorizontal(scoringScheme, entryRef, entrySource) ||
128 scoreGapOpenVertical(scoringScheme, entryRef, entrySource) ==
129 scoreGapExtendVertical(scoringScheme, entryRef, entrySource))
130 return globalAlignment(journaledString, reference, source, scoringScheme, alignConfig, NeedlemanWunsch());
131 else
132 return globalAlignment(journaledString, reference, source, scoringScheme, alignConfig, Gotoh());
133 }
134
135 // Interface without AlignConfig<> and algorithm tag.
136
137 template <typename TValue, typename THostSpec, typename TJournalSpec,
138 typename TBuffSpec, typename TReference, typename TSource,
139 typename TScoreValue, typename TScoreSpec>
globalAlignment(String<TValue,Journaled<THostSpec,TJournalSpec,TBuffSpec>> & journaledString,TReference const & reference,TSource const & source,Score<TScoreValue,TScoreSpec> const & scoringScheme)140 TScoreValue globalAlignment(String<TValue, Journaled<THostSpec, TJournalSpec, TBuffSpec> > & journaledString,
141 TReference const & reference,
142 TSource const & source,
143 Score<TScoreValue, TScoreSpec> const & scoringScheme)
144 {
145 AlignConfig<> alignConfig;
146 return globalAlignment(journaledString, reference, source, scoringScheme, alignConfig);
147 }
148
149 // ----------------------------------------------------------------------------
150 // Function globalAlignment() [banded, String<Journaled<> >]
151 // ----------------------------------------------------------------------------
152
153 // Full interface.
154
155 template <typename TValue, typename THostSpec, typename TJournalSpec,
156 typename TBuffSpec, typename TReference, typename TSource,
157 typename TScoreValue, typename TScoreSpec,
158 bool TOP, bool LEFT, bool RIGHT, bool BOTTOM, typename TACSpec,
159 typename TAlgoTag>
globalAlignment(String<TValue,Journaled<THostSpec,TJournalSpec,TBuffSpec>> & journaledString,TReference const & reference,TSource const & source,Score<TScoreValue,TScoreSpec> const & scoringScheme,AlignConfig<TOP,LEFT,RIGHT,BOTTOM,TACSpec> const &,int lowerDiag,int upperDiag,TAlgoTag const &)160 TScoreValue globalAlignment(String<TValue, Journaled<THostSpec, TJournalSpec, TBuffSpec> > & journaledString,
161 TReference const & reference,
162 TSource const & source,
163 Score<TScoreValue, TScoreSpec> const & scoringScheme,
164 AlignConfig<TOP, LEFT, RIGHT, BOTTOM, TACSpec> const & /*alignConfig*/,
165 int lowerDiag,
166 int upperDiag,
167 TAlgoTag const & /*algoTag*/)
168 {
169 typedef String<TValue, Journaled<THostSpec, TJournalSpec, TBuffSpec> > TJournalString;
170 typedef typename Position<TJournalString>::Type TPosition;
171 typedef typename Size<TJournalString>::Type TSize;
172 typedef TraceSegment_<TPosition, TSize> TTraceSegment;
173 typedef AlignConfig<TOP, LEFT, RIGHT, BOTTOM, TACSpec> TAlignConfig;
174 typedef typename SubstituteAlignConfig_<TAlignConfig>::Type TFreeEndGaps;
175 typedef AlignConfig2<DPGlobal, DPBandConfig<BandOn>, TFreeEndGaps, TracebackOn<TracebackConfig_<SingleTrace, GapsLeft> > > TDPConfig;
176
177 String<TTraceSegment> traceSegments;
178 DPScoutState_<Default> dpScoutState;
179 // We need to do that in order to build journal strings from two simple sequences.
180 TScoreValue res = _setUpAndRunAlignment(traceSegments, dpScoutState, reference, source, scoringScheme,
181 TDPConfig(lowerDiag, upperDiag),
182 IsSameType<TAlgoTag, NeedlemanWunsch>());
183 _adaptTraceSegmentsTo(journaledString, reference, source, traceSegments);
184 return res;
185 }
186
187 // Interface without AlignConfig<>.
188
189 template <typename TValue, typename THostSpec, typename TJournalSpec,
190 typename TBuffSpec, typename TReference, typename TSource,
191 typename TScoreValue, typename TScoreSpec,
192 typename TAlgoTag>
globalAlignment(String<TValue,Journaled<THostSpec,TJournalSpec,TBuffSpec>> & journaledString,TReference const & reference,TSource const & source,Score<TScoreValue,TScoreSpec> const & scoringScheme,int lowerDiag,int upperDiag,TAlgoTag const & algoTag)193 TScoreValue globalAlignment(String<TValue, Journaled<THostSpec, TJournalSpec, TBuffSpec> > & journaledString,
194 TReference const & reference,
195 TSource const & source,
196 Score<TScoreValue, TScoreSpec> const & scoringScheme,
197 int lowerDiag,
198 int upperDiag,
199 TAlgoTag const & algoTag)
200 {
201 AlignConfig<> alignConfig;
202 return globalAlignment(journaledString, reference, source, scoringScheme, alignConfig, lowerDiag, upperDiag,
203 algoTag);
204 }
205
206 // Interface without algorithm tag.
207
208 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBuffSpec,
209 typename TReference, typename TSource,
210 typename TScoreValue, typename TScoreSpec,
211 bool TOP, bool LEFT, bool RIGHT, bool BOTTOM, typename TACSpec>
globalAlignment(String<TValue,Journaled<THostSpec,TJournalSpec,TBuffSpec>> & journaledString,TReference const & reference,TSource const & source,Score<TScoreValue,TScoreSpec> const & scoringScheme,AlignConfig<TOP,LEFT,RIGHT,BOTTOM,TACSpec> const & alignConfig,int lowerDiag,int upperDiag)212 TScoreValue globalAlignment(String<TValue, Journaled<THostSpec, TJournalSpec, TBuffSpec> > & journaledString,
213 TReference const & reference,
214 TSource const & source,
215 Score<TScoreValue, TScoreSpec> const & scoringScheme,
216 AlignConfig<TOP, LEFT, RIGHT, BOTTOM, TACSpec> const & alignConfig,
217 int lowerDiag,
218 int upperDiag)
219 {
220 typedef typename SequenceEntryForScore<Score<TScoreValue, TScoreSpec>, TReference>::Type TReferenceEntryForScore;
221 typedef typename SequenceEntryForScore<Score<TScoreValue, TScoreSpec>, TSource>::Type TSourceEntryForScore;
222
223 TReferenceEntryForScore entryRef = sequenceEntryForScore(scoringScheme, reference, 0);
224 TSourceEntryForScore entrySource = sequenceEntryForScore(scoringScheme, source, 0);
225 if (scoreGapOpenHorizontal(scoringScheme, entryRef, entrySource) ==
226 scoreGapExtendHorizontal(scoringScheme, entryRef, entrySource) ||
227 scoreGapOpenVertical(scoringScheme, entryRef, entrySource) ==
228 scoreGapExtendVertical(scoringScheme, entryRef, entrySource))
229 return globalAlignment(journaledString, reference, source, scoringScheme, alignConfig, lowerDiag, upperDiag,
230 NeedlemanWunsch());
231 else
232 return globalAlignment(journaledString, reference, source, scoringScheme, alignConfig, lowerDiag, upperDiag,
233 Gotoh());
234 }
235
236 // Interface without AlignConfig<> and algorithm tag.
237
238 template <typename TValue, typename THostSpec, typename TJournalSpec,
239 typename TBuffSpec, typename TReference, typename TSource,
240 typename TScoreValue, typename TScoreSpec>
globalAlignment(String<TValue,Journaled<THostSpec,TJournalSpec,TBuffSpec>> & journaledString,TReference const & reference,TSource const & source,Score<TScoreValue,TScoreSpec> const & scoringScheme,int lowerDiag,int upperDiag)241 TScoreValue globalAlignment(String<TValue, Journaled<THostSpec, TJournalSpec, TBuffSpec> > & journaledString,
242 TReference const & reference,
243 TSource const & source,
244 Score<TScoreValue, TScoreSpec> const & scoringScheme,
245 int lowerDiag,
246 int upperDiag)
247 {
248 AlignConfig<> alignConfig;
249 return globalAlignment(journaledString, reference, source, scoringScheme, alignConfig, lowerDiag, upperDiag);
250 }
251
252 } // namespace seqan
253
254 #endif // #ifndef INCLUDE_SEQAN_JOURNALED_SET_JOURNAL_ALIGNMENT_INTERFACE_H_
255