75template <
typename config_t,
typename ...algorithm_policies_t>
84 using alignment_column_t =
decltype(std::declval<alignment_algorithm>().current_alignment_column());
90 static_assert(!std::same_as<alignment_result_t, empty_type>,
"Alignment result type was not configured.");
128 cfg_ptr{std::make_shared<config_t>(cfg)}
130 this->scoring_scheme = seqan3::get<align_cfg::scoring_scheme>(*cfg_ptr).scheme;
131 this->initialise_alignment_state(*
cfg_ptr);
180 template <indexed_sequence_pair_range indexed_sequence_pairs_t,
typename callback_t>
184 void operator()(indexed_sequence_pairs_t && indexed_sequence_pairs, callback_t && callback)
193 template <indexed_sequence_pair_range indexed_sequence_pairs_t,
typename callback_t>
197 void operator()(indexed_sequence_pairs_t && indexed_sequence_pairs, callback_t && callback)
205 auto sequence1_range = indexed_sequence_pairs | views::elements<0> | views::elements<0>;
206 auto sequence2_range = indexed_sequence_pairs | views::elements<0> | views::elements<1>;
209 this->initialise_find_optimum_policy(sequence1_range,
211 this->scoring_scheme.padding_match_score());
219 this->alignment_state.reset_optimum();
241 template <
typename sequence_range_t>
250 for (
auto && simd_vector_chunk : sequences | views::to_simd<simd_score_t>(this->scoring_scheme.padding_symbol))
251 for (
auto && simd_vector : simd_vector_chunk)
252 simd_sequence.
push_back(std::move(simd_vector));
254 return simd_sequence;
274 template <std::ranges::forward_range sequence1_t,
275 std::ranges::forward_range sequence2_t,
278 sequence1_t && sequence1,
279 sequence2_t && sequence2,
280 callback_t & callback)
288 this->alignment_state.reset_optimum();
294 auto const &
band = get<align_cfg::band_fixed_size>(*
cfg_ptr);
296 auto && [subsequence1, subsequence2] = this->slice_sequences(sequence1, sequence2,
band);
324 template <
typename sequence1_t,
typename sequence2_t>
326 sequence2_t && sequence2,
329 static_assert(config_t::template exists<align_cfg::band_fixed_size>(),
330 "The band configuration is required for the banded alignment algorithm.");
333 static_assert(std::is_signed_v<diff_type>,
"Only signed types can be used to test the band parameters.");
335 if (
static_cast<diff_type
>(
band.lower_diagonal) > std::ranges::distance(sequence1))
339 "Invalid band error: The lower diagonal excludes the whole alignment matrix."
343 if (
static_cast<diff_type
>(
band.upper_diagonal) < -std::ranges::distance(sequence2))
347 "Invalid band error: The upper diagonal excludes the whole alignment matrix."
364 template <
typename sequence1_t,
typename sequence2_t>
367 size_t rows = std::ranges::distance(sequence2) + 1;
368 size_t cols = std::ranges::distance(sequence1) + 1;
381 template <
typename sequence1_t,
typename sequence2_t>
391 this->allocate_matrix(sequence1, sequence2);
398 for (
auto const & alphabet1 : sequence1)
400 compute_alignment_column<true>(this->scoring_scheme_profile_column(alphabet1), sequence2);
412 template <
typename sequence1_t,
typename sequence2_t>
423 this->allocate_matrix(sequence1, sequence2,
band, this->alignment_state);
424 using row_index_t = std::ranges::range_difference_t<sequence2_t>;
425 row_index_t last_row_index = this->score_matrix.band_row_index;
432 row_index_t sequence2_size = std::ranges::distance(sequence2);
433 for (
auto const & seq1_value :
std::views::take(sequence1, this->score_matrix.band_col_index))
435 compute_alignment_column<true>(seq1_value,
std::views::take(sequence2, ++last_row_index));
444 size_t first_row_index = 0;
445 for (
auto const & seq1_value :
std::views::drop(sequence1, this->score_matrix.band_col_index))
448 compute_alignment_column<false>(seq1_value, sequence2 |
views::slice(first_row_index++, ++last_row_index));
472 template <
typename sequence2_t>
484 for (
auto it = std::ranges::begin(sequence2); it != std::ranges::end(sequence2); ++it)
488 bool at_last_row =
true;
490 at_last_row =
static_cast<size_t>(this->score_matrix.band_row_index) == this->score_matrix.num_rows - 1;
510 template <
bool initialise_first_cell,
typename sequence1_value_t,
typename sequence2_t>
513 this->next_alignment_column();
517 auto seq2_it = std::ranges::begin(sequence2);
519 if constexpr (initialise_first_cell)
526 this->alignment_state,
527 this->scoring_scheme.score(seq1_value, *seq2_it));
531 for (; seq2_it != std::ranges::end(sequence2); ++seq2_it)
533 this->alignment_state,
534 this->scoring_scheme.score(seq1_value, *seq2_it));
563 this->check_score_of_cells_in_last_column(
alignment_column, this->alignment_state);
593 template <
typename index_t,
typename sequence1_t,
typename sequence2_t,
typename callback_t>
598 [[maybe_unused]] sequence1_t & sequence1,
599 [[maybe_unused]] sequence2_t & sequence2,
600 callback_t & callback)
602 using result_value_t =
typename alignment_result_value_type_accessor<alignment_result_t>::type;
609 "The configuration must contain at least one align_cfg::output_* element.");
611 result_value_t res{};
614 res.sequence1_id = idx;
617 res.sequence2_id = idx;
621 res.score = this->alignment_state.optimum.score;
626 res.end_positions = alignment_coordinate_t{
column_index_type{this->alignment_state.optimum.column_index},
630 res.end_positions.second += res.end_positions.first - this->trace_matrix.band_col_index;
638 detail::matrix_coordinate
const optimum_coordinate
643 auto trace_res = builder(this->trace_matrix.trace_path(optimum_coordinate));
644 res.begin_positions.first = trace_res.first_sequence_slice_positions.first;
645 res.begin_positions.second = trace_res.second_sequence_slice_positions.first;
648 res.alignment = std::move(trace_res.alignment);
659 callback(std::move(res));
687 template <
typename indexed_sequence_pair_range_t,
typename callback_t>
692 callback_t & callback)
694 using result_value_t =
typename alignment_result_value_type_accessor<alignment_result_t>::type;
697 for (
auto && [sequence_pairs, alignment_index] : index_sequence_pairs)
699 (void) sequence_pairs;
700 result_value_t res{};
703 res.sequence1_id = alignment_index;
706 res.sequence2_id = alignment_index;
709 res.score = this->alignment_state.optimum.score[
simd_index];
713 res.end_positions.first = this->alignment_state.optimum.column_index[
simd_index];
714 res.end_positions.second = this->alignment_state.optimum.row_index[
simd_index];
717 callback(std::move(res));
734 auto column = this->current_alignment_column();
736 auto coord = get<1>(
column.front()).coordinate;
738 coord.second += coord.first - this->score_matrix.band_col_index;
746 return get<0>(tpl).current;
747 }), score_debug_matrix.begin() +
offset);
750 if constexpr (traits_t::compute_sequence_alignment)
752 auto trace_matrix_it = trace_debug_matrix.begin() +
offset;
756 return get<1>(tpl).current;
757 }), 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:74
Allocates uninitialized storage whose memory-alignment is specified by alignment.
Definition: aligned_allocator.hpp:72
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:547
trace_debug_matrix_t trace_debug_matrix
The debug matrix for the traces.
Definition: alignment_algorithm.hpp:770
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:88
void compute_alignment_column(sequence1_value_t const &seq1_value, sequence2_t &&sequence2)
Computes a single alignment column.
Definition: alignment_algorithm.hpp:511
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:277
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:197
score_debug_matrix_t score_debug_matrix
The debug matrix for the scores.
Definition: alignment_algorithm.hpp:768
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:242
alignment_column_iterator_t alignment_column_it
Stores the state of the currently processed alignment column.
Definition: alignment_algorithm.hpp:766
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:325
constexpr void finalise_alignment() noexcept
Checks the last cell, respectively column for the alignment optimum.
Definition: alignment_algorithm.hpp:557
auto initialise_first_alignment_column(sequence2_t &&sequence2)
Initialises the first column of the alignment matrix.
Definition: alignment_algorithm.hpp:473
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:597
~alignment_algorithm()=default
Defaulted.
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:691
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:382
constexpr alignment_algorithm(config_t const &cfg)
Constructs the algorithm with the passed configuration.
Definition: alignment_algorithm.hpp:126
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:413
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:772
std::shared_ptr< config_t > cfg_ptr
The alignment configuration stored on the heap.
Definition: alignment_algorithm.hpp:762
decltype(std::declval< alignment_algorithm >().current_alignment_column()) alignment_column_t
The type of an alignment column as defined by the respective matrix policy.
Definition: alignment_algorithm.hpp:84
alignment_column_t alignment_column
Stores the currently processed alignment column.
Definition: alignment_algorithm.hpp:764
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:365
std::ranges::iterator_t< alignment_column_t > alignment_column_iterator_t
The iterator type over the alignment column.
Definition: alignment_algorithm.hpp:86
void dump_alignment_column()
Dumps the current alignment matrix in the debug score matrix and if requested debug trace matrix.
Definition: alignment_algorithm.hpp:730
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: exception.hpp:34
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.
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:99
@ 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: traits.hpp:368
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: traits.hpp:388
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: traits.hpp:471
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition: slice.hpp:183
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.
Provides C++20 additions to the <iterator> header.
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:429
Adaptations of concepts from the Ranges TS.
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: type_traits.hpp:87
static constexpr bool is_banded
Flag indicating whether banded alignment mode is enabled.
Definition: type_traits.hpp:130
static constexpr bool is_vectorised
Flag to indicate vectorised mode.
Definition: type_traits.hpp:121
std::conditional_t< is_vectorised, simd_type_t< original_score_type >, original_score_type > score_type
The score type for the alignment algorithm.
Definition: type_traits.hpp:143
static constexpr bool output_sequence2_id
Flag indicating whether the id of the second sequence shall be returned.
Definition: type_traits.hpp:180
static constexpr bool compute_sequence_alignment
Flag indicating whether the sequence alignment shall be computed.
Definition: type_traits.hpp:174
static constexpr size_t alignments_per_vector
The number of alignments that can be computed in one simd vector.
Definition: type_traits.hpp:158
static constexpr bool compute_begin_positions
Flag indicating whether the begin positions shall be computed.
Definition: type_traits.hpp:171
static constexpr bool is_debug
Flag indicating whether debug mode is enabled.
Definition: type_traits.hpp:132
static constexpr bool output_sequence1_id
Flag indicating whether the id of the first sequence shall be returned.
Definition: type_traits.hpp:177
decltype(determine_alignment_result_type()) alignment_result_type
The alignment result type if present. Otherwise seqan3::detail::empty_type.
Definition: type_traits.hpp:147
static constexpr bool compute_end_positions
Flag indicating whether the end positions shall be computed.
Definition: type_traits.hpp:168
static constexpr bool compute_score
Flag indicating whether the score shall be computed.
Definition: type_traits.hpp:166
A strong type for designated initialisation of the column index of a matrix.
Definition: matrix_coordinate.hpp:34
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:96
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:65
Provides seqan3::detail::to_simd view.
Provides the declaration of seqan3::detail::trace_directions.
Provides seqan3::simd::simd_concept.