43#include <seqan3/alignment/pairwise/policy/affine_gap_init_policy.hpp>
44#include <seqan3/alignment/pairwise/policy/affine_gap_policy.hpp>
45#include <seqan3/alignment/pairwise/policy/alignment_matrix_policy.hpp>
46#include <seqan3/alignment/pairwise/policy/find_optimum_policy.hpp>
47#include <seqan3/alignment/pairwise/policy/scoring_scheme_policy.hpp>
48#include <seqan3/alignment/pairwise/policy/simd_affine_gap_policy.hpp>
49#include <seqan3/alignment/pairwise/policy/simd_find_optimum_policy.hpp>
56#include <seqan3/utility/simd/simd.hpp>
62namespace seqan3::detail
74template <
typename range_type,
typename alignment_config_type>
75struct alignment_contract
84 using first_seq_t = std::tuple_element_t<0, std::ranges::range_value_t<unref_range_type>>;
86 using second_seq_t = std::tuple_element_t<1, std::ranges::range_value_t<unref_range_type>>;
91 static constexpr bool expects_tuple_like_value_type()
94 && std::tuple_size_v<std::ranges::range_value_t<unref_range_type>> == 2;
98 static constexpr bool expects_valid_scoring_scheme()
100 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 static constexpr bool expects_alignment_configuration()
117 bool const is_global = alignment_config_type::template exists<seqan3::align_cfg::method_global>();
118 bool const is_local = alignment_config_type::template exists<seqan3::align_cfg::method_local>();
120 return (is_global || is_local);
128struct alignment_configurator
134 template <
typename traits_t>
135 struct select_matrix_policy
139 static constexpr bool only_coordinates =
140 !(traits_t::compute_begin_positions || traits_t::compute_sequence_alignment);
143 using score_matrix_t =
145 alignment_score_matrix_one_column_banded<typename traits_t::score_type>,
146 alignment_score_matrix_one_column<typename traits_t::score_type>>;
148 using trace_matrix_t =
150 alignment_trace_matrix_full_banded<typename traits_t::trace_type, only_coordinates>,
151 alignment_trace_matrix_full<typename traits_t::trace_type, only_coordinates>>;
155 using type = deferred_crtp_base<alignment_matrix_policy, score_matrix_t, trace_matrix_t>;
161 template <
typename traits_t>
162 struct select_gap_policy
166 using score_t =
typename traits_t::score_type;
173 deferred_crtp_base<simd_affine_gap_policy, score_t, is_local_t>,
174 deferred_crtp_base<affine_gap_policy, score_t, is_local_t>>;
183 template <
typename traits_t>
184 struct select_find_optimum_policy
188 using score_t =
typename traits_t::score_type;
193 deferred_crtp_base<simd_find_optimum_policy, score_t>,
194 deferred_crtp_base<find_optimum_policy>>;
198 template <
typename traits_t,
typename... args_t>
199 using select_alignment_algorithm_t = lazy_conditional_t<traits_t::is_banded,
200 lazy<pairwise_alignment_algorithm_banded, args_t...>,
201 lazy<pairwise_alignment_algorithm, args_t...>>;
206 template <
typename config_t>
207 struct select_gap_recursion_policy
211 using traits_type = alignment_configuration_traits<config_t>;
213 static constexpr bool with_trace = traits_type::requires_trace_information;
217 policy_affine_gap_with_trace_recursion<config_t>,
218 policy_affine_gap_recursion<config_t>>;
220 using banded_gap_recursion_policy_type =
222 policy_affine_gap_with_trace_recursion_banded<config_t>,
223 policy_affine_gap_recursion_banded<config_t>>;
258 template <align_pairwise_range_input sequences_t,
typename config_t>
259 requires is_type_specialisation_of_v<config_t, configuration>
260 static constexpr auto configure(config_t
const & cfg)
262 auto config_with_output = maybe_default_output(cfg);
263 using config_with_output_t =
decltype(config_with_output);
269 using first_seq_t = std::tuple_element_t<0, std::ranges::range_value_t<sequences_t>>;
270 using second_seq_t = std::tuple_element_t<1, std::ranges::range_value_t<sequences_t>>;
272 using wrapped_first_t = type_reduce_t<first_seq_t &>;
273 using wrapped_second_t = type_reduce_t<second_seq_t &>;
276 using indexed_sequence_pair_range_t =
typename chunked_indexed_sequence_pairs<sequences_t>::type;
277 using indexed_sequence_pair_chunk_t = std::ranges::range_value_t<indexed_sequence_pair_range_t>;
280 using alignment_result_value_t =
typename align_result_selector<std::remove_reference_t<wrapped_first_t>,
282 config_with_output_t>::type;
283 using alignment_result_t = alignment_result<alignment_result_value_t>;
284 using callback_on_result_t =
std::function<void(alignment_result_t)>;
286 using function_wrapper_t =
std::function<void(indexed_sequence_pair_chunk_t, callback_on_result_t)>;
289 auto config_with_result_type = config_with_output | align_cfg::detail::result_type<alignment_result_t>{};
295 using alignment_contract_t = alignment_contract<sequences_t, config_with_output_t>;
297 static_assert(alignment_contract_t::expects_alignment_configuration(),
298 "Alignment configuration error: "
299 "The alignment can only be configured with alignment configurations.");
301 static_assert(alignment_contract_t::expects_tuple_like_value_type(),
302 "Alignment configuration error: "
303 "The value type of the sequence ranges must model the seqan3::tuple_like and must contain "
304 "exactly 2 elements.");
306 static_assert(alignment_contract_t::expects_valid_scoring_scheme(),
307 "Alignment configuration error: "
308 "Either the scoring scheme was not configured or the given scoring scheme cannot be invoked with "
309 "the value types of the passed sequences.");
316 align_cfg::gap_cost_affine edit_gap_cost{};
317 auto const & gap_cost = config_with_result_type.get_or(edit_gap_cost);
318 auto const & scoring_scheme = get<align_cfg::scoring_scheme>(cfg).scheme;
320 if constexpr (config_t::template exists<seqan3::align_cfg::method_global>())
323 auto method_global_cfg = get<seqan3::align_cfg::method_global>(config_with_result_type);
325 if (gap_cost.open_score == 0 &&
326 !(method_global_cfg.free_end_gaps_sequence2_leading
327 || method_global_cfg.free_end_gaps_sequence2_trailing)
329 (method_global_cfg.free_end_gaps_sequence1_leading
331 .free_end_gaps_sequence1_trailing))
336 nucleotide_scoring_scheme>)
338 if ((scoring_scheme.score(
'A'_dna15,
'A'_dna15) == 0)
339 && (scoring_scheme.score(
'A'_dna15,
'C'_dna15)) == -1)
341 return std::pair{configure_edit_distance<function_wrapper_t>(config_with_result_type),
342 config_with_result_type};
353 if (config_t::template exists<align_cfg::min_score>())
354 throw invalid_alignment_configuration{
"The align_cfg::min_score configuration is only allowed for the "
355 "specific edit distance computation."};
357 return std::pair{configure_scoring_scheme<function_wrapper_t>(config_with_result_type),
358 config_with_result_type};
371 template <
typename config_t>
372 static constexpr auto maybe_default_output(config_t
const & config)
noexcept
374 using traits_t = alignment_configuration_traits<config_t>;
376 if constexpr (traits_t::has_output_configuration)
379 return config | align_cfg::output_score{} | align_cfg::output_begin_position{}
380 | align_cfg::output_end_position{} | align_cfg::output_alignment{} | align_cfg::output_sequence1_id{}
381 | align_cfg::output_sequence2_id{};
389 template <
typename function_wrapper_t,
typename config_t>
390 static constexpr function_wrapper_t configure_edit_distance(config_t
const & cfg)
392 using traits_t = alignment_configuration_traits<config_t>;
398 if constexpr (traits_t::is_banded)
399 throw invalid_alignment_configuration{
"Banded alignments are yet not supported."};
406 auto method_global_cfg = cfg.get_or(align_cfg::method_global{});
408 auto configure_edit_traits = [&](
auto is_semi_global)
410 struct edit_traits_type
412 using is_semi_global_type [[maybe_unused]] =
std::remove_cvref_t<
decltype(is_semi_global)>;
415 edit_distance_algorithm<std::remove_cvref_t<config_t>, edit_traits_type> algorithm{cfg};
416 return function_wrapper_t{std::move(algorithm)};
420 auto has_free_ends_trailing = [&](
auto first)
constexpr
422 if constexpr (!
decltype(first)::value)
428 if (method_global_cfg.free_end_gaps_sequence1_trailing)
436 if (method_global_cfg.free_end_gaps_sequence1_leading)
458 template <
typename function_wrapper_t,
typename config_t>
459 static constexpr function_wrapper_t configure_scoring_scheme(config_t
const & cfg);
475 template <
typename function_wrapper_t,
typename... policies_t,
typename config_t>
476 static constexpr function_wrapper_t make_algorithm(config_t
const & cfg)
478 using traits_t = alignment_configuration_traits<config_t>;
485 if constexpr (traits_t::is_local ||
486 traits_t::is_debug ||
487 traits_t::compute_sequence_alignment ||
488 (traits_t::is_banded && traits_t::compute_begin_positions)
490 (traits_t::is_vectorised && traits_t::compute_end_positions))
492 using matrix_policy_t =
typename select_matrix_policy<traits_t>::type;
493 using gap_policy_t =
typename select_gap_policy<traits_t>::type;
494 using find_optimum_t =
typename select_find_optimum_policy<traits_t>::type;
495 using gap_init_policy_t = deferred_crtp_base<affine_gap_init_policy>;
497 return alignment_algorithm<config_t,
510 using scalar_optimum_updater_t =
513 using optimum_tracker_policy_t =
514 lazy_conditional_t<traits_t::is_vectorised,
515 lazy<policy_optimum_tracker_simd, config_t, max_score_updater_simd_global>,
516 lazy<policy_optimum_tracker, config_t, scalar_optimum_updater_t>>;
522 using gap_cost_policy_t =
typename select_gap_recursion_policy<config_t>::type;
528 using result_builder_policy_t = policy_alignment_result_builder<config_t>;
534 using alignment_method_t = std::
535 conditional_t<traits_t::is_global, seqan3::align_cfg::method_global, seqan3::align_cfg::method_local>;
537 using score_t =
typename traits_t::score_type;
538 using scoring_scheme_t =
typename traits_t::scoring_scheme_type;
539 constexpr bool is_aminoacid_scheme =
540 is_type_specialisation_of_v<scoring_scheme_t, aminoacid_scoring_scheme>;
542 using simple_simd_scheme_t = lazy_conditional_t<traits_t::is_vectorised,
543 lazy<simd_match_mismatch_scoring_scheme,
545 typename traits_t::scoring_scheme_alphabet_type,
548 using matrix_simd_scheme_t = lazy_conditional_t<traits_t::is_vectorised,
549 lazy<simd_matrix_scoring_scheme,
551 typename traits_t::scoring_scheme_alphabet_type,
555 using alignment_scoring_scheme_t =
560 using scoring_scheme_policy_t = policy_scoring_scheme<config_t, alignment_scoring_scheme_t>;
566 using score_matrix_t = score_matrix_single_column<score_t>;
567 using trace_matrix_t = trace_matrix_full<trace_directions>;
569 using alignment_matrix_t =
571 combined_score_and_trace_matrix<score_matrix_t, trace_matrix_t>,
573 using alignment_matrix_policy_t = policy_alignment_matrix<traits_t, alignment_matrix_t>;
579 using algorithm_t = select_alignment_algorithm_t<traits_t,
582 optimum_tracker_policy_t,
583 result_builder_policy_t,
584 scoring_scheme_policy_t,
585 alignment_matrix_policy_t>;
586 return algorithm_t{cfg};
592template <
typename function_wrapper_t,
typename config_t>
593constexpr function_wrapper_t alignment_configurator::configure_scoring_scheme(config_t
const & cfg)
595 using traits_t = alignment_configuration_traits<config_t>;
597 using scoring_scheme_t =
typename traits_t::scoring_scheme_type;
598 constexpr bool is_aminoacid_scheme = is_type_specialisation_of_v<scoring_scheme_t, aminoacid_scoring_scheme>;
599 using alignment_type_t =
typename std::
600 conditional_t<traits_t::is_global, seqan3::align_cfg::method_global, seqan3::align_cfg::method_local>;
602 using simple_simd_scheme_t = lazy_conditional_t<traits_t::is_vectorised,
603 lazy<simd_match_mismatch_scoring_scheme,
604 typename traits_t::score_type,
605 typename traits_t::scoring_scheme_alphabet_type,
608 using matrix_simd_scheme_t = lazy_conditional_t<traits_t::is_vectorised,
609 lazy<simd_matrix_scoring_scheme,
610 typename traits_t::score_type,
611 typename traits_t::scoring_scheme_alphabet_type,
615 using alignment_scoring_scheme_t =
620 using scoring_scheme_policy_t = deferred_crtp_base<scoring_scheme_policy, alignment_scoring_scheme_t>;
621 return make_algorithm<function_wrapper_t, scoring_scheme_policy_t>(cfg);
Provides configuration for alignment output.
Provides seqan3::align_cfg::detail::result_type.
Provides seqan3::detail::align_result_selector.
Provides concepts needed internally for the alignment algorithms.
Provides helper type traits for the configuration and execution of the alignment algorithm.
Provides seqan3::detail::alignment_algorithm.
Provides seqan3::alignment_result.
Provides seqan3::detail::alignment_score_matrix_one_column.
Provides seqan3::detail::alignment_score_matrix_one_column_banded.
Provides seqan3::detail::alignment_trace_matrix_full.
Provides seqan3::detail::alignment_trace_matrix_full_banded.
Provides seqan3::aminoacid_scoring_scheme.
Provides seqan3::detail::combined_score_and_trace_matrix.
Provides seqan3::detail::deferred_crtp_base.
Provides seqan3::detail::edit_distance_algorithm.
A concept that requires that type be able to score two letters.
Whether a type behaves like a tuple.
Provides lazy template instantiation traits.
Provides seqan3::nucleotide_scoring_scheme.
Provides seqan3::detail::pairwise_alignment_algorithm.
Provides seqan3::detail::pairwise_alignment_algorithm.
Provides seqan3::detail::policy_affine_gap_recursion.
Provides seqan3::detail::policy_affine_gap_recursion_banded.
Provides seqan3::detail::policy_affine_gap_with_trace_recursion.
Provides seqan3::detail::policy_affine_gap_with_trace_recursion_banded.
Provides seqan3::detail::policy_alignment_matrix.
Provides seqan3::detail::policy_alignment_result_builder.
Provides seqan3::detail::policy_optimum_tracker.
Provides seqan3::detail::policy_optimum_tracker_simd.
Provides seqan3::detail::policy_scoring_scheme.
Provides seqan3::detail::score_matrix_single_column.
Provides seqan3::detail::simd_match_mismatch_scoring_scheme.
Provides seqan3::detail::simd_matrix_scoring_scheme.
Provides type traits for working with templates.
Provides seqan3::detail::trace_matrix_full.
Provides seqan3::views::type_reduce.
Provides seqan3::tuple_like.
Provides seqan3::views::zip.