SeqAn3 3.4.0-rc.1
The Modern C++ library for sequence analysis.
Loading...
Searching...
No Matches
seqan3::detail::policy_affine_gap_recursion< alignment_configuration_t > Class Template Reference

Implements the alignment recursion function for the alignment algorithm using affine gap costs. More...

#include <seqan3/alignment/pairwise/detail/policy_affine_gap_recursion.hpp>

+ Inheritance diagram for seqan3::detail::policy_affine_gap_recursion< alignment_configuration_t >:

Protected Types

using affine_cell_type = affine_cell_proxy< affine_score_tuple_t >
 The affine cell type returned by the functions.
 
using affine_score_tuple_t = std::tuple< score_type, score_type, score_type >
 The internal tuple storing the scores of an affine cell.
 
using original_score_type = typename traits_type::original_score_type
 The configured original score type.
 
using score_type = typename traits_type::score_type
 The configured score type.
 
using traits_type = alignment_configuration_traits< alignment_configuration_t >
 The configuration traits type.
 

Protected Member Functions

template<typename affine_cell_t >
affine_cell_type compute_inner_cell (score_type diagonal_score, affine_cell_t previous_cell, score_type const sequence_score) const noexcept
 Computes an inner cell of the alignment matrix.
 
template<typename affine_cell_t >
affine_cell_type initialise_first_column_cell (affine_cell_t previous_cell) const noexcept
 Initialises a cell of the first alignment matrix column.
 
template<typename affine_cell_t >
affine_cell_type initialise_first_row_cell (affine_cell_t previous_cell) const noexcept
 Initialises the first cell of a alignment matrix column.
 
affine_cell_type initialise_origin_cell () const noexcept
 Initialises the first cell of the alignment matrix in the top left corner of the matrix.
 
score_type lowest_viable_score () const noexcept
 Returns the lowest viable score.
 
template<typename score_t >
requires arithmetic<std::remove_cvref_t<score_t>>
constexpr auto maybe_convert_to_simd (score_t &&score) const noexcept
 Converts the given score type to a simd vector if the alignment is executed in vectorised mode.
 
Constructors, destructor and assignment
 policy_affine_gap_recursion ()=default
 Defaulted.
 
 policy_affine_gap_recursion (policy_affine_gap_recursion const &)=default
 Defaulted.
 
 policy_affine_gap_recursion (policy_affine_gap_recursion &&)=default
 Defaulted.
 
policy_affine_gap_recursionoperator= (policy_affine_gap_recursion const &)=default
 Defaulted.
 
policy_affine_gap_recursionoperator= (policy_affine_gap_recursion &&)=default
 Defaulted.
 
 ~policy_affine_gap_recursion ()=default
 Defaulted.
 
 policy_affine_gap_recursion (alignment_configuration_t const &config)
 Construction and initialisation using the alignment configuration.
 

Protected Attributes

bool first_column_is_free {}
 Initialisation state of the first column of the alignment.
 
bool first_row_is_free {}
 Initialisation state of the first row of the alignment.
 
score_type gap_extension_score {}
 The score for a gap extension.
 
score_type gap_open_score {}
 The score for a gap opening including the gap extension.
 

Detailed Description

template<typename alignment_configuration_t>
class seqan3::detail::policy_affine_gap_recursion< alignment_configuration_t >

Implements the alignment recursion function for the alignment algorithm using affine gap costs.

Template Parameters
alignment_configuration_tThe type of the alignment configuration.

Implements the functions to initialise and compute the alignment matrix using the recursion formula for affine gaps. Other policies can inherit from this policy and overload the recursion functions, e.g. to change the initialisation of the alignment matrix.

Note
For more information, please refer to the original article for the alignment with affine gap cost function: GOTOH, Osamu. An improved algorithm for matching biological sequences. Journal of molecular biology, 1982, 162. Jg., Nr. 3, S. 705-708.

Constructor & Destructor Documentation

◆ policy_affine_gap_recursion()

template<typename alignment_configuration_t >
seqan3::detail::policy_affine_gap_recursion< alignment_configuration_t >::policy_affine_gap_recursion ( alignment_configuration_t const &  config)
inlineexplicitprotected

Construction and initialisation using the alignment configuration.

Parameters
[in]configThe alignment configuration.

Initialises the gap open score and gap extension score for this policy. If no gap cost model was provided by the user the default gap costs -10 and -1 are set for the gap open score and the gap extension score respectively.

Member Function Documentation

◆ compute_inner_cell()

template<typename alignment_configuration_t >
template<typename affine_cell_t >
affine_cell_type seqan3::detail::policy_affine_gap_recursion< alignment_configuration_t >::compute_inner_cell ( score_type  diagonal_score,
affine_cell_t  previous_cell,
score_type const  sequence_score 
) const
inlineprotectednoexcept

