NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
scoring.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 
31 
32 #pragma once
33 
34 #include <nvbio/basic/types.h>
35 #include <nvbio/basic/options.h>
36 #include <nvbio/alignment/alignment_base.h>
37 #include <nvBowtie/bowtie2/quality_coeffs.h>
38 #include <nvBowtie/bowtie2/cuda/defs.h>
39 #include <nvBowtie/bowtie2/cuda/func.h>
40 #include <string>
41 #include <map>
42 
43 namespace nvbio {
44 namespace bowtie2 {
45 namespace cuda {
46 
49 
52 
53 enum AlignmentType {
54  EndToEndAlignment = 0,
55  LocalAlignment = 1,
56 };
57 
58 enum CostType {
59  ROUNDED_QUAL_COST = 1,
60  QUAL_COST = 2,
61  CONSTANT_COST = 3
62 };
63 
67 template <typename T>
68 struct RoundedQualCost
69 {
70  static const CostType COST_TYPE = ROUNDED_QUAL_COST;
71 
72  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
73  RoundedQualCost() {}
74 
75  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
76  RoundedQualCost(const T min_val, const T max_val) {}
77 
78  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
79  T operator() (const int i) const { return T( phred_to_maq(i) ); }
80 };
81 
85 template <typename T>
86 struct QualCost
87 {
88  static const CostType COST_TYPE = QUAL_COST;
89 
90  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
91  QualCost() : m_min_val(0), m_max_val(0) {}
92 
93  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
94  QualCost(const T min_val, const T max_val) : m_min_val( min_val ), m_max_val( max_val ) {}
95 
96  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
97  T operator() (const int i) const
98  {
99  const float frac = (float)(nvbio::min(i, 40) / 40.0f);
100  return m_min_val + T( frac * (m_max_val - m_min_val) );
101  }
102 
103  T m_min_val;
104  T m_max_val;
105 };
106 
110 template <typename T>
111 struct ConstantCost
112 {
113  static const CostType COST_TYPE = CONSTANT_COST;
114 
115  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
116  ConstantCost() : m_val(0) {}
117 
118  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
119  ConstantCost(const T min_val, const T max_val) : m_val( max_val ) {}
120 
121  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
122  T operator() (const int i) const { return T( m_val ); }
123 
124  T m_val;
125 };
126 
133 struct EditDistanceScoringScheme
134 {
135  typedef EditDistanceScoringScheme scheme_type;
136  typedef SimpleFunc threshold_score_type;
137  typedef aln::EditDistanceTag aligner_tag;
138 
139  typedef aln::EditDistanceAligner<aln::LOCAL> local_aligner_type;
140  typedef aln::EditDistanceAligner<aln::SEMI_GLOBAL> end_to_end_aligner_type;
141 
142  typedef aln::EditDistanceAligner<aln::LOCAL> ungapped_local_aligner_type;
143  typedef aln::EditDistanceAligner<aln::SEMI_GLOBAL> ungapped_end_to_end_aligner_type;
144 
145  static const int32 inf_score = 0;
146  static const int32 worst_score = -(1 << 8);
147 
150  local_aligner_type local_aligner() const { return local_aligner_type(); }
151 
154  end_to_end_aligner_type end_to_end_aligner() const { return end_to_end_aligner_type(); }
155 
158  ungapped_local_aligner_type ungapped_local_aligner() const { return ungapped_local_aligner_type(); }
159 
162  ungapped_end_to_end_aligner_type ungapped_end_to_end_aligner() const { return ungapped_end_to_end_aligner_type(); }
163 
164  // ---------- constructors -------------------------------------------------------------------- //
165 
168  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
169  EditDistanceScoringScheme() : m_score_min( SimpleFunc::LinearFunc, -5.0f, 0.0f ) {}
170 
171  // ---------- begin: limits ------------------------------------------------------------------- //
172 
175  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
176  int32 perfect_score(const uint32 read_len) const { return 0; }
177 
180  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
181  int32 min_score(const uint32 len) const { return m_score_min( len ); }
182 
185  SimpleFunc threshold_score() const
186  {
187  return m_score_min;
188  }
189 
190  // ---------- end: limits ---------------------------------------------------------------------- //
191 
192 public:
193  SimpleFunc m_score_min; // minimum read score function
194 };
195 
203 template <
204  typename MMCost = QualCost<int>,
205  typename NCost = ConstantCost<int> >
206 struct SmithWatermanScoringScheme
207 {
208  typedef SmithWatermanScoringScheme<MMCost,NCost> scheme_type;
209  typedef aln::GotohTag aligner_tag;
210 
211  typedef aln::GotohAligner<aln::LOCAL,scheme_type> local_aligner_type;
212  typedef aln::GotohAligner<aln::SEMI_GLOBAL,scheme_type> end_to_end_aligner_type;
213 
214  typedef aln::HammingDistanceAligner<aln::LOCAL,scheme_type> ungapped_local_aligner_type;
215  typedef aln::HammingDistanceAligner<aln::SEMI_GLOBAL,scheme_type> ungapped_end_to_end_aligner_type;
216 
217  typedef ConstantCost<int> MatchCost;
218  typedef MMCost MismatchCost;
219 
220  typedef MatchCost match_cost_function;
221  typedef MismatchCost mismatch_cost_function;
222  typedef NCost N_cost_function;
223 
224  typedef SimpleFunc threshold_score_type;
225 
226  static const int32 inf_score = -(1 << 16);
227  static const int32 worst_score = inf_score;
228 
231  local_aligner_type local_aligner() const { return local_aligner_type(*this); }
232 
235  end_to_end_aligner_type end_to_end_aligner() const { return end_to_end_aligner_type(*this); }
236 
239  ungapped_local_aligner_type ungapped_local_aligner() const { return ungapped_local_aligner_type(*this); }
240 
243  ungapped_end_to_end_aligner_type ungapped_end_to_end_aligner() const { return ungapped_end_to_end_aligner_type(*this); }
244 
245  // ---------- constructors -------------------------------------------------------------------- //
246 
249  static SmithWatermanScoringScheme base1();
250 
253  static SmithWatermanScoringScheme local();
254 
257  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
258  SmithWatermanScoringScheme();
259 
263  SmithWatermanScoringScheme(
264  const std::map<std::string,std::string>& options,
265  const AlignmentType type = LocalAlignment);
266 
267  // ---------- begin: limits ------------------------------------------------------------------- //
268 
271  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
272  int32 min_score(const uint32 len) const { return m_score_min( len ); }
273 
276  SimpleFunc threshold_score() const { return m_score_min; }
277 
280  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
281  int32 perfect_score(const uint32 read_len) const { return int32(read_len) * match( 0 ); }
282 
283  // ---------- end: limits ---------------------------------------------------------------------- //
284 
285  // -------- begin: aln::GotohAligner interface ----------------------------------------------------------------- //
286  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE int32 match(const uint8 q = 0) const { return m_match(q); }
287  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE int32 mismatch(const uint8 q = 0) const { return -m_mmp(q); }
288  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE int32 mismatch(const uint8 r, const uint8 q, const uint8 qq = 0) const { return -m_mmp(qq); }
289  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE int32 substitution(const uint32 r_i, const uint32 q_j, const uint8 r, const uint8 q, const uint8 qq = 0) const { return r == q ? m_match(qq) : -m_mmp(qq); }
290  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE int32 pattern_gap_open() const { return -m_read_gap_const - m_read_gap_coeff; }
291  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE int32 pattern_gap_extension() const { return -m_read_gap_coeff; }
292  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE int32 text_gap_open() const { return -m_ref_gap_const - m_ref_gap_coeff; }
293  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE int32 text_gap_extension() const { return -m_ref_gap_coeff; }
294  // -------- end: aln::GotohAligner interface ------------------------------------------------------------------- //
295 
296  // -------- begin: helper methods to perform final scoring --------------------------------------------------- //
297  // NOTE: technically we could use the same interface used by the SW module, but wheareas that is geared
298  // towards dynamic programming, this one is simpler to use when just linearly scanning through a given
299  // alignment
300 
303  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
304  int score(const uint8 read, const uint8 ref_mask, int q) const
305  {
306  return (read > 3 || ref_mask > 15) ? // is there an N?
307  -m_np(q) : // N score
308  ((ref_mask & (1u << read)) != 0) ? // is there a match ?
309  m_match(q) : // match score
310  -m_mmp(q); // mismatch score
311  }
312 
315  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
316  int n(int q) const { return m_np( q < 255 ? q : 255 ); }
317 
320  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
321  int cumulative_insertion(const uint32 i) const
322  {
323  return m_read_gap_const + m_read_gap_coeff * i;
324  }
325 
328  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
329  int cumulative_deletion(const uint32 i) const
330  {
331  return m_ref_gap_const + m_ref_gap_coeff * i;
332  }
333  // -------- end: helper methods to perform final scoring --------------------------------------------------- //
334 
335 public:
336  SimpleFunc m_score_min; // minimum read score function
337  float m_n_ceil_const; // constant for the function governing the ceiling on the number of N's, depending on the read-length
338  float m_n_ceil_coeff; // coefficient for the function governing the ceiling on the number of N's, depending on the read-length
339  int m_read_gap_const; // reap gap open penalty
340  int m_read_gap_coeff; // reap gap extension penalty
341  int m_ref_gap_const; // reference gap open penalty
342  int m_ref_gap_coeff; // reference gap extension penalty
343  int m_gap_free; // length of the gap-free area at the beginning of each read
344  MatchCost m_match; // match bonus function (function of the quality score)
345  MMCost m_mmp; // mismatch penalty function (function of the quality score)
346  NCost m_np; // N-penalty function (function of the quality score)
347  bool m_monotone; // is this scoring scheme monotone? (i.e. match bonus == 0)
348  bool m_local; // are we doing local alignment?
349 
350 private:
351  static SimpleFunc::Type func_type(const std::string& type);
352  static SimpleFunc min_score_function(const std::map<std::string,std::string>& options);
353  static MatchCost match_cost(const std::map<std::string,std::string>& options);
354  static MMCost mm_cost(const std::map<std::string,std::string>& options);
355  static NCost n_cost(const std::map<std::string,std::string>& options);
356 };
357 
360 template <AlignmentType TYPE, typename scheme_type> struct make_aligner_dispatch {};
361 
364 template <typename scheme_type> struct make_aligner_dispatch<LocalAlignment,scheme_type> { typedef typename scheme_type::local_aligner_type type; static type make(const scheme_type& scheme) { return scheme.local_aligner(); } };
365 
368 template <typename scheme_type> struct make_aligner_dispatch<EndToEndAlignment,scheme_type> { typedef typename scheme_type::local_aligner_type type; static type make(const scheme_type& scheme) { return scheme.end_to_end_aligner(); } };
369 
372 template <AlignmentType TYPE, typename scheme_type>
373 typename make_aligner_dispatch<TYPE,scheme_type>::type
374 make_aligner(const scheme_type& scheme) { return make_aligner_dispatch<TYPE,scheme_type>::make(); }
375 
378 SmithWatermanScoringScheme<> load_scoring_scheme(const char* name, const AlignmentType type);
379 
384 struct UberScoringScheme
385 {
386  EditDistanceScoringScheme ed;
387  SmithWatermanScoringScheme<> sw;
388 };
389 
393 template <typename ScoringTagType>
394 struct ScoringSchemeSelector
395 {};
396 
399 template <>
400 struct ScoringSchemeSelector<edit_distance_scoring_tag>
401 {
402  typedef EditDistanceScoringScheme type;
403 
404  static EditDistanceScoringScheme scheme(const UberScoringScheme& _scheme) { return _scheme.ed; }
405 };
406 
409 template <>
410 struct ScoringSchemeSelector<smith_waterman_scoring_tag>
411 {
412  typedef SmithWatermanScoringScheme<> type;
413 
414  static SmithWatermanScoringScheme<> scheme(const UberScoringScheme& _scheme) { return _scheme.sw; }
415 };
416 
420 template <typename ScoringSchemeType>
421 struct ScoringSchemeTag {};
422 
425 template <>
426 struct ScoringSchemeTag< EditDistanceScoringScheme > { typedef edit_distance_scoring_tag type; };
427 
430 template <
431  typename MMCost,
432  typename NCost >
433 struct ScoringSchemeTag< SmithWatermanScoringScheme<MMCost,NCost> > { typedef smith_waterman_scoring_tag type; };
434 
437 
438 } // namespace cuda
439 } // namespace bowtie2
440 } // namespace nvbio
441 
442 #include <nvBowtie/bowtie2/cuda/scoring_inl.h>
Generated on Wed Feb 25 2015 08:33:06 for NVBIO by   doxygen 1.8.4