77 template <
typename range_type,
78 typename alignment_config_type>
88 using first_seq_t = std::tuple_element_t<0, std::ranges::range_value_t<unref_range_type>>;
90 using second_seq_t = std::tuple_element_t<1, std::ranges::range_value_t<unref_range_type>>;
98 std::tuple_size_v<std::ranges::range_value_t<unref_range_type>> == 2;
104 if constexpr (alignment_config_type::template exists<align_cfg::scoring_scheme>())
108 decltype(get<align_cfg::scoring_scheme>(std::declval<alignment_config_type>()).scheme)>;
110 std::ranges::range_value_t<first_seq_t>,
111 std::ranges::range_value_t<second_seq_t>>);
122 const bool is_global = alignment_config_type::template exists<seqan3::align_cfg::method_global>();
123 const bool is_local = alignment_config_type::template exists<seqan3::align_cfg::method_local>();
125 return (is_global || is_local);
140 template <
typename traits_t>
146 traits_t::compute_sequence_alignment);
167 template <
typename traits_t>
172 using score_t =
typename traits_t::score_type;
189 template <
typename traits_t>
194 using score_t =
typename traits_t::score_type;
204 template <
typename traits_t,
typename ...args_t>
212 template <
typename config_t>
264 template <align_pairwise_range_input sequences_t,
typename config_t>
266 requires is_type_specialisation_of_v<config_t, configuration>
271 using config_with_output_t = decltype(config_with_output);
277 using first_seq_t = std::tuple_element_t<0, std::ranges::range_value_t<sequences_t>>;
278 using second_seq_t = std::tuple_element_t<1, std::ranges::range_value_t<sequences_t>>;
285 using indexed_sequence_pair_chunk_t = std::ranges::range_value_t<indexed_sequence_pair_range_t>;
290 config_with_output_t>::type;
292 using callback_on_result_t =
std::function<void(alignment_result_t)>;
294 using function_wrapper_t =
std::function<void(indexed_sequence_pair_chunk_t, callback_on_result_t)>;
305 static_assert(alignment_contract_t::expects_alignment_configuration(),
306 "Alignment configuration error: "
307 "The alignment can only be configured with alignment configurations.");
309 static_assert(alignment_contract_t::expects_tuple_like_value_type(),
310 "Alignment configuration error: "
311 "The value type of the sequence ranges must model the seqan3::tuple_like and must contain "
312 "exactly 2 elements.");
314 static_assert(alignment_contract_t::expects_valid_scoring_scheme(),
315 "Alignment configuration error: "
316 "Either the scoring scheme was not configured or the given scoring scheme cannot be invoked with "
317 "the value types of the passed sequences.");
325 auto const & gap_cost = config_with_result_type.get_or(edit_gap_cost);
326 auto const & scoring_scheme = get<align_cfg::scoring_scheme>(cfg).scheme;
328 if constexpr (config_t::template exists<seqan3::align_cfg::method_global>())
331 auto method_global_cfg = get<seqan3::align_cfg::method_global>(config_with_result_type);
333 if (gap_cost.open_score == 0 &&
334 !(method_global_cfg.free_end_gaps_sequence2_leading ||
335 method_global_cfg.free_end_gaps_sequence2_trailing) &&
336 (method_global_cfg.free_end_gaps_sequence1_leading ==
337 method_global_cfg.free_end_gaps_sequence1_trailing))
344 if ((scoring_scheme.score(
'A'_dna15,
'A'_dna15) == 0) &&
345 (scoring_scheme.score(
'A'_dna15,
'C'_dna15)) == -1)
347 return std::pair{configure_edit_distance<function_wrapper_t>(config_with_result_type),
348 config_with_result_type};
359 if (config_t::template exists<align_cfg::min_score>())
361 "specific edit distance computation."};
363 return std::pair{configure_scoring_scheme<function_wrapper_t>(config_with_result_type),
364 config_with_result_type};
377 template <
typename config_t>
382 if constexpr (traits_t::has_output_configuration)
398 template <
typename function_wrapper_t,
typename config_t>
407 if constexpr (traits_t::is_banded)
417 auto configure_edit_traits = [&] (
auto is_semi_global)
419 struct edit_traits_type
421 using is_semi_global_type [[maybe_unused]] =
std::remove_cvref_t<decltype(is_semi_global)>;
425 return function_wrapper_t{std::move(algorithm)};
429 auto has_free_ends_trailing = [&] (
auto first) constexpr
431 if constexpr (!decltype(first)::value)
437 if (method_global_cfg.free_end_gaps_sequence1_trailing)
445 if (method_global_cfg.free_end_gaps_sequence1_leading)
467 template <
typename function_wrapper_t,
typename config_t>
484 template <
typename function_wrapper_t,
typename ...policies_t,
typename config_t>
494 if constexpr (traits_t::is_local ||
495 traits_t::is_debug ||
496 traits_t::compute_sequence_alignment ||
497 (traits_t::is_banded && traits_t::compute_begin_positions) ||
498 (traits_t::is_vectorised && traits_t::compute_end_positions))
505 return alignment_algorithm<config_t, matrix_policy_t, gap_policy_t, find_optimum_t, gap_init_policy_t, policies_t...>{cfg};
517 using optimum_tracker_policy_t =
518 lazy_conditional_t<traits_t::is_vectorised,
542 using score_t =
typename traits_t::score_type;
543 using scoring_scheme_t =
typename traits_t::scoring_scheme_type;
544 constexpr
bool is_aminoacid_scheme = is_type_specialisation_of_v<scoring_scheme_t, aminoacid_scoring_scheme>;
546 using simple_simd_scheme_t = lazy_conditional_t<traits_t::is_vectorised,
549 typename traits_t::scoring_scheme_alphabet_type,
552 using matrix_simd_scheme_t = lazy_conditional_t<traits_t::is_vectorised,
555 typename traits_t::scoring_scheme_alphabet_type,
561 matrix_simd_scheme_t,
562 simple_simd_scheme_t>,
587 optimum_tracker_policy_t,
588 result_builder_policy_t,
589 scoring_scheme_policy_t,
590 alignment_matrix_policy_t>;
591 return algorithm_t{cfg};
597 template <
typename function_wrapper_t,
typename config_t>
600 using traits_t = alignment_configuration_traits<config_t>;
602 using scoring_scheme_t =
typename traits_t::scoring_scheme_type;
603 constexpr
bool is_aminoacid_scheme = is_type_specialisation_of_v<scoring_scheme_t, aminoacid_scoring_scheme>;
608 using simple_simd_scheme_t = lazy_conditional_t<traits_t::is_vectorised,
609 lazy<simd_match_mismatch_scoring_scheme,
610 typename traits_t::score_type,
611 typename traits_t::scoring_scheme_alphabet_type,
614 using matrix_simd_scheme_t = lazy_conditional_t<traits_t::is_vectorised,
615 lazy<simd_matrix_scoring_scheme,
616 typename traits_t::score_type,
617 typename traits_t::scoring_scheme_alphabet_type,
625 using scoring_scheme_policy_t = deferred_crtp_base<scoring_scheme_policy, alignment_scoring_scheme_t>;
626 return make_algorithm<function_wrapper_t, scoring_scheme_policy_t>(cfg);
Provides seqan3::detail::affine_gap_init_policy.
Provides seqan3::detail::affine_gap_policy.
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::detail::alignment_matrix_policy.
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.
Configuration element capturing the configured seqan3::alignment_result for the alignment algorithm.
Definition: align_config_result_type.hpp:47
A configuration element for the affine gap cost scheme.
Definition: align_config_gap_cost_affine.hpp:74
Sets the global alignment method.
Definition: align_config_method.hpp:107
Sets the local alignment method.
Definition: align_config_method.hpp:43
Configures the alignment result to output the alignment.
Definition: align_config_output.hpp:171
Configures the alignment result to output the begin positions.
Definition: align_config_output.hpp:131
Configures the alignment result to output the end position.
Definition: align_config_output.hpp:87
Configures the alignment result to output the score.
Definition: align_config_output.hpp:43
Configures the alignment result to output the id of the first sequence.
Definition: align_config_output.hpp:211
Configures the alignment result to output the id of the second sequence.
Definition: align_config_output.hpp:251
Stores the alignment results and gives access to score, alignment and the front and end positionss.
Definition: alignment_result.hpp:155
The alignment algorithm type to compute standard pairwise alignment using dynamic programming.
Definition: alignment_algorithm.hpp:78
A banded alignment score matrix storing only a single banded column for the computation.
Definition: alignment_score_matrix_one_column_banded.hpp:43
An alignment score matrix storing only a single column for the computation.
Definition: alignment_score_matrix_one_column.hpp:45
An alignment traceback matrix storing the entire banded traceback matrix.
Definition: alignment_trace_matrix_full_banded.hpp:56
An alignment traceback matrix storing the entire traceback matrix.
Definition: alignment_trace_matrix_full.hpp:53
An alignment matrix that combines a score matrix with a trace matrix into a common interface.
Definition: combined_score_and_trace_matrix.hpp:50
This algorithm unifies different edit distance implementations and uses the appropriate one depending...
Definition: edit_distance_algorithm.hpp:40
The alignment algorithm type to compute the banded standard pairwise alignment using dynamic programm...
Definition: pairwise_alignment_algorithm_banded.hpp:35
The alignment algorithm type to compute standard pairwise alignment using dynamic programming.
Definition: pairwise_alignment_algorithm.hpp:49
Implements the alignment recursion function for the banded alignment algorithm using affine gap costs...
Definition: policy_affine_gap_recursion_banded.hpp:26
Implements the alignment recursion function for the alignment algorithm using affine gap costs.
Definition: policy_affine_gap_recursion.hpp:45
Implements the alignment recursion function for the banded alignment algorithm using affine gap costs...
Definition: policy_affine_gap_with_trace_recursion_banded.hpp:28
Implements the alignment recursion function for the alignment algorithm using affine gap costs with t...
Definition: policy_affine_gap_with_trace_recursion.hpp:27
A policy that provides a common interface to acquire the correct alignment matrices.
Definition: policy_alignment_matrix.hpp:49
Implements the alignment result builder.
Definition: policy_alignment_result_builder.hpp:41
Stores the configured scoring scheme used for this algorithm.
Definition: policy_scoring_scheme.hpp:35
Score matrix for the pairwise alignment using only a single column.
Definition: score_matrix_single_column.hpp:56
A vectorised scoring scheme handling matches and mismatches only.
Definition: simd_match_mismatch_scoring_scheme.hpp:72
A vectorised scoring scheme to handle scoring matrices using gather strategy.
Definition: simd_matrix_scoring_scheme.hpp:61
Trace matrix for the pairwise alignment using the full trace matrix.
Definition: trace_matrix_full.hpp:55
Thrown if the configuration of the alignment algorithm is invalid.
Definition: exception.hpp:34
A data structure for managing and computing the score of two nucleotides.
Definition: nucleotide_scoring_scheme.hpp:38
Provides seqan3::detail::combined_score_and_trace_matrix.
Provides seqan3::detail::deferred_crtp_base.
Provides seqan3::detail::edit_distance_algorithm.
Provides seqan3::detail::find_optimum_policy.
A concept that requires that type be able to score two letters.
Whether a type behaves like a tuple.
Provides lazy template instantiation traits.
The internal SeqAn3 namespace.
Definition: aligned_sequence_concept.hpp:29
decltype(views::type_reduce(std::declval< t >())) type_reduce_t
Deduces the return value of seqan3::views::type_reduce.
Definition: type_reduce.hpp:172
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::scoring_scheme_policy.
Provides seqan3::simd::simd_type.
Provides seqan3::detail::simd_affine_gap_policy.
Provides seqan3::detail::simd_find_optimum_policy.
Provides seqan3::detail::simd_match_mismatch_scoring_scheme.
Provides seqan3::detail::simd_matrix_scoring_scheme.
Helper metafunction to select the alignment result type based on the configuration.
Definition: align_result_selector.hpp:49
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 requires_trace_information
Flag indicating whether the trace matrix needs to be computed.
Definition: type_traits.hpp:190
Transformation trait that chooses the correct find optimum policy.
Definition: alignment_configurator.hpp:191
typename traits_t::score_type score_t
The score type for the alignment computation.
Definition: alignment_configurator.hpp:194
Transformation trait that chooses the correct gap policy.
Definition: alignment_configurator.hpp:169
typename traits_t::score_type score_t
The score type for the alignment computation.
Definition: alignment_configurator.hpp:172
Selects the gap recursion policy.
Definition: alignment_configurator.hpp:214
static constexpr bool with_trace
A flag indicating if trace is required.
Definition: alignment_configurator.hpp:219
std::conditional_t< with_trace, policy_affine_gap_with_trace_recursion_banded< config_t >, policy_affine_gap_recursion_banded< config_t > > banded_gap_recursion_policy_type
The banded gap recursion policy.
Definition: alignment_configurator.hpp:229
Transformation trait that chooses the correct matrix policy.
Definition: alignment_configurator.hpp:142
static constexpr bool only_coordinates
Indicates whether only the coordinate is required to compute the alignment.
Definition: alignment_configurator.hpp:145
Configures the alignment algorithm given the sequences and the configuration object.
Definition: alignment_configurator.hpp:134
static constexpr auto maybe_default_output(config_t const &config) noexcept
Adds maybe the default output arguments if the user did not provide any.
Definition: alignment_configurator.hpp:378
static constexpr auto configure(config_t const &cfg)
Configures the algorithm.
Definition: alignment_configurator.hpp:268
lazy_conditional_t< traits_t::is_banded, lazy< pairwise_alignment_algorithm_banded, args_t... >, lazy< pairwise_alignment_algorithm, args_t... > > select_alignment_algorithm_t
Selects either the banded or the unbanded alignment algorithm based on the given traits type.
Definition: alignment_configurator.hpp:207
static constexpr function_wrapper_t make_algorithm(config_t const &cfg)
Constructs the actual alignment algorithm wrapped in the passed std::function object.
Definition: alignment_configurator.hpp:485
static constexpr function_wrapper_t configure_edit_distance(config_t const &cfg)
Configures the edit distance algorithm.
Definition: alignment_configurator.hpp:399
static constexpr function_wrapper_t configure_scoring_scheme(config_t const &cfg)
Configures the scoring scheme to use for the alignment computation.
Provides several contracts to test when configuring the alignment algorithm.
Definition: alignment_configurator.hpp:80
constexpr static bool expects_tuple_like_value_type()
Tests whether the value type of range_type is a tuple with exactly 2 members.
Definition: alignment_configurator.hpp:95
std::tuple_element_t< 0, std::ranges::range_value_t< unref_range_type > > first_seq_t
The type of the first sequence.
Definition: alignment_configurator.hpp:88
constexpr static bool expects_valid_scoring_scheme()
Tests whether the scoring scheme is set and can be invoked with the sequences passed.
Definition: alignment_configurator.hpp:102
std::tuple_element_t< 1, std::ranges::range_value_t< unref_range_type > > second_seq_t
The type of the second sequence.
Definition: alignment_configurator.hpp:90
constexpr static bool expects_alignment_configuration()
Expects alignment configurations.
Definition: alignment_configurator.hpp:120
decltype(views::zip(std::declval< sequence_pairs_t >(), std::views::iota(0))|views::chunk(1)) type
The transformed type that models seqan3::detail::indexed_sequence_pair_range.
Definition: type_traits.hpp:68
An invocable wrapper that defers the instantiation of a crtp_base class.
Definition: deferred_crtp_base.hpp:43
An empty type whose only purpose is to hold an uninstantiated template plus its arguments.
Definition: lazy_conditional.hpp:36
A function object that compares and possibly updates the alignment optimum with the current cell.
Definition: policy_optimum_tracker.hpp:112
A function object that compares and possibly updates the alignment optimum with the current cell.
Definition: policy_optimum_tracker.hpp:39
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.