Computes an inner cell of the alignment matrix.

Template Parameters
affine_cell_tThe type of the affine cell; must be an instance of seqan3::detail::affine_cell_proxy.
Parameters
[in]diagonal_scoreThe previous diagonal score, which corresponds to \(M[i - 1, j - 1]\).
[in]previous_cellThe predecessor cell corresponding to the values \(V[i - 1, j]\) and \(H[i, j -1]\).
[in]sequence_scoreThe score obtained from the scoring scheme for the current cell ( \( \delta\)).
Returns
The computed affine cell.

Computes the current cell according to following recursion formula:

  • \( H[i, j] = \max \{M[i, j - 1] + g_o, H[i, j - 1] + g_e\}\)
  • \( V[i, j] = \max \{M[i - 1, j] + g_o, V[i - 1, j] + g_e\}\)
  • \( M[i, j] = \max \{M[i - 1, j - 1] + \delta, H[i, j], V[i, j]\}\)

◆ initialise_first_column_cell()

template<typename alignment_configuration_t >
template<typename affine_cell_t >
affine_cell_type seqan3::detail::policy_affine_gap_recursion< alignment_configuration_t >::initialise_first_column_cell ( affine_cell_t  previous_cell) const
inlineprotectednoexcept

Initialises a cell of the first alignment matrix column.

Template Parameters
affine_cell_tThe type of the affine cell; must be an instance of seqan3::detail::affine_cell_proxy.
Parameters
[in]previous_cellThe predecessor cell on the same column \(M[i-1, 0]\).
Returns
The computed affine cell.

Initialises a cell of the first alignment matrix column. The optimal score is the same as the vertical score which is equal to \(V[i, 0] = M[i, 0] = g_o + g_e * i\). The horizontal score is initialised to \(H[i, 0] = V[i, 0] + g_o\) to prohibit extending a gap in the horizontal matrix from \(H[i, 0]\).

◆ initialise_first_row_cell()

template<typename alignment_configuration_t >
template<typename affine_cell_t >
affine_cell_type seqan3::detail::policy_affine_gap_recursion< alignment_configuration_t >::initialise_first_row_cell ( affine_cell_t  previous_cell) const
inlineprotectednoexcept

Initialises the first cell of a alignment matrix column.

Template Parameters
affine_cell_tThe type of the affine cell; must be an instance of seqan3::detail::affine_cell_proxy.
Parameters
[in]previous_cellThe predecessor cell on the same row \(M[0, j-1]\).
Returns
The computed affine cell.

Initialises the first cell of a alignment matrix column. The optimal score is the same as the horizontal score which is equal to \(H[0, j] = M[0, j] = g_o + g_e * j\). The vertical score is initialised to \(V[0,j] = H[0, j] + g_o\) to prohibit extending a gap in the vertical matrix from \(V[0, j]\).

◆ initialise_origin_cell()

template<typename alignment_configuration_t >
affine_cell_type seqan3::detail::policy_affine_gap_recursion< alignment_configuration_t >::initialise_origin_cell ( ) const
inlineprotectednoexcept

Initialises the first cell of the alignment matrix in the top left corner of the matrix.

Returns
The computed affine cell.

Initialises the cell at the origin of the alignment matrix (top left corner of the matrix). The optimal score is initialised to 0, while the value of the horizontal and vertical matrix are initialised as: \(V[0, 0] = H[0, 0] = g_o\).

◆ lowest_viable_score()

template<typename alignment_configuration_t >
score_type seqan3::detail::policy_affine_gap_recursion< alignment_configuration_t >::lowest_viable_score ( ) const
inlineprotectednoexcept

Returns the lowest viable score.

In some versions of the algorithms a value representing minus infinity is needed. Since the data type is an signed integral there is no infinity but only the lowest possible value that can be represented by the score type. In order to avoid unnecessary if conditions to protect against signed integer underflow the lowest viable score is computed. Subtracting a gap penalty from this will still result in a valid score which represents minus infinity.

◆ maybe_convert_to_simd()

template<typename alignment_configuration_t >
template<typename score_t >
requires arithmetic<std::remove_cvref_t<score_t>>
constexpr auto seqan3::detail::policy_affine_gap_recursion< alignment_configuration_t >::maybe_convert_to_simd ( score_t &&  score) const
inlineconstexprprotectednoexcept

Converts the given score type to a simd vector if the alignment is executed in vectorised mode.

Template Parameters
score_tThe score type to convert; must model seqan3::arithmetic.
Parameters
[in]scoreThe score to convert.
Returns
The score converted to the target simd vector or the unmodified value if in scalar mode.

The documentation for this class was generated from the following file:
Hide me