19 #include <type_traits>
77 template <
typename config_t,
typename ...algorithm_policies_t>
86 using alignment_column_t = decltype(std::declval<alignment_algorithm>().current_alignment_column());
92 static_assert(!std::same_as<alignment_result_t, empty_type>,
"Alignment result type was not configured.");
130 cfg_ptr{std::make_shared<config_t>(cfg)}
132 this->scoring_scheme = seqan3::get<align_cfg::scoring_scheme>(*cfg_ptr).scheme;
133 this->initialise_alignment_state(*
cfg_ptr);
182 template <indexed_sequence_pair_range indexed_sequence_pairs_t,
typename callback_t>
186 void operator()(indexed_sequence_pairs_t && indexed_sequence_pairs, callback_t && callback)
195 template <indexed_sequence_pair_range indexed_sequence_pairs_t,
typename callback_t>
199 void operator()(indexed_sequence_pairs_t && indexed_sequence_pairs, callback_t && callback)
207 auto sequence1_range = indexed_sequence_pairs | views::get<0> | views::get<0>;
208 auto sequence2_range = indexed_sequence_pairs | views::get<0> | views::get<1>;
211 this->initialise_find_optimum_policy(sequence1_range,
213 this->scoring_scheme.padding_match_score());
221 this->alignment_state.reset_optimum();
243 template <
typename sequence_range_t>
252 for (
auto && simd_vector_chunk : sequences | views::to_simd<simd_score_t>(this->scoring_scheme.padding_symbol))
253 for (
auto && simd_vector : simd_vector_chunk)
256 return simd_sequence;
276 template <std::ranges::forward_range sequence1_t,
277 std::ranges::forward_range sequence2_t,
280 sequence1_t && sequence1,
281 sequence2_t && sequence2,
282 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))
341 "Invalid band error: The lower diagonal excludes the whole alignment matrix."
345 if (
static_cast<diff_type
>(
band.upper_diagonal) < -std::ranges::distance(sequence2))
349 "Invalid band error: The upper diagonal excludes the whole alignment matrix."
366 template <
typename sequence1_t,
typename sequence2_t>
369 size_t rows = std::ranges::distance(sequence2) + 1;
370 size_t cols = std::ranges::distance(sequence1) + 1;
383 template <
typename sequence1_t,
typename sequence2_t>
393 this->allocate_matrix(sequence1, sequence2);
400 for (
auto const & alphabet1 : sequence1)
402 compute_alignment_column<true>(this->scoring_scheme_profile_column(alphabet1), sequence2);
414 template <
typename sequence1_t,
typename sequence2_t>
425 this->allocate_matrix(sequence1, sequence2,
band, this->alignment_state);
426 size_t last_row_index = this->score_matrix.band_row_index;
433 size_t sequence2_size = std::ranges::distance(sequence2);
434 for (
auto const & seq1_value : sequence1 |
views::take(this->score_matrix.band_col_index))
436 compute_alignment_column<true>(seq1_value, sequence2 |
views::take(++last_row_index));
445 size_t first_row_index = 0;
446 for (
auto const & seq1_value : sequence1 |
views::drop(this->score_matrix.band_col_index))
449 compute_alignment_column<false>(seq1_value, sequence2 |
views::slice(first_row_index++, ++last_row_index));
473 template <
typename sequence2_t>
485 for (
auto it = std::ranges::begin(sequence2); it != std::ranges::end(sequence2); ++it)
489 bool at_last_row =
true;
491 at_last_row =
static_cast<size_t>(this->score_matrix.band_row_index) == this->score_matrix.num_rows - 1;
511 template <
bool initialise_first_cell,
typename sequence1_value_t,
typename sequence2_t>
514 this->next_alignment_column();
518 auto seq2_it = std::ranges::begin(sequence2);
520 if constexpr (initialise_first_cell)
527 this->alignment_state,
528 this->scoring_scheme.score(seq1_value, *seq2_it));
532 for (; seq2_it != std::ranges::end(sequence2); ++seq2_it)
534 this->alignment_state,
535 this->scoring_scheme.score(seq1_value, *seq2_it));
564 this->check_score_of_cells_in_last_column(
alignment_column, this->alignment_state);
594 template <
typename index_t,
typename sequence1_t,
typename sequence2_t,
typename callback_t>
599 [[maybe_unused]] sequence1_t & sequence1,
600 [[maybe_unused]] sequence2_t & sequence2,
601 callback_t & callback)
603 using result_value_t =
typename alignment_result_value_type_accessor<alignment_result_t>::type;
610 "The configuration must contain at least one align_cfg::output_* element.");
612 result_value_t res{};
615 res.sequence1_id = idx;
618 res.sequence2_id = idx;
622 res.score = this->alignment_state.optimum.score;
630 res.end_positions.second += res.end_positions.first - this->trace_matrix.band_col_index;
639 auto trace_res = builder(this->trace_matrix.trace_path(optimum_coordinate));
640 res.begin_positions.first = trace_res.first_sequence_slice_positions.first;
641 res.begin_positions.second = trace_res.second_sequence_slice_positions.first;
644 res.alignment =
std::move(trace_res.alignment);
683 template <
typename indexed_sequence_pair_range_t,
typename callback_t>
688 callback_t & callback)
690 using result_value_t =
typename alignment_result_value_type_accessor<alignment_result_t>::type;
693 for (
auto && [sequence_pairs, alignment_index] : index_sequence_pairs)
695 (void) sequence_pairs;
696 result_value_t res{};
699 res.sequence1_id = alignment_index;
702 res.sequence2_id = alignment_index;
705 res.score = this->alignment_state.optimum.score[
simd_index];
709 res.end_positions.first = this->alignment_state.optimum.column_index[
simd_index];
710 res.end_positions.second = this->alignment_state.optimum.row_index[
simd_index];
730 auto column = this->current_alignment_column();
732 auto coord = get<1>(
column.front()).coordinate;
734 coord.second += coord.first - this->score_matrix.band_col_index;
742 return get<0>(tpl).current;
752 return 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:72
Allocates uninitialized storage whose memory-alignment is specified by alignment.
Definition: aligned_allocator.hpp:72
Represents the begin/end of the pairwise alignment in the respective sequences.
Definition: alignment_coordinate.hpp:341
Builds the alignment for a given pair of sequences and the respective trace.
Definition: aligned_sequence_builder.hpp:118
The alignment algorithm type to compute standard pairwise alignment using dynamic programming.
Definition: alignment_algorithm.hpp:80
constexpr alignment_algorithm(alignment_algorithm &&)=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:548
trace_debug_matrix_t trace_debug_matrix
The debug matrix for the traces.
Definition: alignment_algorithm.hpp:766
constexpr alignment_algorithm(alignment_algorithm const &)=default
Defaulted.
constexpr void make_alignment_result([[maybe_unused]] index_t const idx, [[maybe_unused]] sequence1_t &sequence1, [[maybe_unused]] 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:598
typename traits_t::alignment_result_type alignment_result_t
The alignment result type.
Definition: alignment_algorithm.hpp:90
void compute_alignment_column(sequence1_value_t const &seq1_value, sequence2_t &&sequence2)
Computes a single alignment column.
Definition: alignment_algorithm.hpp:512
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:279
void operator()(indexed_sequence_pairs_t &&indexed_sequence_pairs, callback_t &&callback)
Computes the pairwise sequence alignment for the given range over indexed sequence pairs.
Definition: alignment_algorithm.hpp:186
score_debug_matrix_t score_debug_matrix
The debug matrix for the scores.
Definition: alignment_algorithm.hpp:764
constexpr alignment_algorithm & operator=(alignment_algorithm const &)=default
Defaulted.
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:244
alignment_column_iterator_t alignment_column_it
Stores the state of the currently processed alignment column.
Definition: alignment_algorithm.hpp:762
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:558
auto initialise_first_alignment_column(sequence2_t &&sequence2)
Initialises the first column of the alignment matrix.
Definition: alignment_algorithm.hpp:474
~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:687
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:384
constexpr alignment_algorithm(config_t const &cfg)
Constructs the algorithm with the passed configuration.
Definition: alignment_algorithm.hpp:128
constexpr alignment_algorithm & operator=(alignment_algorithm &&)=default
Defaulted.
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:415
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:768
std::shared_ptr< config_t > cfg_ptr
The alignment configuration stored on the heap.
Definition: alignment_algorithm.hpp:758
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:86
alignment_column_t alignment_column
Stores the currently processed alignment column.
Definition: alignment_algorithm.hpp:760
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:367
std::ranges::iterator_t< alignment_column_t > alignment_column_iterator_t
The iterator type over the alignment column.
Definition: alignment_algorithm.hpp:88
void dump_alignment_column()
Dumps the current alignment matrix in the debug score matrix and if requested debug trace matrix.
Definition: alignment_algorithm.hpp:726
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::drop.
Provides seqan3::detail::empty_type.
Provides various type traits for use on functions.
Provides seqan3::views::get.
@ 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.
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:434
constexpr auto drop
A view adaptor that returns all elements after n from the underlying range (or an empty range if the ...
Definition: drop.hpp:172
auto const get
A view calling std::get on each element in a range.
Definition: get.hpp:66
constexpr auto take
A view adaptor that returns the first size elements from the underlying range (or less if the underly...
Definition: take.hpp:611
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition: slice.hpp:145
auto const move
A view that turns lvalue-references into rvalue-references.
Definition: move.hpp:70
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:434
Adaptations of concepts from the Ranges TS.
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::views::take.
Provides seqan3::detail::to_simd view.
Provides the declaration of seqan3::detail::trace_directions.
Provides seqan3::simd::simd_concept.
Provides seqan3::simd::simd_type.
Provides seqan3::simd::simd_traits.