72template <
typename config_t,
typename... algorithm_policies_t>
90 template <
typename alignment_algorithm_t = alignment_algorithm>
91 static auto _alignment_column_t() ->
decltype(std::declval<alignment_algorithm_t>().current_alignment_column());
100 static_assert(!std::same_as<alignment_result_t, empty_type>,
"Alignment result type was not configured.");
138 cfg_ptr{std::make_shared<config_t>(cfg)}
140 this->scoring_scheme = seqan3::get<align_cfg::scoring_scheme>(*cfg_ptr).scheme;
141 this->initialise_alignment_state(*
cfg_ptr);
190 template <indexed_sequence_pair_range indexed_sequence_pairs_t,
typename callback_t>
192 void operator()(indexed_sequence_pairs_t && indexed_sequence_pairs, callback_t && callback)
201 template <indexed_sequence_pair_range indexed_sequence_pairs_t,
typename callback_t>
203 void operator()(indexed_sequence_pairs_t && indexed_sequence_pairs, callback_t && callback)
211 auto sequence1_range = indexed_sequence_pairs | views::elements<0> | views::elements<0>;
212 auto sequence2_range = indexed_sequence_pairs | views::elements<0> | views::elements<1>;
215 this->initialise_find_optimum_policy(sequence1_range,
217 this->scoring_scheme.padding_match_score());
225 this->alignment_state.reset_optimum();
247 template <
typename sequence_range_t>
256 for (
auto && simd_vector_chunk : sequences | views::to_simd<simd_score_t>(this->scoring_scheme.padding_symbol))
257 for (
auto && simd_vector : simd_vector_chunk)
258 simd_sequence.
push_back(std::move(simd_vector));
260 return simd_sequence;
280 template <std::ranges::forward_range sequence1_t, std::ranges::forward_range sequence2_t,
typename callback_t>
282 compute_single_pair(
size_t const idx, sequence1_t && sequence1, sequence2_t && sequence2, callback_t & callback)
290 this->alignment_state.reset_optimum();
296 auto const &
band = get<align_cfg::band_fixed_size>(*
cfg_ptr);
298 auto && [subsequence1, subsequence2] = this->slice_sequences(sequence1, sequence2,
band);
326 template <
typename sequence1_t,
typename sequence2_t>
328 sequence2_t && sequence2,
331 static_assert(config_t::template exists<align_cfg::band_fixed_size>(),
332 "The band configuration is required for the banded alignment algorithm.");
335 static_assert(std::is_signed_v<diff_type>,
"Only signed types can be used to test the band parameters.");
337 if (
static_cast<diff_type
>(
band.lower_diagonal) > std::ranges::distance(sequence1))
340 "Invalid band error: The lower diagonal excludes the whole alignment matrix."};
343 if (
static_cast<diff_type
>(
band.upper_diagonal) < -std::ranges::distance(sequence2))
346 "Invalid band error: The upper diagonal excludes the whole alignment matrix."};
362 template <
typename sequence1_t,
typename sequence2_t>
365 size_t rows = std::ranges::distance(sequence2) + 1;
366 size_t cols = std::ranges::distance(sequence1) + 1;
379 template <
typename sequence1_t,
typename sequence2_t>
387 this->allocate_matrix(sequence1, sequence2);
394 for (
auto const & alphabet1 : sequence1)
396 compute_alignment_column<true>(this->scoring_scheme_profile_column(alphabet1), sequence2);
408 template <
typename sequence1_t,
typename sequence2_t>
417 this->allocate_matrix(sequence1, sequence2,
band, this->alignment_state);
418 using row_index_t = std::ranges::range_difference_t<sequence2_t>;
419 row_index_t last_row_index = this->score_matrix.band_row_index;
426 row_index_t sequence2_size = std::ranges::distance(sequence2);
427 for (
auto const & seq1_value : std::views::take(sequence1, this->score_matrix.band_col_index))
429 compute_alignment_column<true>(seq1_value, std::views::take(sequence2, ++last_row_index));
438 size_t first_row_index = 0;
439 for (
auto const & seq1_value : std::views::drop(sequence1, this->score_matrix.band_col_index))
442 compute_alignment_column<false>(seq1_value, sequence2 |
views::slice(first_row_index++, ++last_row_index));
466 template <
typename sequence2_t>
478 for (
auto it =
std::ranges::begin(sequence2); it != std::ranges::end(sequence2); ++it)
482 bool at_last_row =
true;
484 at_last_row =
static_cast<size_t>(this->score_matrix.band_row_index) == this->score_matrix.num_rows - 1;
504 template <
bool initialise_first_cell,
typename sequence1_value_t,
typename sequence2_t>
507 this->next_alignment_column();
513 if constexpr (initialise_first_cell)
520 this->alignment_state,
521 this->scoring_scheme.score(seq1_value, *seq2_it));
525 for (; seq2_it != std::ranges::end(sequence2); ++seq2_it)
527 this->alignment_state,
528 this->scoring_scheme.score(seq1_value, *seq2_it));
557 this->check_score_of_cells_in_last_column(
alignment_column, this->alignment_state);
587 template <
typename index_t,
typename sequence1_t,
typename sequence2_t,
typename callback_t>
590 [[maybe_unused]] sequence1_t & sequence1,
591 [[maybe_unused]] sequence2_t & sequence2,
592 callback_t & callback)
594 using result_value_t =
typename alignment_result_value_type_accessor<alignment_result_t>::type;
601 "The configuration must contain at least one align_cfg::output_* element.");
603 result_value_t res{};
606 res.sequence1_id = idx;
609 res.sequence2_id = idx;
613 res.score = this->alignment_state.optimum.score;
618 res.end_positions = alignment_coordinate_t{
column_index_type{this->alignment_state.optimum.column_index},
622 res.end_positions.second += res.end_positions.first - this->trace_matrix.band_col_index;
630 detail::matrix_coordinate
const optimum_coordinate{
633 auto trace_res = builder(this->trace_matrix.trace_path(optimum_coordinate));
634 res.begin_positions.first = trace_res.first_sequence_slice_positions.first;
635 res.begin_positions.second = trace_res.second_sequence_slice_positions.first;
638 res.alignment = std::move(trace_res.alignment);
649 callback(std::move(res));
677 template <
typename indexed_sequence_pair_range_t,
typename callback_t>
681 using result_value_t =
typename alignment_result_value_type_accessor<alignment_result_t>::type;
684 for (
auto && [sequence_pairs, alignment_index] : index_sequence_pairs)
686 (void)sequence_pairs;
687 result_value_t res{};
690 res.sequence1_id = alignment_index;
693 res.sequence2_id = alignment_index;
696 res.score = this->alignment_state.optimum.score[
simd_index];
700 res.end_positions.first = this->alignment_state.optimum.column_index[
simd_index];
701 res.end_positions.second = this->alignment_state.optimum.row_index[
simd_index];
704 callback(std::move(res));
721 auto column = this->current_alignment_column();
723 auto coord = get<1>(
column.front()).coordinate;
725 coord.second += coord.first - this->score_matrix.band_col_index;
731 | std::views::transform(
735 return get<0>(tpl).current;
744 | std::views::transform(
748 auto trace = get<1>(tpl).current;
Provides seqan3::detail::align_config_band.
Provides seqan3::align_cfg::scoring_scheme.
Provides seqan3::detail::align_result_selector.
Provides seqan3::aligned_allocator.
Provides seqan3::detail::aligned_sequence_builder.
Includes customized exception types for the alignment module .
Provides concepts needed internally for the alignment algorithms.
Provides helper type traits for the configuration and execution of the alignment algorithm.
Configuration element for setting a fixed size band.
Definition align_config_band.hpp:60
Allocates uninitialized storage whose memory-alignment is specified by alignment.
Definition aligned_allocator.hpp:74
Implements an internal alignment coordinate that can be used as an argument to the std::ranges::iota_...
Definition advanceable_alignment_coordinate.hpp:63
Builds the alignment for a given pair of sequences and the respective trace.
Definition aligned_sequence_builder.hpp:114
The alignment algorithm type to compute standard pairwise alignment using dynamic programming.
Definition alignment_algorithm.hpp:75
constexpr alignment_algorithm(alignment_algorithm &&)=default
Defaulted.
constexpr alignment_algorithm & operator=(alignment_algorithm const &)=default
Defaulted.
constexpr void finalise_last_cell_in_column(bool const at_last_row) noexcept
Finalises the last cell of the current alignment column.
Definition alignment_algorithm.hpp:541
trace_debug_matrix_t trace_debug_matrix
The debug matrix for the traces.
Definition alignment_algorithm.hpp:776
constexpr alignment_algorithm(alignment_algorithm const &)=default
Defaulted.
typename traits_t::alignment_result_type alignment_result_t
The alignment result type.
Definition alignment_algorithm.hpp:98
::is_vectorised constexpr auto make_alignment_result(indexed_sequence_pair_range_t &&index_sequence_pairs, callback_t &callback)
Creates a new alignment result from the current alignment optimum and for the given indexed sequence ...
Definition alignment_algorithm.hpp:679
void compute_matrix(sequence1_t &sequence1, sequence2_t &sequence2, align_cfg::band_fixed_size const &band)
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition alignment_algorithm.hpp:409
void compute_alignment_column(sequence1_value_t const &seq1_value, sequence2_t &&sequence2)
Computes a single alignment column.
Definition alignment_algorithm.hpp:505
constexpr void compute_single_pair(size_t const idx, sequence1_t &&sequence1, sequence2_t &&sequence2, callback_t &callback)
Computes the pairwise sequence alignment for a single pair of sequences.
Definition alignment_algorithm.hpp:282
score_debug_matrix_t score_debug_matrix
The debug matrix for the scores.
Definition alignment_algorithm.hpp:774
constexpr auto convert_batch_of_sequences_to_simd_vector(sequence_range_t &sequences)
Converts a batch of sequences to a sequence of simd vectors.
Definition alignment_algorithm.hpp:248
alignment_column_iterator_t alignment_column_it
Stores the state of the currently processed alignment column.
Definition alignment_algorithm.hpp:772
constexpr alignment_algorithm & operator=(alignment_algorithm &&)=default
Defaulted.
constexpr void check_valid_band_parameter(sequence1_t &&sequence1, sequence2_t &&sequence2, align_cfg::band_fixed_size const &band)
Checks if the band parameters are valid for the given sequences.
Definition alignment_algorithm.hpp:327
constexpr void finalise_alignment() noexcept
Checks the last cell, respectively column for the alignment optimum.
Definition alignment_algorithm.hpp:551
decltype(_alignment_column_t()) alignment_column_t
The type of an alignment column as defined by the respective matrix policy.
Definition alignment_algorithm.hpp:94
auto initialise_first_alignment_column(sequence2_t &&sequence2)
Initialises the first column of the alignment matrix.
Definition alignment_algorithm.hpp:467
~alignment_algorithm()=default
Defaulted.
constexpr alignment_algorithm(config_t const &cfg)
Constructs the algorithm with the passed configuration.
Definition alignment_algorithm.hpp:136
static auto _alignment_column_t() -> decltype(std::declval< alignment_algorithm_t >().current_alignment_column())
Helper function to access ((some_policy *)this)->current_alignment_column().
std::pair< size_t, size_t > max_size_in_collection
The maximal size within the first and the second sequence collection.
Definition alignment_algorithm.hpp:778
std::shared_ptr< config_t > cfg_ptr
The alignment configuration stored on the heap.
Definition alignment_algorithm.hpp:768
alignment_column_t alignment_column
Stores the currently processed alignment column.
Definition alignment_algorithm.hpp:770
constexpr alignment_algorithm()=default
Defaulted.
constexpr void initialise_debug_matrices(sequence1_t &sequence1, sequence2_t &sequence2)
Initialises the debug matrices for the given sequences.
Definition alignment_algorithm.hpp:363
constexpr void make_alignment_result(index_t const idx, sequence1_t &sequence1, sequence2_t &sequence2, callback_t &callback)
Creates a new alignment result from the current alignment optimum and for the given pair of sequences...
Definition alignment_algorithm.hpp:589
void compute_matrix(sequence1_t &sequence1, sequence2_t &sequence2)
Compute the alignment by iterating over the alignment matrix in a column wise manner.
Definition alignment_algorithm.hpp:380
std::ranges::iterator_t< alignment_column_t > alignment_column_iterator_t
The iterator type over the alignment column.
Definition alignment_algorithm.hpp:96
void dump_alignment_column()
Dumps the current alignment matrix in the debug score matrix and if requested debug trace matrix.
Definition alignment_algorithm.hpp:717
::is_vectorised &&std::invocable< callback_t, alignment_result_t > void operator()(indexed_sequence_pairs_t &&indexed_sequence_pairs, callback_t &&callback)
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition alignment_algorithm.hpp:203
A two dimensional matrix used inside of alignment algorithms.
Definition two_dimensional_matrix.hpp:62
Thrown if the configuration of the alignment algorithm is invalid.
Definition alignment/exception.hpp:32
Provides seqan3::detail::deferred_crtp_base.
Provides seqan3::views::elements.
Provides seqan3::detail::empty_type.
Provides various type traits for use on functions.
@ band
ID for the band option.
@ column
The corresponding alignment coordinate will be incrementable/decrementable in the column index.
@ column
Accesses matrix in column major order.
@ carry_left_open
Carry bit for the last left open even if it is not the maximum value.
@ up
Trace comes from the above entry.
@ left
Trace comes from the left entry.
@ carry_up_open
Carry bit for the last up open even if it is not the maximum value.
@ left_open
Trace comes from the left entry, while opening the gap.
@ up_open
Trace comes from the above entry, while opening the gap.
typename deferred_crtp_base_t::template invoke< derived_t > invoke_deferred_crtp_base
Template alias to instantiate the deferred crtp base with the derived class.
Definition deferred_crtp_base.hpp:94
@ offset
Sequence (seqan3::field::seq) relative start position (0-based), unsigned value.
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition slice.hpp:175
A helper concept to check if a type is a sequence pair.
The generic simd concept.
Refines the seqan3::simd::simd_concept requiring the underlying scalar type to model std::integral.
The internal SeqAn3 namespace.
Definition aligned_sequence_concept.hpp:26
constexpr auto const & get(configuration< configs_t... > const &config) noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition configuration.hpp:412
Provides seqan3::simd::simd_type.
Provides seqan3::simd::simd_traits.
A traits type for the alignment algorithm that exposes static information stored within the alignment...
Definition alignment/pairwise/detail/type_traits.hpp:80
static constexpr bool is_banded
Flag indicating whether banded alignment mode is enabled.
Definition alignment/pairwise/detail/type_traits.hpp:120
static constexpr bool is_vectorised
Flag to indicate vectorised mode.
Definition alignment/pairwise/detail/type_traits.hpp:112
std::conditional_t< is_vectorised, simd_type_t< original_score_type >, original_score_type > score_type
The score type for the alignment algorithm.
Definition alignment/pairwise/detail/type_traits.hpp:133
static constexpr bool output_sequence2_id
Flag indicating whether the id of the second sequence shall be returned.
Definition alignment/pairwise/detail/type_traits.hpp:165
static constexpr bool compute_sequence_alignment
Flag indicating whether the sequence alignment shall be computed.
Definition alignment/pairwise/detail/type_traits.hpp:161
static constexpr size_t alignments_per_vector
The number of alignments that can be computed in one simd vector.
Definition alignment/pairwise/detail/type_traits.hpp:146
static constexpr bool compute_begin_positions
Flag indicating whether the begin positions shall be computed.
Definition alignment/pairwise/detail/type_traits.hpp:158
static constexpr bool is_debug
Flag indicating whether debug mode is enabled.
Definition alignment/pairwise/detail/type_traits.hpp:122
static constexpr bool output_sequence1_id
Flag indicating whether the id of the first sequence shall be returned.
Definition alignment/pairwise/detail/type_traits.hpp:163
decltype(determine_alignment_result_type()) alignment_result_type
The alignment result type if present. Otherwise seqan3::detail::empty_type.
Definition alignment/pairwise/detail/type_traits.hpp:137
static constexpr bool compute_end_positions
Flag indicating whether the end positions shall be computed.
Definition alignment/pairwise/detail/type_traits.hpp:156
static constexpr bool compute_score
Flag indicating whether the score shall be computed.
Definition alignment/pairwise/detail/type_traits.hpp:154
A strong type for designated initialisation of the column index of a matrix.
Definition matrix_coordinate.hpp:29
An empty class type used in meta programming.
Definition empty_type.hpp:20
A representation of a location or offset within a two-dimensional matrix.
Definition matrix_coordinate.hpp:87
Strong type for setting the column dimension of a matrix.
Definition two_dimensional_matrix.hpp:29
Strong type for setting the row dimension of a matrix.
Definition two_dimensional_matrix.hpp:37
A strong type for designated initialisation of the row index of a matrix.
Definition matrix_coordinate.hpp:58
Provides seqan3::detail::to_simd view.
Provides the declaration of seqan3::detail::trace_directions.
Provides seqan3::simd::simd_concept.