Module: Alignments

Module Structure

alignment/detail/...                 // The core implementation of the alignment code, which is not prevent.

alignment/representation.hpp         // Required only if output format is not score only.
alignment/representation/...         // Data structures and utility functions to represent and work with alignments.

alignment/pairwise.hpp
alignment/pairwise/...             // Defining the public API for calling the standard alignment algorithms.

alignment/msa.hpp
alignment/msa/...                  // Defining the public API for calling the msa algorithms.

alignment/seed_extend.hpp
alignment/seed_extend/...          

alignment/split.hpp
alignment/split/...

alignment/banded_chain.hpp
alignment/banded_chain/...

Alignment Representation

In SeqAn 2.x we have several possibilities to represent an alignment. The most unpractical on is the Align object, which represents multiple alignment rows of the same types.

Gap Sequence

template <typename t>
concept bool aligned_sequence_view_concept(t g)
{
   requires view_concept<t>;

   // Element access
   { g[] const; } -> typename t::value_type;

   // Manipulation
   { g.insert_gap(0, 4) } -> bool;
   { g.remove_gap(0, 2) } -> bool;

   { g.underlying_pos() } -> typename t::size_type;
};

Concrete implementation:

Array Gaps

template <typename underlying_t> 
  requires container_concept<underlying_t>
class aligned_sequence_view_blocked
{
public:
   
   gapped_alphabet operator[](size_t const pos){}

   void insert_gap(size_t const pos, size_t const length);
   void remove_gap(size_t const pos, size_t const length);
protected:
   using underlying_iterator = typename underlying_t::const_iterator;
  
   view_interface<underlying_t>;
   underlying_iterator end;
   
};

Anchor Gaps

template <typename host_t, typename gap_traits = default_gap_traits<typename host_t::value_type>>
class aligned_sequence_view_anchored
{
public:
protected:
private:
};

Alignment View

template <typename ...gap_ts>
    requires (gap_sequence_concept<gap_ts> && ...)
class alignment_view 
{
public:
   

    // display
    template <typename stream_t>
    stream_t & operator<<(stream_t && stream);
  
protected:
     std::tuple<gap_ts...>  data;
};

What else do we want to do with the alignment view? Utility functions:

• merge two alignment views. How?

Alignment Algorithms

Compile-time configuration

template <typename t>
concept bool dp_settings_concept = requires
{
    typename t::algorithm_type;
    typename t::gaps_type;
    typename t::trace_type;
    typename t::band_type;

    typename t::output_format; 
}

struct dp_traits
{
    // Gocal alignment with linear gap costs.
    struct global_linear
    {
        // The algorithm to choose.
        using algorithm_type    = global_alignment_<>;
        // The Gaps to choose
        using gap_type          = linear_gaps;
        // The Band to choose.
        using band_type         = band_off;
        // The traceback.
        using traceback_type    = traceback_on<traceback_config_<single_trace, gaps_left>>;
        // The output to choose.
        using format_type           = array_gaps;
    };

    // Global alignment with affine gap costs.
    struct global_affine : public global_linear
    {
        using gap_type          = affine_gaps;
    };

    // Global alignment with affine gap costs.
    struct semi_global_linear : public global_linear
    {
        using algorithm_type = global_alignment_<free_end_gaps_<true, false, true, false>>;
    };

    // Global alignment with affine gap costs.
    struct semi_global_affine : public global_affine
    {
        using algorithm_type = global_alignment_<free_end_gaps_<true, false, true, false>>;
    };

    // Banded global alignment with linear gap costs.
    struct banded_global_linear : public global_linear
    {
        using band_type         = band_on;
    };

    // Banded global alignment with affine gap costs.
    struct BandedGlobalAffine : public BandedGlobalLinear
    {
        using gap_type          = affine_gaps;
    };

    // Local alignment with linear gap costs.
    struct local_linear : public global_linear
    {
        using algorithm_type  = seqan::LocalAlignment_<>;
    };

