The alignment algorithm type to compute standard pairwise alignment using dynamic programming.
More...
|
template<typename sequence1_t , typename sequence2_t > |
constexpr void | check_valid_band_parameter (sequence1_t &&sequence1, sequence2_t &&sequence2, align_cfg::band_fixed_size const &band) |
| Checks if the band parameters are valid for the given sequences.
|
|
template<bool initialise_first_cell, typename sequence1_value_t , typename sequence2_t > |
void | compute_alignment_column (sequence1_value_t const &seq1_value, sequence2_t &&sequence2) |
| Computes a single alignment column.
|
|
template<typename sequence1_t , typename sequence2_t >
requires (!traits_t::is_banded) |
void | compute_matrix (sequence1_t &sequence1, sequence2_t &sequence2) |
| Compute the alignment by iterating over the alignment matrix in a column wise manner.
|
|
template<typename sequence1_t , typename sequence2_t >
requires (traits_t::is_banded) |
void | compute_matrix (sequence1_t &sequence1, sequence2_t &sequence2, align_cfg::band_fixed_size const &band) |
| This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
|
template<std::ranges::forward_range sequence1_t, std::ranges::forward_range sequence2_t, typename callback_t > |
constexpr void | compute_single_pair (size_t const idx, sequence1_t &&sequence1, sequence2_t &&sequence2, callback_t &callback) |
| Computes the pairwise sequence alignment for a single pair of sequences.
|
|
template<typename sequence_range_t > |
constexpr auto | convert_batch_of_sequences_to_simd_vector (sequence_range_t &sequences) |
| Converts a batch of sequences to a sequence of simd vectors.
|
|
void | dump_alignment_column () |
| Dumps the current alignment matrix in the debug score matrix and if requested debug trace matrix.
|
|
constexpr void | finalise_alignment () noexcept |
| Checks the last cell, respectively column for the alignment optimum.
|
|
constexpr void | finalise_last_cell_in_column (bool const at_last_row) noexcept |
| Finalises the last cell of the current alignment column.
|
|
template<typename sequence1_t , typename sequence2_t > |
constexpr void | initialise_debug_matrices (sequence1_t &sequence1, sequence2_t &sequence2) |
| Initialises the debug matrices for the given sequences.
|
|
template<typename sequence2_t > |
auto | initialise_first_alignment_column (sequence2_t &&sequence2) |
| Initialises the first column of the alignment matrix.
|
|
template<typename index_t , typename sequence1_t , typename sequence2_t , typename callback_t >
requires (!traits_t::is_vectorised) |
constexpr void | make_alignment_result (index_t const idx, sequence1_t &sequence1, sequence2_t &sequence2, callback_t &callback) |
| Creates a new alignment result from the current alignment optimum and for the given pair of sequences.
|
|
template<typename indexed_sequence_pair_range_t , typename callback_t >
requires traits_t |
::is_vectorised constexpr auto | make_alignment_result (indexed_sequence_pair_range_t &&index_sequence_pairs, callback_t &callback) |
| Creates a new alignment result from the current alignment optimum and for the given indexed sequence range.
|
|
template<typename config_t, typename... algorithm_policies_t>
class seqan3::detail::alignment_algorithm< config_t, algorithm_policies_t >
The alignment algorithm type to compute standard pairwise alignment using dynamic programming.
- Template Parameters
-
Configuration
The first template argument is the type of the alignment configuration which was used to configure the alignment algorithm type. They must be the same, otherwise it is possible that the output is not coherent with the expected result given the different configurations. The correct alignment is configured within the seqan3::detail::alignment_configurator and returned as a std::function object, which can be passed around and copied to create, for example multiple instances of the algorithm that can be executed in parallel.
Policies
This type uses multiple inheritance to configure a specific alignment computation, e.g. global or local alignments, using SIMD operations or scalar operations, computing the traceback or only the score etc.. These configurations are inherited using so-called alignment policies
. An alignment policy is a type that implements a specific functionality through a common interface that is used by the alignment algorithm. These policies are also the customisation points of the algorithm which will be used to implement a specific behaviour. You can read more about the policies in Alignment policies.
Since some of the policies are augmented with traits to further refine the policy execution during the configuration, it is necessary to defer the template instantiation of the policies, which are modelled as CRTP-base classes. Therefore every added policy must be wrapped in a seqan3::detail::deferred_crtp_base class wrapper. This wrapper then is expanded during the final template instantiation of the alignment algorithm type using the corresponding template function seqan3::detail::invoke_deferred_crtp_base, which instantiates the CRTP policy types with the correct alignment algorithm type.
template<typename config_t , typename... algorithm_policies_t>
template<typename alignment_algorithm_t = alignment_algorithm>
Helper function to access ((some_policy *)this)->current_alignment_column().
This works around an issue of accessing inherited members during declaration time by defering the access by using two-phase lookup.
During the declaration time this class is still an incomplete type and we are technically not allowed to access its inherited members. gcc will allow that anyway, but clang rightfully doesn't.
- See also
- http://blog.llvm.org/2009/12/dreaded-two-phase-name-lookup.html
template<typename config_t , typename... algorithm_policies_t>
template<bool initialise_first_cell, typename sequence1_value_t , typename sequence2_t >
Computes a single alignment column.
- Template Parameters
-
initialise_first_cell | An explicit bool template argument indicating whether the first cell of the current alignment column needs to be initialised. |
seq1_value_t | The value type of the first sequence. |
sequence2_t | The type of the second sequence. |
- Parameters
-
[in] | seq1_value | The current value of the first sequence for this alignment column. |
[in] | sequence2 | The current slice of the second sequence for this alignment column. |
Computes a single column within the alignment matrix. The first cell of the column is either initialised according to the initialisation policy if initialise_first_cell
is true
, otherwise it assumes a banded column within the matrix and computes the value accordingly.
template<typename config_t , typename... algorithm_policies_t>
template<typename sequence1_t , typename sequence2_t >
Initialises the debug matrices for the given sequences.
- Template Parameters
-
sequence1_t | The type of the first sequence. |
sequence2_t | The type of the second sequence. |
param[in] sequence1 The first sequence. param[in] sequence2 The second sequence.
Initialises the debug matrices if the alignment algorithm is running in debug mode. See seqan3::align_cfg::detail::debug for more information.
template<typename config_t , typename... algorithm_policies_t>
template<typename index_t , typename sequence1_t , typename sequence2_t , typename callback_t >
requires (!
traits_t::is_vectorised)
constexpr void seqan3::detail::alignment_algorithm< config_t, algorithm_policies_t >::make_alignment_result |
( |
index_t const |
idx, |
|
|
sequence1_t & |
sequence1, |
|
|
sequence2_t & |
sequence2, |
|
|
callback_t & |
callback |
|
) |
| |
|
inlineconstexprprivate |
Creates a new alignment result from the current alignment optimum and for the given pair of sequences.
- Template Parameters
-
callback_t | The type of the callback function. |
index_t | The type of the index. |
sequence1_t | The type of the first sequence. |
sequence2_t | The type of the second sequence. |
- Parameters
-
[in] | idx | The internal index used for this pair of sequences. |
[in] | sequence1 | The first range to get the alignment for if requested. |
[in] | sequence2 | The second range to get the alignment for if requested. |
[in] | callback | The callback function to be invoked with the alignment result. |
Fills the alignment result with the requested values. Depending on the selected configuration the following is extracted and/or computed:
- The alignment score.
- The end positions of the aligned range for the first and second sequence.
- The begin positions of the aligned range for the first and second sequence.
- The alignment between both sequences in the respective aligned region.
If the alignment is run in debug mode (see seqan3::align_cfg::detail::debug) the debug score and optionally trace matrix are stored in the alignment result as well.
Finally, the callback is invoked with the computed alignment result.
template<typename config_t , typename... algorithm_policies_t>
template<typename indexed_sequence_pair_range_t , typename callback_t >
requires
traits_t
::is_vectorised constexpr auto seqan3::detail::alignment_algorithm< config_t, algorithm_policies_t >::make_alignment_result |
( |
indexed_sequence_pair_range_t && |
index_sequence_pairs, |
|
|
callback_t & |
callback |
|
) |
| |
|
inlineconstexprprivate |
Creates a new alignment result from the current alignment optimum and for the given indexed sequence range.
- Template Parameters
-
callback_t | The type of the callback function. |
indexed_sequence_pair_range_t | The type of the indexed sequence pair range. |
- Parameters
-
[in] | index_sequence_pairs | The range over indexed sequence pairs. |
[in] | callback | The callback function to be invoked with the alignment result. |
This function is called for the vectorised algorithm. In this case the alignment state stores the results for the entire chunk of sequence pairs processed within this alignment computation. Accordingly, the chunk of sequence pairs is processed iteratively and the alignment results are added to the returned vector. Depending on the selected configuration the following is extracted and/or computed:
- The alignment score.
- The end positions of the aligned range for the first and second sequence.
- The begin positions of the aligned range for the first and second sequence.
- The alignment between both sequences in the respective aligned region.
If the alignment is run in debug mode (see seqan3::align_cfg::detail::debug) the debug score and optionally trace matrix are stored in the alignment result as well.
Finally, the callback is invoked with each computed alignment result iteratively.
template<typename config_t , typename... algorithm_policies_t>
Computes the pairwise sequence alignment for the given range over indexed sequence pairs.
- Template Parameters
-
- Parameters
-
[in] | indexed_sequence_pairs | A range over indexed sequence pairs to be aligned. |
[in] | callback | The callback function to be invoked with each computed alignment result. |
- Exceptions
-
Uses the standard dynamic programming algorithm to compute the pairwise sequence alignment for each sequence pair. The space and runtime complexities depend on the selected configurations (see below). For every computed alignment the given callback is invoked with the respective alignment result.
Exception
Strong exception guarantee. Might throw std::bad_alloc or seqan3::invalid_alignment_configuration.
Thread-safety
Calls to this functions in a concurrent environment are not thread safe. Instead use a copy of the alignment algorithm type.
Complexity
The following table lists the runtime and space complexities for the banded and unbanded algorithm dependent on the given seqan3::align_cfg::output_* per sequence pair. Let n
be the length of the first sequence, m
be the length of the second sequence and k
be the size of the band.
| unbanded | banded |
runtime | \( O(n*m) \) | \( O(n*k) \) |
space (score only) | \( O(m) \) | \( O(k) \) |
space (end positions) | \( O(m) \) | \( O(k) \) |
space (begin positions) | \( O(n*m) \) | \( O(n*k) \) |
space (alignment) | \( O(n*m) \) | \( O(n*k) \) |