75template <
typename config_t,
typename... algorithm_policies_t>
93 template <
typename alignment_algorithm_t = alignment_algorithm>
94 static auto _alignment_column_t() ->
decltype(std::declval<alignment_algorithm_t>().current_alignment_column());
103 static_assert(!std::same_as<alignment_result_t, empty_type>,
"Alignment result type was not configured.");
141 cfg_ptr{std::make_shared<config_t>(cfg)}
143 this->scoring_scheme = seqan3::get<align_cfg::scoring_scheme>(*cfg_ptr).scheme;
144 this->initialise_alignment_state(*
cfg_ptr);
193 template <indexed_sequence_pair_range indexed_sequence_pairs_t,
typename callback_t>
195 void operator()(indexed_sequence_pairs_t && indexed_sequence_pairs, callback_t && callback)
204 template <indexed_sequence_pair_range indexed_sequence_pairs_t,
typename callback_t>
206 void operator()(indexed_sequence_pairs_t && indexed_sequence_pairs, callback_t && callback)
214 auto sequence1_range = indexed_sequence_pairs | views::elements<0> | views::elements<0>;
215 auto sequence2_range = indexed_sequence_pairs | views::elements<0> | views::elements<1>;
218 this->initialise_find_optimum_policy(sequence1_range,
220 this->scoring_scheme.padding_match_score());
228 this->alignment_state.reset_optimum();
250 template <
typename sequence_range_t>
259 for (
auto && simd_vector_chunk : sequences | views::to_simd<simd_score_t>(this->scoring_scheme.padding_symbol))
260 for (
auto && simd_vector : simd_vector_chunk)
261 simd_sequence.
push_back(std::move(simd_vector));
263 return simd_sequence;
283 template <std::ranges::forward_range sequence1_t, std::ranges::forward_range sequence2_t,
typename callback_t>
285 compute_single_pair(
size_t const idx, sequence1_t && sequence1, sequence2_t && sequence2, callback_t & callback)
293 this->alignment_state.reset_optimum();
299 auto const &
band = get<align_cfg::band_fixed_size>(*
cfg_ptr);
301 auto && [subsequence1, subsequence2] = this->slice_sequences(sequence1, sequence2,
band);
329 template <
typename sequence1_t,
typename sequence2_t>
331 sequence2_t && sequence2,
334 static_assert(config_t::template exists<align_cfg::band_fixed_size>(),
335 "The band configuration is required for the banded alignment algorithm.");
338 static_assert(std::is_signed_v<diff_type>,
"Only signed types can be used to test the band parameters.");
340 if (
static_cast<diff_type
>(
band.lower_diagonal) > std::ranges::distance(sequence1))
343 "Invalid band error: The lower diagonal excludes the whole alignment matrix."};
346 if (
static_cast<diff_type
>(
band.upper_diagonal) < -std::ranges::distance(sequence2))
349 "Invalid band error: The upper diagonal excludes the whole alignment matrix."};
365 template <
typename sequence1_t,
typename sequence2_t>
368 size_t rows = std::ranges::distance(sequence2) + 1;
369 size_t cols = std::ranges::distance(sequence1) + 1;
382 template <
typename sequence1_t,
typename sequence2_t>
390 this->allocate_matrix(sequence1, sequence2);
397 for (
auto const & alphabet1 : sequence1)
399 compute_alignment_column<true>(this->scoring_scheme_profile_column(alphabet1), sequence2);
411 template <
typename sequence1_t,
typename sequence2_t>
420 this->allocate_matrix(sequence1, sequence2,
band, this->alignment_state);
421 using row_index_t = std::ranges::range_difference_t<sequence2_t>;
422 row_index_t last_row_index = this->score_matrix.band_row_index;
429 row_index_t sequence2_size = std::ranges::distance(sequence2);
430 for (
auto const & seq1_value :
std::views::take(sequence1, this->score_matrix.band_col_index))
432 compute_alignment_column<true>(seq1_value,
std::views::take(sequence2, ++last_row_index));
441 size_t first_row_index = 0;
442 for (
auto const & seq1_value :
std::views::drop(sequence1, this->score_matrix.band_col_index))
445 compute_alignment_column<false>(seq1_value, sequence2 |
views::slice(first_row_index++, ++last_row_index));
469 template <
typename sequence2_t>
481 for (
auto it =
std::ranges::begin(sequence2); it != std::ranges::end(sequence2); ++it)
485 bool at_last_row =
true;
487 at_last_row =
static_cast<size_t>(this->score_matrix.band_row_index) == this->score_matrix.num_rows - 1;
507 template <
bool initialise_first_cell,
typename sequence1_value_t,
typename sequence2_t>
510 this->next_alignment_column();
516 if constexpr (initialise_first_cell)
523 this->alignment_state,
524 this->scoring_scheme.score(seq1_value, *seq2_it));
528 for (; seq2_it != std::ranges::end(sequence2); ++seq2_it)
530 this->alignment_state,
531 this->scoring_scheme.score(seq1_value, *seq2_it));
560 this->check_score_of_cells_in_last_column(
alignment_column, this->alignment_state);
590 template <
typename index_t,
typename sequence1_t,
typename sequence2_t,
typename callback_t>
593 [[maybe_unused]] sequence1_t & sequence1,
594 [[maybe_unused]] sequence2_t & sequence2,
595 callback_t & callback)
597 using result_value_t =
typename alignment_result_value_type_accessor<alignment_result_t>::type;
604 "The configuration must contain at least one align_cfg::output_* element.");
606 result_value_t res{};
609 res.sequence1_id = idx;
612 res.sequence2_id = idx;
616 res.score = this->alignment_state.optimum.score;
621 res.end_positions = alignment_coordinate_t{
column_index_type{this->alignment_state.optimum.column_index},
625 res.end_positions.second += res.end_positions.first - this->trace_matrix.band_col_index;
633 detail::matrix_coordinate
const optimum_coordinate{
636 auto trace_res = builder(this->trace_matrix.trace_path(optimum_coordinate));
637 res.begin_positions.first = trace_res.first_sequence_slice_positions.first;
638 res.begin_positions.second = trace_res.second_sequence_slice_positions.first;
641 res.alignment = std::move(trace_res.alignment);
652 callback(std::move(res));
680 template <
typename indexed_sequence_pair_range_t,
typename callback_t>
684 using result_value_t =
typename alignment_result_value_type_accessor<alignment_result_t>::type;
687 for (
auto && [sequence_pairs, alignment_index] : index_sequence_pairs)
689 (void)sequence_pairs;
690 result_value_t res{};
693 res.sequence1_id = alignment_index;
696 res.sequence2_id = alignment_index;
699 res.score = this->alignment_state.optimum.score[
simd_index];
703 res.end_positions.first = this->alignment_state.optimum.column_index[
simd_index];
704 res.end_positions.second = this->alignment_state.optimum.row_index[
simd_index];
707 callback(std::move(res));
724 auto column = this->current_alignment_column();
726 auto coord = get<1>(
column.front()).coordinate;
728 coord.second += coord.first - this->score_matrix.band_col_index;
738 return get<0>(tpl).current;
740 score_debug_matrix.begin() +
offset);
743 if constexpr (traits_t::compute_sequence_alignment)
745 auto trace_matrix_it = trace_debug_matrix.begin() +
offset;
752 auto trace = get<1>(tpl).current;
767 trace_debug_matrix.begin() +
offset);
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:63
Allocates uninitialized storage whose memory-alignment is specified by alignment.
Definition: aligned_allocator.hpp:77
Implements an internal alignment coordinate that can be used as an argument to the std::ranges::iota_...
Definition: advanceable_alignment_coordinate.hpp:66
Builds the alignment for a given pair of sequences and the respective trace.
Definition: aligned_sequence_builder.hpp:117
The alignment algorithm type to compute standard pairwise alignment using dynamic programming.
Definition: alignment_algorithm.hpp:78
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:544
trace_debug_matrix_t trace_debug_matrix
The debug matrix for the traces.
Definition: alignment_algorithm.hpp:780
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:101
::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:682
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:412
void compute_alignment_column(sequence1_value_t const &seq1_value, sequence2_t &&sequence2)
Computes a single alignment column.
Definition: alignment_algorithm.hpp:508
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:285
score_debug_matrix_t score_debug_matrix
The debug matrix for the scores.
Definition: alignment_algorithm.hpp:778
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:251
alignment_column_iterator_t alignment_column_it
Stores the state of the currently processed alignment column.
Definition: alignment_algorithm.hpp:776
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:330
constexpr void finalise_alignment() noexcept
Checks the last cell, respectively column for the alignment optimum.
Definition: alignment_algorithm.hpp:554
decltype(_alignment_column_t()) alignment_column_t
The type of an alignment column as defined by the respective matrix policy.
Definition: alignment_algorithm.hpp:97
auto initialise_first_alignment_column(sequence2_t &&sequence2)
Initialises the first column of the alignment matrix.
Definition: alignment_algorithm.hpp:470
~alignment_algorithm()=default
Defaulted.
constexpr alignment_algorithm(config_t const &cfg)
Constructs the algorithm with the passed configuration.
Definition: alignment_algorithm.hpp:139
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:782
std::shared_ptr< config_t > cfg_ptr
The alignment configuration stored on the heap.
Definition: alignment_algorithm.hpp:772
alignment_column_t alignment_column
Stores the currently processed alignment column.
Definition: alignment_algorithm.hpp:774
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:366
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:592
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:383
std::ranges::iterator_t< alignment_column_t > alignment_column_iterator_t
The iterator type over the alignment column.
Definition: alignment_algorithm.hpp:99
void dump_alignment_column()
Dumps the current alignment matrix in the debug score matrix and if requested debug trace matrix.
Definition: alignment_algorithm.hpp:720
::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:206
A two dimensional matrix used inside of alignment algorithms.
Definition: two_dimensional_matrix.hpp:65
Thrown if the configuration of the alignment algorithm is invalid.
Definition: alignment/exception.hpp:35
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:97
@ offset
Sequence (seqan3::field::seq) relative start position (0-based), unsigned value.
typename decltype(detail::split_after< i >(list_t{}))::first_type take
Return a seqan3::type_list of the first n types in the input type list.
Definition: type_list/traits.hpp:377
typename decltype(detail::split_after< i >(list_t{}))::second_type drop
Return a seqan3::type_list of the types in the input type list, except the first n.
Definition: type_list/traits.hpp:395
decltype(detail::transform< trait_t >(list_t{})) transform
Apply a transformation trait to every type in the list and return a seqan3::type_list of the results.
Definition: type_list/traits.hpp:470
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition: slice.hpp:178
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:29
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:415
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:83
static constexpr bool is_banded
Flag indicating whether banded alignment mode is enabled.
Definition: alignment/pairwise/detail/type_traits.hpp:123
static constexpr bool is_vectorised
Flag to indicate vectorised mode.
Definition: alignment/pairwise/detail/type_traits.hpp:115
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:136
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:169
static constexpr bool compute_sequence_alignment
Flag indicating whether the sequence alignment shall be computed.
Definition: alignment/pairwise/detail/type_traits.hpp:165
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:149
static constexpr bool compute_begin_positions
Flag indicating whether the begin positions shall be computed.
Definition: alignment/pairwise/detail/type_traits.hpp:162
static constexpr bool is_debug
Flag indicating whether debug mode is enabled.
Definition: alignment/pairwise/detail/type_traits.hpp:125
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:167
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:140
static constexpr bool compute_end_positions
Flag indicating whether the end positions shall be computed.
Definition: alignment/pairwise/detail/type_traits.hpp:160
static constexpr bool compute_score
Flag indicating whether the score shall be computed.
Definition: alignment/pairwise/detail/type_traits.hpp:158
A strong type for designated initialisation of the column index of a matrix.
Definition: matrix_coordinate.hpp:32
An empty class type used in meta programming.
Definition: empty_type.hpp:23
A representation of a location or offset within a two-dimensional matrix.
Definition: matrix_coordinate.hpp:90
Strong type for setting the column dimension of a matrix.
Definition: two_dimensional_matrix.hpp:32
Strong type for setting the row dimension of a matrix.
Definition: two_dimensional_matrix.hpp:40
A strong type for designated initialisation of the row index of a matrix.
Definition: matrix_coordinate.hpp:61
Provides seqan3::detail::to_simd view.
Provides the declaration of seqan3::detail::trace_directions.
Provides seqan3::simd::simd_concept.