Provides the algorithmic components for the computation of pairwise alignments. More...
Modules | |
Alignment policies | |
Provides policies for the alignment algorithm. | |
Classes | |
interface | align_pairwise_range_input |
A helper concept to test for correct range input in seqan3::align_pairwise. More... | |
interface | align_pairwise_single_input |
A helper concept to test for correct single value input in seqan3::align_pairwise. More... | |
struct | seqan3::detail::align_result_selector< first_range_t, second_range_t, configuration_t > |
Helper metafunction to select the alignment result type based on the configuration. More... | |
class | seqan3::detail::alignment_algorithm< config_t, algorithm_policies_t > |
The alignment algorithm type to compute standard pairwise alignment using dynamic programming. More... | |
struct | seqan3::detail::alignment_algorithm_state< score_type > |
Local state for the standard alignment algorithm. More... | |
struct | seqan3::detail::alignment_configuration_traits< configuration_t > |
A traits type for the alignment algorithm that exposes static information stored within the alignment configuration object. More... | |
struct | seqan3::detail::alignment_configurator |
Configures the alignment algorithm given the sequences and the configuration object. More... | |
struct | seqan3::detail::alignment_contract< range_type, alignment_config_type > |
Provides several contracts to test when configuring the alignment algorithm. More... | |
struct | seqan3::detail::alignment_function_traits< function_t > |
A traits class to provide a uniform access to the properties of the wrapped alignment algorithm. More... | |
class | seqan3::alignment_result< alignment_result_value_t > |
Stores the alignment results and gives access to score, alignment and the front and end positionss. More... | |
struct | seqan3::detail::alignment_result_value_type< sequence1_id_t, sequence2_id_t, score_t, end_positions_t, begin_positions_t, alignment_t, score_debug_matrix_t, trace_debug_matrix_t > |
A struct that contains the actual alignment result data. More... | |
struct | seqan3::detail::alignment_result_value_type_accessor< alignment_result< result_value_t > > |
Transformation trait to access the hidden result value type of the seqan3::alignment_result class. More... | |
struct | seqan3::detail::chunked_indexed_sequence_pairs< sequence_pairs_t > |
A transformation trait to retrieve the chunked range over indexed sequence pairs. More... | |
struct | seqan3::detail::default_edit_distance_trait_type< database_t, query_t, align_config_t, is_semi_global_t, word_t > |
The default traits type for the edit distance algorithm. More... | |
class | seqan3::detail::edit_distance_score_matrix_full< word_t, score_t, is_semi_global, use_max_errors > |
The underlying data structure of seqan3::detail::edit_distance_unbanded that represents the score matrix. More... | |
class | seqan3::detail::edit_distance_trace_matrix_full< word_t, is_semi_global, use_max_errors > |
The underlying data structure of seqan3::detail::edit_distance_unbanded that represents the trace matrix. More... | |
class | seqan3::detail::edit_distance_unbanded< database_t, query_t, align_config_t, edit_traits > |
This calculates an alignment using the edit distance and without a band. More... | |
interface | indexed_sequence_pair_range |
A helper concept to check the input of the range based alignment algorithm interface. More... | |
struct | seqan3::detail::max_score_banded_updater |
A function object that compares and possibly updates the alignment optimum with the current cell. More... | |
struct | seqan3::detail::max_score_updater |
A function object that compares and possibly updates the alignment optimum with the current cell. More... | |
struct | seqan3::detail::max_score_updater_simd_global |
Function object that compares and updates the alignment optimum for the vectorised global alignment algorithm. More... | |
class | seqan3::detail::pairwise_alignment_algorithm< alignment_configuration_t, policies_t > |
The alignment algorithm type to compute standard pairwise alignment using dynamic programming. More... | |
class | seqan3::detail::pairwise_alignment_algorithm_banded< alignment_configuration_t, policies_t > |
The alignment algorithm type to compute the banded standard pairwise alignment using dynamic programming. More... | |
class | seqan3::detail::policy_affine_gap_recursion< alignment_configuration_t > |
Implements the alignment recursion function for the alignment algorithm using affine gap costs. More... | |
class | seqan3::detail::policy_affine_gap_recursion_banded< alignment_configuration_t > |
Implements the alignment recursion function for the banded alignment algorithm using affine gap costs. More... | |
class | seqan3::detail::policy_affine_gap_with_trace_recursion< alignment_configuration_t > |
Implements the alignment recursion function for the alignment algorithm using affine gap costs with trace information. More... | |
class | seqan3::detail::policy_affine_gap_with_trace_recursion_banded< alignment_configuration_t > |
Implements the alignment recursion function for the banded alignment algorithm using affine gap costs with trace information. More... | |
class | seqan3::detail::policy_alignment_matrix< traits_t, alignment_matrix_t > |
A policy that provides a common interface to acquire the correct alignment matrices. More... | |
class | seqan3::detail::policy_alignment_result_builder< alignment_configuration_t > |
Implements the alignment result builder. More... | |
class | seqan3::detail::policy_optimum_tracker< alignment_configuration_t, optimum_updater_t > |
Implements the tracker to store the global optimum for a particular alignment computation. More... | |
class | seqan3::detail::policy_optimum_tracker_simd< alignment_configuration_t, optimum_updater_t > |
Implements the tracker to store the global optimum for a particular alignment computation. More... | |
class | seqan3::detail::policy_scoring_scheme< alignment_configuration_t, scoring_scheme_t > |
Stores the configured scoring scheme used for this algorithm. More... | |
interface | sequence_pair |
A helper concept to check if a type is a sequence pair. More... | |
interface | sequence_pair_range |
A helper concept to check if a type is a range over seqan3::detail::sequence_pair. More... | |
struct | seqan3::detail::simd_global_alignment_state< simd_t > |
A state that is only used for global alignments. More... | |
Functions | |
template<typename sequence_t , typename alignment_config_t > | |
constexpr auto | seqan3::align_pairwise (sequence_t &&seq, alignment_config_t const &config) |
Computes the pairwise alignment for a pair of sequences or a range over sequence pairs. More... | |
Provides the algorithmic components for the computation of pairwise alignments.
|
constexpr |
Computes the pairwise alignment for a pair of sequences or a range over sequence pairs.
sequence_t | The type of sequence pairs (see details for more information on the type constraints). |
alignment_config_t | The type of the alignment configuration; must be a seqan3::configuration. |
[in] | seq | A tuple with two sequences or a range over such tuples. |
[in] | config | The object storing the alignment configuration. |
This function computes the pairwise alignment for the given sequences. During the setup phase the most efficient implementation is selected depending on the configurations stored in the given seqan3::configuration object. The configuration also holds settings for parallel or vectorised execution.
In cases where only a single alignment is to be computed, the two sequences can be passed as a pair. The pair can be any class template that models the seqan3::tuple_like concept. The tuple elements must model std::ranges::viewable_range and std::copy_constructible. The following example demonstrates how an alignment is computed from a std::pair of sequences.
Alternatively, you can use std::tie as shown in the example below:
In many cases one needs to compute multiple pairwise alignments. Accordingly, the align_pairwise interface allows to pass a range over sequence pairs. The alignment algorithm will be configured only once for all submitted alignments and then computes the alignments sequentially or in parallel depending on the given configuration. Since there is always a certain amount of initial setup involving runtime checks required, it is advisable to pass many sequence-pairs to this algorithm instead of repeatedly calling it with a single pair.
For each sequence pair one or more seqan3::alignment_results can be computed. The seqan3::align_pairwise function returns an seqan3::algorithm_result_generator_range which can be used to iterate over the alignments. If the vectorised
configurations are omitted the alignments are computed on-demand when iterating over the results. In case of a parallel execution all alignments are computed at once in parallel when calling begin
on the associated seqan3::algorithm_result_generator_range.
The following snippets demonstrate the single element and the range based interface.
Strong exception guarantee.
Might throw std::bad_alloc if it fails to allocate the alignment matrix or seqan3::invalid_alignment_configuration if the configuration is invalid. Throws std::runtime_error if seqan3::align_cfg::parallel has been specified without a thread_count
value.
The complexity depends on the configured algorithm. For the edit distance the following worst case over two input sequences of size can be assumed:
Computing | Runtime | Space |
---|---|---|
score | ||
back coordinate | ||
front coordinate | ||
alignment |
is the size of a machine word.
For all other algorithms that compute the standard dynamic programming algorithm the following worst case holds:
Computing | Runtime | Space |
---|---|---|
score | ||
back coordinate | ||
front coordinate | ||
alignment |
In the banded case the worst case is modified as follows:
Computing | Runtime | Space |
---|---|---|
score | ||
back coordinate | ||
front coordinate | ||
alignment |
is the size of the band.
This function is re-entrant, i.e. it is always safe to call in parallel with different inputs. It is thread-safe, i.e. it is safe to call in parallel with the same input under the condition that the input sequences do not change when being iterated over.