19#include <seqan3/utility/simd/views/to_simd.hpp>
22namespace seqan3::detail
41template <
typename alignment_configuration_t,
typename... policies_t>
42 requires is_type_specialisation_of_v<alignment_configuration_t, configuration>
43class pairwise_alignment_algorithm :
protected policies_t...
47 using traits_type = alignment_configuration_traits<alignment_configuration_t>;
49 using score_type =
typename traits_type::score_type;
51 using alignment_result_type =
typename traits_type::alignment_result_type;
53 static_assert(!std::same_as<alignment_result_type, empty_type>,
"Alignment result type was not configured.");
59 pairwise_alignment_algorithm() =
default;
60 pairwise_alignment_algorithm(pairwise_alignment_algorithm
const &) =
default;
61 pairwise_alignment_algorithm(pairwise_alignment_algorithm &&) =
default;
62 pairwise_alignment_algorithm & operator=(pairwise_alignment_algorithm
const &) =
default;
63 pairwise_alignment_algorithm & operator=(pairwise_alignment_algorithm &&) =
default;
64 ~pairwise_alignment_algorithm() =
default;
73 pairwise_alignment_algorithm(alignment_configuration_t
const & config) : policies_t(config)...
122 template <indexed_sequence_pair_range indexed_sequence_pairs_t,
typename callback_t>
123 requires std::invocable<callback_t, alignment_result_type>
124 void operator()(indexed_sequence_pairs_t && indexed_sequence_pairs, callback_t && callback)
128 for (
auto && [sequence_pair, idx] : indexed_sequence_pairs)
130 size_t const sequence1_size = std::ranges::distance(get<0>(sequence_pair));
131 size_t const sequence2_size = std::ranges::distance(get<1>(sequence_pair));
133 auto && [alignment_matrix, index_matrix] = this->acquire_matrices(sequence1_size, sequence2_size);
135 compute_matrix(get<0>(sequence_pair), get<1>(sequence_pair), alignment_matrix, index_matrix);
136 this->make_result_and_invoke(
std::forward<
decltype(sequence_pair)>(sequence_pair),
139 this->optimal_coordinate,
147 template <indexed_sequence_pair_range indexed_sequence_pairs_t,
typename callback_t>
148 requires traits_type::is_vectorised && std::invocable<callback_t, alignment_result_type>
149 auto operator()(indexed_sequence_pairs_t && indexed_sequence_pairs, callback_t && callback)
151 using simd_collection_t =
std::vector<score_type, aligned_allocator<score_type,
alignof(score_type)>>;
152 using original_score_t =
typename traits_type::original_score_type;
155 auto seq1_collection = indexed_sequence_pairs | views::elements<0> | views::elements<0>;
156 auto seq2_collection = indexed_sequence_pairs | views::elements<0> | views::elements<1>;
158 this->initialise_tracker(seq1_collection, seq2_collection);
161 thread_local simd_collection_t simd_seq1_collection{};
162 thread_local simd_collection_t simd_seq2_collection{};
164 convert_batch_of_sequences_to_simd_vector(simd_seq1_collection,
166 this->scoring_scheme.padding_symbol);
167 convert_batch_of_sequences_to_simd_vector(simd_seq2_collection,
169 this->scoring_scheme.padding_symbol);
171 size_t const sequence1_size = std::ranges::distance(simd_seq1_collection);
172 size_t const sequence2_size = std::ranges::distance(simd_seq2_collection);
174 auto && [alignment_matrix, index_matrix] = this->acquire_matrices(sequence1_size, sequence2_size);
176 compute_matrix(simd_seq1_collection, simd_seq2_collection, alignment_matrix, index_matrix);
179 for (
auto && [sequence_pair, idx] : indexed_sequence_pairs)
181 original_score_t score = this->optimal_score[index]
182 - (this->padding_offsets[index] * this->scoring_scheme.padding_match_score());
183 matrix_coordinate coordinate{row_index_type{
size_t{this->optimal_coordinate.row[index]}},
184 column_index_type{
size_t{this->optimal_coordinate.col[index]}}};
185 this->make_result_and_invoke(
std::forward<
decltype(sequence_pair)>(sequence_pair),
188 std::move(coordinate),
215 template <
typename simd_sequence_t, std::ranges::forward_range sequence_collection_t, arithmetic padding_symbol_t>
216 requires std::ranges::output_range<simd_sequence_t, score_type>
217 void convert_batch_of_sequences_to_simd_vector(simd_sequence_t & simd_sequence,
218 sequence_collection_t & sequences,
219 padding_symbol_t
const & padding_symbol)
221 assert(
static_cast<size_t>(std::ranges::distance(sequences)) <= traits_type::alignments_per_vector);
223 simd_sequence.clear();
224 for (
auto && simd_vector_chunk : sequences | views::to_simd<score_type>(padding_symbol))
241 template <std::ranges::forward_range sequence1_t,
242 std::ranges::forward_range sequence2_t,
243 std::ranges::input_range alignment_matrix_t,
244 std::ranges::input_range index_matrix_t>
245 requires std::ranges::forward_range<std::ranges::range_reference_t<alignment_matrix_t>>
246 && std::ranges::forward_range<std::ranges::range_reference_t<index_matrix_t>>
247 void compute_matrix(sequence1_t && sequence1,
248 sequence2_t && sequence2,
249 alignment_matrix_t && alignment_matrix,
250 index_matrix_t && index_matrix)
256 this->reset_optimum();
258 auto alignment_matrix_it = alignment_matrix.begin();
259 auto indexed_matrix_it = index_matrix.begin();
261 initialise_column(*alignment_matrix_it, *indexed_matrix_it, sequence2);
267 for (
auto alphabet1 : sequence1)
268 compute_column(*++alignment_matrix_it,
269 *++indexed_matrix_it,
270 this->scoring_scheme_profile_column(alphabet1),
277 auto && alignment_column = *alignment_matrix_it;
278 auto && cell_index_column = *indexed_matrix_it;
280 auto alignment_column_it = alignment_column.begin();
281 auto cell_index_column_it = cell_index_column.begin();
283 this->track_last_column_cell(*alignment_column_it, *cell_index_column_it);
285 for ([[maybe_unused]]
auto && unused : sequence2)
286 this->track_last_column_cell(*++alignment_column_it, *++cell_index_column_it);
288 this->track_final_cell(*alignment_column_it, *cell_index_column_it);
309 template <std::ranges::input_range alignment_column_t,
310 std::ranges::input_range cell_index_column_t,
311 std::ranges::input_range sequence2_t>
312 void initialise_column(alignment_column_t && alignment_column,
313 cell_index_column_t && cell_index_column,
314 sequence2_t && sequence2)
320 auto first_column_it = alignment_column.begin();
321 auto cell_index_column_it = cell_index_column.begin();
322 *first_column_it = this->track_cell(this->initialise_origin_cell(), *cell_index_column_it);
328 for ([[maybe_unused]]
auto const & unused : sequence2)
332 this->track_cell(this->initialise_first_column_cell(*first_column_it), *++cell_index_column_it);
339 this->track_last_row_cell(*first_column_it, *cell_index_column_it);
360 template <std::ranges::input_range alignment_column_t,
361 std::ranges::input_range cell_index_column_t,
362 typename alphabet1_t,
363 std::ranges::input_range sequence2_t>
365 void compute_column(alignment_column_t && alignment_column,
366 cell_index_column_t && cell_index_column,
367 alphabet1_t
const & alphabet1,
368 sequence2_t && sequence2)
370 using score_type =
typename traits_type::score_type;
376 auto alignment_column_it = alignment_column.begin();
377 auto cell_index_column_it = cell_index_column.begin();
379 auto cell = *alignment_column_it;
380 score_type diagonal = cell.best_score();
381 *alignment_column_it = this->track_cell(this->initialise_first_row_cell(cell), *cell_index_column_it);
387 for (
auto const & alphabet2 : sequence2)
389 auto cell = *++alignment_column_it;
390 score_type next_diagonal = cell.best_score();
391 *alignment_column_it = this->track_cell(
392 this->compute_inner_cell(diagonal, cell, this->scoring_scheme.score(alphabet1, alphabet2)),
393 *++cell_index_column_it);
394 diagonal = next_diagonal;
401 this->track_last_row_cell(*alignment_column_it, *cell_index_column_it);
Provides seqan3::aligned_allocator.
Provides helper type traits for the configuration and execution of the alignment algorithm.
T back_inserter(T... args)
Provides seqan3::views::elements.
Provides seqan3::detail::empty_type.
The basis for seqan3::alphabet, but requires only rank interface (not char).
SeqAn specific customisations in the standard namespace.
Provides traits to inspect some information of a type, for example its name.