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