NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ed_inl.h
Go to the documentation of this file.
1 /*
2  * nvbio
3  * Copyright (c) 2011-2014, NVIDIA CORPORATION. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  * * Redistributions of source code must retain the above copyright
8  * notice, this list of conditions and the following disclaimer.
9  * * Redistributions in binary form must reproduce the above copyright
10  * notice, this list of conditions and the following disclaimer in the
11  * documentation and/or other materials provided with the distribution.
12  * * Neither the name of the NVIDIA CORPORATION nor the
13  * names of its contributors may be used to endorse or promote products
14  * derived from this software without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19  * DISCLAIMED. IN NO EVENT SHALL NVIDIA CORPORATION BE LIABLE FOR ANY
20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26  */
27 
28 #pragma once
29 
30 #include <nvbio/alignment/sink.h>
31 #include <nvbio/alignment/utils.h>
32 #include <nvbio/alignment/alignment_base_inl.h>
33 #include <nvbio/alignment/sw/sw_inl.h>
34 #include <nvbio/alignment/ed/ed_utils.h>
35 
36 
37 namespace nvbio {
38 namespace aln {
39 
40 namespace priv
41 {
42 
45 
55 template <
56  AlignmentType TYPE,
57  typename algorithm_tag,
58  typename pattern_string,
59  typename qual_string,
60  typename text_string,
61  typename column_type>
62 struct alignment_score_dispatch<
63  EditDistanceAligner<TYPE,algorithm_tag>,
64  pattern_string,
65  qual_string,
66  text_string,
67  column_type>
68 {
69  typedef EditDistanceAligner<TYPE,algorithm_tag> aligner_type;
70 
82  template <typename sink_type>
83  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
84  static bool dispatch(
85  const aligner_type aligner,
86  const pattern_string pattern,
87  const qual_string quals,
88  const text_string text,
89  const int32 min_score,
90  sink_type& sink,
91  column_type column)
92  {
93  typedef typename pattern_string::value_type symbol_type;
94 
95  NVBIO_VAR_UNUSED const uint32 BAND_LEN = sw_bandlen_selector<TYPE,1u,symbol_type>::BAND_LEN;
96 
97  priv::SWScoringContext<BAND_LEN,TYPE,algorithm_tag> context;
98 
99  const uint32 length = equal<algorithm_tag,PatternBlockingTag>() ? pattern.length() : text.length();
100 
101  return sw_alignment_score_dispatch<BAND_LEN,TYPE,algorithm_tag,symbol_type>::run( EditDistanceSWScheme(), context, pattern, quals, text, min_score, sink, 0, length, column );
102  }
103 
119  template <
120  typename sink_type,
121  typename checkpoint_type>
122  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
123  static bool dispatch(
124  const aligner_type aligner,
125  const pattern_string pattern,
126  const qual_string quals,
127  const text_string text,
128  const int32 min_score,
129  const uint32 window_begin,
130  const uint32 window_end,
131  sink_type& sink,
132  checkpoint_type checkpoint,
133  column_type column)
134  {
135  typedef typename pattern_string::value_type symbol_type;
136 
137  NVBIO_VAR_UNUSED const uint32 BAND_LEN = sw_bandlen_selector<TYPE,1u,symbol_type>::BAND_LEN;
138 
139  priv::SWCheckpointedScoringContext<BAND_LEN,TYPE,algorithm_tag,checkpoint_type> context( checkpoint );
140 
141  return sw_alignment_score_dispatch<BAND_LEN,TYPE,algorithm_tag,symbol_type>::run( EditDistanceSWScheme(), context, pattern, quals, text, min_score, sink, window_begin, window_end, column );
142  }
143 
156  template <typename sink_type>
157  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
158  static bool dispatch(
159  const aligner_type aligner,
160  const pattern_string pattern,
161  const qual_string quals,
162  const text_string text,
163  const int32 min_score,
164  const uint32 window_begin,
165  const uint32 window_end,
166  sink_type& sink,
167  column_type column)
168  {
169  typedef typename pattern_string::value_type symbol_type;
170 
171  NVBIO_VAR_UNUSED const uint32 BAND_LEN = sw_bandlen_selector<TYPE,1u,symbol_type>::BAND_LEN;
172 
173  priv::SWScoringContext<BAND_LEN,TYPE,algorithm_tag> context;
174 
175  return sw_alignment_score_dispatch<BAND_LEN,TYPE,algorithm_tag,symbol_type>::run( EditDistanceSWScheme(), context, pattern, quals, text, min_score, sink, window_begin, window_end, column );
176  }
177 };
178 
188 template <
189  uint32 CHECKPOINTS,
190  AlignmentType TYPE,
191  typename pattern_string,
192  typename qual_string,
193  typename text_string,
194  typename column_type>
195 struct alignment_checkpointed_dispatch<
196  CHECKPOINTS,
197  EditDistanceAligner<TYPE>,
198  pattern_string,
199  qual_string,
200  text_string,
201  column_type>
202 {
203  typedef EditDistanceAligner<TYPE> aligner_type;
204 
224  template <
225  typename sink_type,
226  typename checkpoint_type>
227  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
228  static
229  void dispatch_checkpoints(
230  const aligner_type aligner,
231  const pattern_string pattern,
232  const qual_string quals,
233  const text_string text,
234  const int32 min_score,
235  sink_type& sink,
236  checkpoint_type checkpoints,
237  column_type column)
238  {
239  typedef typename pattern_string::value_type symbol_type;
240 
241  NVBIO_VAR_UNUSED const uint32 BAND_LEN = sw_bandlen_selector<TYPE,1u,symbol_type>::BAND_LEN;
242 
243  priv::SWCheckpointContext<BAND_LEN,TYPE,CHECKPOINTS,checkpoint_type> context( checkpoints );
244 
245  sw_alignment_score_dispatch<BAND_LEN,TYPE,PatternBlockingTag,symbol_type>::run( EditDistanceSWScheme(), context, pattern, quals, text, min_score, sink, 0, pattern.length(), column );
246  }
247 
272  template <
273  typename checkpoint_type,
274  typename submatrix_type>
275  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
276  static
277  uint32 dispatch_submatrix(
278  const aligner_type aligner,
279  const pattern_string pattern,
280  const qual_string quals,
281  const text_string text,
282  const int32 min_score,
283  checkpoint_type checkpoints,
284  const uint32 checkpoint_id,
285  submatrix_type submatrix,
286  column_type column)
287  {
288  typedef typename pattern_string::value_type symbol_type;
289 
290  NVBIO_VAR_UNUSED const uint32 BAND_LEN = sw_bandlen_selector<TYPE,1u,symbol_type>::BAND_LEN;
291 
292  priv::SWSubmatrixContext<BAND_LEN,TYPE,CHECKPOINTS,checkpoint_type,submatrix_type>
293  context( checkpoints, checkpoint_id, submatrix );
294 
295  const uint32 window_begin = checkpoint_id * CHECKPOINTS;
296  const uint32 window_end = nvbio::min( window_begin + CHECKPOINTS, uint32(pattern.length()) );
297 
298  NullSink null_sink;
299  sw_alignment_score_dispatch<BAND_LEN,TYPE,PatternBlockingTag,symbol_type>::run( EditDistanceSWScheme(), context, pattern, quals, text, min_score, null_sink, window_begin, window_end, column );
300 
301  return window_end - window_begin;
302  }
303 };
304 
340 template <
341  uint32 CHECKPOINTS,
342  AlignmentType TYPE,
343  typename checkpoint_type,
344  typename submatrix_type,
345  typename backtracer_type>
346 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
347 bool alignment_traceback(
348  const EditDistanceAligner<TYPE> aligner,
349  checkpoint_type checkpoints,
350  const uint32 checkpoint_id,
351  submatrix_type submatrix,
352  const uint32 submatrix_width,
353  const uint32 submatrix_height,
354  uint8& state,
355  uint2& sink,
356  backtracer_type& backtracer)
357 {
358  return alignment_traceback<CHECKPOINTS>(
359  make_smith_waterman_aligner<TYPE>( EditDistanceSWScheme() ),
360  checkpoints,
361  checkpoint_id,
362  submatrix,
363  submatrix_width,
364  submatrix_height,
365  state,
366  sink,
367  backtracer );
368 }
369 
371 
372 } // namespace priv
373 
374 } // namespace aln
375 } // namespace nvbio
Generated on Wed Feb 25 2015 08:32:53 for NVBIO by   doxygen 1.8.4