1 // Copyright (c) 2020 Robert Vaser
2 
3 #ifndef SPOA_ALIGNMENT_ENGINE_HPP_
4 #define SPOA_ALIGNMENT_ENGINE_HPP_
5 
6 #pragma once
7 
8 #include <cstdint>
9 #include <memory>
10 #include <string>
11 #include <utility>
12 #include <vector>
13 
14 namespace spoa {
15 
16 enum class AlignmentType {
17   kSW,  // Smith Waterman
18   kNW,  // Needleman Wunsch
19   kOV   // Overlap
20 };
21 
22 enum class AlignmentSubtype {
23   kLinear,  // g * i
24   kAffine,  // g + (i - 1) * e
25   kConvex   // min(g1 + (i - 1) * e1, g2 + (i - 1) * e2)
26 };
27 
28 class Graph;
29 using Alignment = std::vector<std::pair<std::int32_t, std::int32_t>>;
30 
31 class AlignmentEngine {
32  public:
33   virtual ~AlignmentEngine() = default;
34 
35   static std::unique_ptr<AlignmentEngine> Create(
36       AlignmentType type,
37       std::int8_t m,   // match
38       std::int8_t n,   // mismatch
39       std::int8_t g);  // gap
40 
41   static std::unique_ptr<AlignmentEngine> Create(
42       AlignmentType type,
43       std::int8_t m,
44       std::int8_t n,
45       std::int8_t g,   // gap open
46       std::int8_t e);  // gap extend
47 
48   static std::unique_ptr<AlignmentEngine> Create(
49       AlignmentType type,
50       std::int8_t m,
51       std::int8_t n,
52       std::int8_t g,
53       std::int8_t e,
54       std::int8_t q,   // gap open of second affine
55       std::int8_t c);  // gap extend of second affine
56 
57   virtual void Prealloc(
58       std::uint32_t max_sequence_len,
59       std::uint8_t alphabet_size) = 0;
60 
61   Alignment Align(
62       const std::string& sequence,
63       const Graph& graph,
64       std::int32_t* score = nullptr);
65 
66   virtual Alignment Align(
67       const char* sequence, std::uint32_t sequence_len,
68       const Graph& graph,
69       std::int32_t* score = nullptr) = 0;
70 
71  protected:
72   AlignmentEngine(
73       AlignmentType type,
74       AlignmentSubtype subtype,
75       std::int8_t m,
76       std::int8_t n,
77       std::int8_t g,
78       std::int8_t e,
79       std::int8_t q,
80       std::int8_t c);
81 
82   std::int64_t WorstCaseAlignmentScore(
83       std::int64_t sequence_len,
84       std::int64_t graph_len) const;
85 
86   AlignmentType type_;
87   AlignmentSubtype subtype_;
88   std::int8_t m_;
89   std::int8_t n_;
90   std::int8_t g_;
91   std::int8_t e_;
92   std::int8_t q_;
93   std::int8_t c_;
94 };
95 
96 }  // namespace spoa
97 
98 #endif  // SPOA_ALIGNMENT_ENGINE_HPP_
99