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