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>
40 #include <string>
41 #include <map>
42 
43 namespace nvbio {
44 namespace bowtie2 {
45 namespace cuda {
46 
49 
52 
56 };
57 
58 enum CostType {
60  QUAL_COST = 2,
62 };
63 
67 template <typename T>
69 {
71 
74 
76  RoundedQualCost(const T min_val, const T max_val) {}
77 
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 
92 
94  QualCost(const T min_val, const T max_val) : m_min_val( min_val ), m_max_val( max_val ) {}
95 
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 
105 };
106 
110 template <typename T>
112 {
114 
116  ConstantCost() : m_val(0) {}
117 
119  ConstantCost(const T min_val, const T max_val) : m_val( max_val ) {}
120 
122  T operator() (const int i) const { return T( m_val ); }
123 
124  T m_val;
125 };
126 
134 {
138 
141 
144 
145  static const int32 inf_score = 0;
146  static const int32 worst_score = -(1 << 8);
147 
151 
155 
159 
163 
164  // ---------- constructors -------------------------------------------------------------------- //
165 
169  EditDistanceScoringScheme() : m_score_min( SimpleFunc::LinearFunc, -5.0f, 0.0f ) {}
170 
171  // ---------- begin: limits ------------------------------------------------------------------- //
172 
176  int32 perfect_score(const uint32 read_len) const { return 0; }
177 
181  int32 min_score(const uint32 len) const { return m_score_min( len ); }
182 
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> >
207 {
210 
213 
216 
218  typedef MMCost MismatchCost;
219 
222  typedef NCost N_cost_function;
223 
225 
226  static const int32 inf_score = -(1 << 16);
227  static const int32 worst_score = inf_score;
228 
232 
236 
240 
244 
245  // ---------- constructors -------------------------------------------------------------------- //
246 
250 
254 
259 
264  const std::map<std::string,std::string>& options,
265  const AlignmentType type = LocalAlignment);
266 
267  // ---------- begin: limits ------------------------------------------------------------------- //
268 
272  int32 min_score(const uint32 len) const { return m_score_min( len ); }
273 
277 
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); }
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 
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 
316  int n(int q) const { return m_np( q < 255 ? q : 255 ); }
317 
321  int cumulative_insertion(const uint32 i) const
322  {
323  return m_read_gap_const + m_read_gap_coeff * i;
324  }
325 
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>
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 
385 {
388 };
389 
393 template <typename ScoringTagType>
395 {};
396 
399 template <>
401 {
403 
404  static EditDistanceScoringScheme scheme(const UberScoringScheme& _scheme) { return _scheme.ed; }
405 };
406 
409 template <>
411 {
413 
414  static SmithWatermanScoringScheme<> scheme(const UberScoringScheme& _scheme) { return _scheme.sw; }
415 };
416 
420 template <typename ScoringSchemeType>
422 
425 template <>
427 
430 template <
431  typename MMCost,
432  typename NCost >
434 
437 
438 } // namespace cuda
439 } // namespace bowtie2
440 } // namespace nvbio
441