    // Local alignment with affine gap costs.
    struct local_affine : public local_linear
    {
        using gap_type   = affine_gaps;
    };
};

template <typename exec_policy_t, typename seq1_t, typename seq2_t, typename dp_settings_t>
   requires is_execution_policy<exec_policy_t>::value &&
            container_concept<seq1_t> &&
            container_concept<seq2_t> &&
            dp_settings_concept<dp_settings_t>
inline auto 
align(exec_policy_t const & exec_policy,
      seq1_t const & seq1,
      seq2_t const & seq2,
      dp_settings_t const & settings)
{
   // delegate to corresponding functions.
   // depending on configuration we can return several different things, like the alignment and score or just the score or the trace matrix or what ever we want.
   return { ... };
}

template <typename exec_policy_t, typename seq1_t, typename seq2_t, typename configurator_t, typename callback_f>
   requires is_execution_policy<exec_policy_t>::value &&
            container_concept<seq1_t> &&
            container_concept<seq2_t>
inline void
align_and_then(exec_policy_t const & exec_policy,
               seq1_t const & seq1,
               seq2_t const & seq2,
               configurator_t const & config,
               callback_f && callback)
{
   // delegate to corresponding functions.
   // depending on configuration we can callback several different things, like the alignment and score or just the score or the trace matrix or what ever we want.
}

Runtime configuration

The runtime configuration creates a chain of continuators to create a dp_settings object and delegate to the traits based interfaces. Generic continuators can be designed as a lambda-continuator.

struct DPSelect
{
    // ----------------------------------------------------------------------------
    //  Enum GapPenalty
    // ----------------------------------------------------------------------------

    enum GapPenalty : uint8_t
    {
        LINEAR,
        AFFINE,
        DYNAMIC,
        AUTOMATIC
    };

    // ----------------------------------------------------------------------------
    //  Class FreeEndGaps
    // ----------------------------------------------------------------------------

    struct FreeEndGaps
    {
        static constexpr uint8_t TOP{1};
        static constexpr uint8_t BOTTOM{2};
        static constexpr uint8_t LEFT{4};
        static constexpr uint8_t RIGHT{8};
    };

    // ----------------------------------------------------------------------------
    //  Enum Traceback
    // ----------------------------------------------------------------------------

    enum Traceback : uint8_t
    {
        SCORE_ONLY,
        BEST_ONE,
        BEST_ALL
    };

    // ----------------------------------------------------------------------------
    //  Enum GapsPlacement
    // ----------------------------------------------------------------------------

    enum GapsPlacement : uint8_t
    {
        LEFT,
        RIGHT
    };

    enum OutputFormat : uint8_t
    {
        ANCHOR_GAPS,
        ARRAY_GAPS,
        ALIGNMENT_GRAPH,
        FRAGMENTS
    };
};

template <typename exec_policy_t, typename seq1_t, typename seq2_t, typename configurator_t>
   requires is_execution_policy<exec_policy_t>::value &&
            container_concept<seq1_t> &&
            container_concept<seq2_t>
inline auto 
align(exec_policy_t const & exec_policy,
      seq1_t const & seq1,
      seq2_t const & seq2,
      configurator_t const & config)
{
   // delegate to corresponding functions.
   // depending on configuration we can return several different things, like the alignment and score or just the score or the trace matrix or what ever we want.
   return { ... };
}

template <typename exec_policy_t, typename seq1_t, typename seq2_t, typename configurator_t, typename callback_f>
   requires is_execution_policy<exec_policy_t>::value &&
            container_concept<seq1_t> &&
            container_concept<seq2_t>
inline void
align_and_then(exec_policy_t const & exec_policy,
               seq1_t const & seq1,
               seq2_t const & seq2,
               configurator_t const & config,
               callback_f && callback)
{
   // delegate to corresponding functions.
   // depending on configuration we can callback several different things, like the alignment and score or just the score or the trace matrix or what ever we want.
}