Provides policies for the alignment algorithm. More...

Collaboration diagram for Alignment policies:

Classes
class	seqan3::detail::affine_gap_init_policy< alignment_algorithm_t >
	The CRTP-policy that implements the initialisation of the dynamic programming matrix with affine gaps. More...

class	seqan3::detail::affine_gap_policy< alignment_algorithm_t, score_t, align_local_t >
	The CRTP-policy that computes a single cell in the alignment matrix. More...

class	seqan3::detail::alignment_matrix_policy< alignment_algorithm_t, score_matrix_t, trace_matrix_t >
	Manages the alignment and score matrix. More...

class	seqan3::detail::find_optimum_policy< alignment_algorithm_t >
	The CRTP-policy to determine the optimum of the dynamic programming matrix. More...

class	seqan3::detail::scoring_scheme_policy< alignment_algorithm_t, scoring_scheme_t >
	The CRTP-policy that stores the scoring scheme used for this alignment algorithm. More...

class	seqan3::detail::simd_affine_gap_policy< alignment_algorithm_t, score_t, align_local_t >
	The CRTP-policy that computes a batch of cells in the alignment matrix using simd instructions. More...

class	seqan3::detail::simd_find_optimum_policy< alignment_algorithm_t, simd_t >
	The CRTP-policy to determine the optimum of the dynamic programming matrix. More...

Detailed Description

Provides policies for the alignment algorithm.

See also: Pairwise Alignments

Introduction

The standard pairwise alignment algorithm in SeqAn is implemented in many variations. It supports the standard algorithms such as the global, local, and semi-global alignment using different kinds of scoring matrices for nucleotide or amino acid alphabets. It further allows for computing only the score or the begin and end positions or even the traceback. In addition, the algorithms can be executed in highly parallel environments using SIMD (Single Instruction Multiple Data) vectorisation and multi-threading. The combination of all of these variations leads to a huge number of different implementations of the same algorithm. Hence it is desirable to reduce the code duplication in order to increase maintenance and extension of the alignment algorithms in the future. To achieve this the alignment algorithm type is specialised with alignment policies.

Policy state

Policies can have an internal state to manage some additional variables. However, be careful with using non-stateless policies, as they can affect the internal memory layout which can result in performance regressions. The state of a policy should therefore be carefully tested with benchmarks.

Customising the alignment algorithm

An alignment policy serves as a customisation point to the alignment algorithm which has to implement a specific set of functions that are called by the actual seqan3::detail::alignment_algorithm type. These policies further separate logical units of the alignment algorithm, i.e. the initialisation, the computation, and the memory allocation of the alignment matrix.

Gap policies

Gap policies are used to initialise and to compute the cells within the alignment matrix. The gap policies are further divided into a policy initialising the matrix and computing the cells. The following table shows the functions that need to be implemented by a gap policy.

Function name	Arguments	Return value
`compute_cell`	`cell &&`, `cache &`, `score const &`	`void`

compute_cell:

This function implements the kernel that computes the score and, if enabled, the traceback direction. It gets as an input the dereferenced value of the scoring matrix (see above), the current alignment algorithm cache and the score of comparing two letter of the used alphabet using the passed scoring scheme.

Existing gap policies:

seqan3::detail::affine_gap_policy

The following table displays requirements for the corresponding gap intialisation policy:

Function name	Arguments	Return value
`init_origin_cell`	`cell &&`, `cache &`	`void`
`init_column_cell`	`cell &&`, `cache &`	`void`
`init_row_cell`	`cell &&`, `cache &`	`void`

init_origin_cell:

Implements the initialisation of the matrix origin \( (M(0,0)) \). This function gets the current cell dereferenced from the score matrix and the alignment algorithm cache.
init_column_cell:

Implements the initialisation of the cells in the first row of the matrix \( (M(i,0)) \). This function gets the current cell dereferenced from the score matrix and the alignment algorithm cache.
init_row_cell:

Implements the initialisation of the cells in the first column of the matrix \( (M(0,j)) \). This function gets the current cell dereferenced from the score matrix and the alignment algorithm cache.

Existing gap init policies:

seqan3::detail::affine_gap_init_policy

Find optimum policies

These policies are used to define the search space of the alignment optimum.

Function name	Arguments	Return value
`check_score`	`cell const`, `optimum &`	`void`
`check_score_last_row`	`cell const`, `optimum &`	`void`
`check_score_last_column`	`cell const`, `optimum &`	`void`

check_score:

Is called for every cell in the dynamic programming matrix. Might be a "NO-OP". The left operand is the score of the current cell and the right operand is the current optimum that will be updated if the current score was higher.
check_score_last_row:

Is called only for the cells in the last row of the dynamic programming matrix. Might be a NO-OP. The left operand is the score of the current cell and the right operand is the current optimum that will be updated if the current score was higher.
check_score_last_column:

Is called only for the cells in the last column of the dynamic programming matrix. The left operand is the entire last column, because the algorithm's layout is column based. This function might skip the entire range and only compare the last value (the score for the global alignment) depending on the alignment configuration.

Existing optimum policies:

seqan3::detail::find_optimum_policy

Classes