60 namespace seqan3::detail
72 template <
typename range_type,
73 typename alignment_config_type>
74 struct alignment_contract
83 using first_seq_t = std::tuple_element_t<0, std::ranges::range_value_t<unref_range_type>>;
85 using second_seq_t = std::tuple_element_t<1, std::ranges::range_value_t<unref_range_type>>;
90 constexpr
static bool expects_tuple_like_value_type()
93 std::tuple_size_v<std::ranges::range_value_t<unref_range_type>> == 2;
97 constexpr
static bool expects_valid_scoring_scheme()
99 if constexpr (alignment_config_type::template exists<align_cfg::scoring_scheme>())
103 decltype(get<align_cfg::scoring_scheme>(std::declval<alignment_config_type>()).scheme)>;
105 std::ranges::range_value_t<first_seq_t>,
106 std::ranges::range_value_t<second_seq_t>>);
115 constexpr
static bool expects_alignment_configuration()
117 const bool is_global = alignment_config_type::template exists<seqan3::align_cfg::method_global>();
118 const bool is_local = alignment_config_type::template exists<seqan3::align_cfg::method_local>();
120 return (is_global || is_local);
128 struct alignment_configurator
135 template <
typename traits_t>
136 struct select_matrix_policy
140 static constexpr
bool only_coordinates = !(traits_t::compute_begin_positions ||
141 traits_t::compute_sequence_alignment);
145 alignment_score_matrix_one_column_banded<typename traits_t::score_type>,
146 alignment_score_matrix_one_column<typename traits_t::score_type>>;
149 alignment_trace_matrix_full_banded<
typename traits_t::trace_type,
151 alignment_trace_matrix_full<
typename traits_t::trace_type,
156 using type = deferred_crtp_base<alignment_matrix_policy, score_matrix_t, trace_matrix_t>;
162 template <
typename traits_t>
163 struct select_gap_policy
167 using score_t =
typename traits_t::score_type;
174 deferred_crtp_base<simd_affine_gap_policy, score_t, is_local_t>,
175 deferred_crtp_base<affine_gap_policy, score_t, is_local_t>>;
184 template <
typename traits_t>
185 struct select_find_optimum_policy
189 using score_t =
typename traits_t::score_type;
194 deferred_crtp_base<simd_find_optimum_policy, score_t>,
195 deferred_crtp_base<find_optimum_policy>>;
199 template <
typename traits_t,
typename ...args_t>
200 using select_alignment_algorithm_t = lazy_conditional_t<traits_t::is_banded,
201 lazy<pairwise_alignment_algorithm_banded, args_t...>,
202 lazy<pairwise_alignment_algorithm, args_t...>>;
231 template <align_pairwise_range_input sequences_t,
typename config_t>
233 requires is_type_specialisation_of_v<config_t, configuration>
235 static constexpr
auto configure(config_t
const & cfg)
237 auto config_with_output = maybe_default_output(cfg);
238 using config_with_output_t = decltype(config_with_output);
244 using first_seq_t = std::tuple_element_t<0, std::ranges::range_value_t<sequences_t>>;
245 using second_seq_t = std::tuple_element_t<1, std::ranges::range_value_t<sequences_t>>;
247 using wrapped_first_t = type_reduce_view<first_seq_t &>;
248 using wrapped_second_t = type_reduce_view<second_seq_t &>;
251 using indexed_sequence_pair_range_t =
typename chunked_indexed_sequence_pairs<sequences_t>::type;
252 using indexed_sequence_pair_chunk_t = std::ranges::range_value_t<indexed_sequence_pair_range_t>;
255 using alignment_result_value_t =
typename align_result_selector<std::remove_reference_t<wrapped_first_t>,
257 config_with_output_t>::type;
258 using alignment_result_t = alignment_result<alignment_result_value_t>;
259 using callback_on_result_t =
std::function<void(alignment_result_t)>;
261 using function_wrapper_t =
std::function<void(indexed_sequence_pair_chunk_t, callback_on_result_t)>;
264 auto config_with_result_type = config_with_output | align_cfg::detail::result_type<alignment_result_t>{};
270 using alignment_contract_t = alignment_contract<sequences_t, config_with_output_t>;
272 static_assert(alignment_contract_t::expects_alignment_configuration(),
273 "Alignment configuration error: "
274 "The alignment can only be configured with alignment configurations.");
276 static_assert(alignment_contract_t::expects_tuple_like_value_type(),
277 "Alignment configuration error: "
278 "The value type of the sequence ranges must model the seqan3::tuple_like and must contain "
279 "exactly 2 elements.");
281 static_assert(alignment_contract_t::expects_valid_scoring_scheme(),
282 "Alignment configuration error: "
283 "Either the scoring scheme was not configured or the given scoring scheme cannot be invoked with "
284 "the value types of the passed sequences.");
291 align_cfg::gap_cost_affine edit_gap_cost{};
292 auto const & gap_cost = config_with_result_type.get_or(edit_gap_cost);
293 auto const & scoring_scheme = get<align_cfg::scoring_scheme>(cfg).scheme;
295 if constexpr (config_t::template exists<seqan3::align_cfg::method_global>())
298 auto method_global_cfg = get<seqan3::align_cfg::method_global>(config_with_result_type);
300 if (gap_cost.open_score == 0 &&
301 !(method_global_cfg.free_end_gaps_sequence2_leading ||
302 method_global_cfg.free_end_gaps_sequence2_trailing) &&
303 (method_global_cfg.free_end_gaps_sequence1_leading ==
304 method_global_cfg.free_end_gaps_sequence1_trailing))
309 nucleotide_scoring_scheme>)
311 if ((scoring_scheme.score(
'A'_dna15,
'A'_dna15) == 0) &&
312 (scoring_scheme.score(
'A'_dna15,
'C'_dna15)) == -1)
314 return std::pair{configure_edit_distance<function_wrapper_t>(config_with_result_type),
315 config_with_result_type};
326 if (config_t::template exists<align_cfg::min_score>())
327 throw invalid_alignment_configuration{
"The align_cfg::min_score configuration is only allowed for the "
328 "specific edit distance computation."};
330 return std::pair{configure_scoring_scheme<function_wrapper_t>(config_with_result_type),
331 config_with_result_type};
344 template <
typename config_t>
345 static constexpr
auto maybe_default_output(config_t
const & config) noexcept
347 using traits_t = alignment_configuration_traits<config_t>;
349 if constexpr (traits_t::has_output_configuration)
352 return config | align_cfg::output_score{} |
353 align_cfg::output_begin_position{} |
354 align_cfg::output_end_position{} |
355 align_cfg::output_alignment{} |
356 align_cfg::output_sequence1_id{} |
357 align_cfg::output_sequence2_id{};
365 template <
typename function_wrapper_t,
typename config_t>
366 static constexpr function_wrapper_t configure_edit_distance(config_t
const & cfg)
368 using traits_t = alignment_configuration_traits<config_t>;
374 if constexpr (traits_t::is_banded)
375 throw invalid_alignment_configuration{
"Banded alignments are yet not supported."};
382 auto method_global_cfg = cfg.get_or(align_cfg::method_global{});
384 auto configure_edit_traits = [&] (
auto is_semi_global)
386 struct edit_traits_type
388 using is_semi_global_type [[maybe_unused]] =
std::remove_cvref_t<decltype(is_semi_global)>;
391 edit_distance_algorithm<std::remove_cvref_t<config_t>, edit_traits_type> algorithm{cfg};
392 return function_wrapper_t{
std::move(algorithm)};
396 auto has_free_ends_trailing = [&] (
auto first) constexpr
398 if constexpr (!decltype(first)::value)
404 if (method_global_cfg.free_end_gaps_sequence1_trailing)
412 if (method_global_cfg.free_end_gaps_sequence1_leading)
434 template <
typename function_wrapper_t,
typename config_t>
435 static constexpr function_wrapper_t configure_scoring_scheme(config_t
const & cfg);
451 template <
typename function_wrapper_t,
typename ...policies_t,
typename config_t>
452 static constexpr function_wrapper_t make_algorithm(config_t
const & cfg)
454 using traits_t = alignment_configuration_traits<config_t>;
461 if constexpr (traits_t::is_local ||
462 traits_t::is_debug ||
463 (traits_t::compute_begin_positions || traits_t::compute_sequence_alignment) ||
464 (traits_t::is_banded && traits_t::compute_end_positions) ||
465 (traits_t::is_vectorised && traits_t::is_banded) ||
466 (traits_t::is_vectorised && traits_t::compute_end_positions))
468 using matrix_policy_t =
typename select_matrix_policy<traits_t>::type;
469 using gap_policy_t =
typename select_gap_policy<traits_t>::type;
470 using find_optimum_t =
typename select_find_optimum_policy<traits_t>::type;
471 using gap_init_policy_t = deferred_crtp_base<affine_gap_init_policy>;
473 return alignment_algorithm<config_t, matrix_policy_t, gap_policy_t, find_optimum_t, gap_init_policy_t, policies_t...>{cfg};
477 using optimum_tracker_policy_t =
478 lazy_conditional_t<traits_t::is_vectorised,
479 lazy<policy_optimum_tracker_simd, config_t, max_score_updater_simd_global>,
480 lazy<policy_optimum_tracker, config_t, max_score_updater>>;
483 policy_affine_gap_recursion_banded<config_t>,
484 policy_affine_gap_recursion<config_t>>;
485 using result_builder_policy_t = policy_alignment_result_builder<config_t>;
491 using score_t =
typename traits_t::score_type;
492 using alignment_scoring_scheme_t =
493 lazy_conditional_t<traits_t::is_vectorised,
494 lazy<simd_match_mismatch_scoring_scheme,
496 typename traits_t::scoring_scheme_alphabet_type,
498 typename traits_t::scoring_scheme_type>;
500 using scoring_scheme_policy_t = policy_scoring_scheme<config_t, alignment_scoring_scheme_t>;
501 using alignment_matrix_policy_t = policy_alignment_matrix<traits_t, score_matrix_single_column<score_t>>;
503 using algorithm_t = select_alignment_algorithm_t<traits_t,
506 optimum_tracker_policy_t,
507 result_builder_policy_t,
508 scoring_scheme_policy_t,
509 alignment_matrix_policy_t>;
510 return algorithm_t{cfg};
516 template <
typename function_wrapper_t,
typename config_t>
517 constexpr function_wrapper_t alignment_configurator::configure_scoring_scheme(config_t
const & cfg)
519 using traits_t = alignment_configuration_traits<config_t>;
521 using alignment_scoring_scheme_t =
522 lazy_conditional_t<traits_t::is_vectorised,
523 lazy<simd_match_mismatch_scoring_scheme,
524 typename traits_t::score_type,
525 typename traits_t::scoring_scheme_alphabet_type,
529 typename traits_t::scoring_scheme_type>;
531 using scoring_scheme_policy_t = deferred_crtp_base<scoring_scheme_policy, alignment_scoring_scheme_t>;
532 return make_algorithm<function_wrapper_t, scoring_scheme_policy_t>(cfg);