seqan3::detail::edit_distance_unbanded< database_t, query_t, align_config_t, edit_traits > Class Template Reference

This calculates an alignment using the edit distance and without a band. More...

#include <seqan3/alignment/pairwise/edit_distance_unbanded.hpp>

Inheritance diagram for seqan3::detail::edit_distance_unbanded< database_t, query_t, align_config_t, edit_traits >:

Classes
struct	compute_state
	The internal state needed to compute the alignment. More...
struct	compute_state_trace_matrix
	The internal state needed to compute the trace matrix. More...

Public Member Functions
template<typename callback_t >
void	operator() (size_t const idx, callback_t &&callback)
	Generic invocable interface.
Constructors, destructor and assignment
	edit_distance_unbanded ()=delete
	The class template parameter may resolve to an lvalue reference which prohibits default constructibility.
	edit_distance_unbanded (edit_distance_unbanded const &)=default
	Defaulted.
	edit_distance_unbanded (edit_distance_unbanded &&)=default
	Defaulted.
edit_distance_unbanded &	operator= (edit_distance_unbanded const &)=default
	Defaulted.
edit_distance_unbanded &	operator= (edit_distance_unbanded &&)=default
	Defaulted.
	~edit_distance_unbanded ()=default
	Defaulted.
	edit_distance_unbanded (database_t _database, query_t _query, align_config_t _config, edit_traits const &_traits)
	Constructor.
Public Member Functions inherited from seqan3::detail::edit_distance_unbanded_global_policy< derived_t, edit_traits >
std::optional< score_type >	score () const noexcept
	Return the score of the alignment. Only available if default_edit_distance_trait_type::compute_score is true.
seqan3::detail::advanceable_alignment_coordinate	end_positions () const noexcept
	Return the end position of the alignment Only available if default_edit_distance_trait_type::compute_end_positions is true.
Public Member Functions inherited from seqan3::detail::edit_distance_unbanded_score_matrix_policy< derived_t, edit_traits >
score_matrix_type const &	score_matrix () const noexcept
	Return the score matrix of the alignment. Only available if default_edit_distance_trait_type::compute_score_matrix is true.
Public Member Functions inherited from seqan3::detail::edit_distance_unbanded_trace_matrix_policy< derived_t, edit_traits >
trace_matrix_type const &	trace_matrix () const noexcept
	Return the trace matrix of the alignment.
seqan3::detail::advanceable_alignment_coordinate	begin_positions () const noexcept
	Return the begin position of the alignment. Only available if default_edit_distance_trait_type::compute_begin_positions is true.
auto	alignment () const noexcept
	Return the alignment, i.e. the actual base pair matching. Only available if default_edit_distance_trait_type::compute_sequence_alignment is true.

Private Member Functions
void	add_state ()
	Add a computation step.
void	advance_score (word_type P, word_type N, word_type mask) noexcept
	Increase or decrease the score.
void	compute ()
	Compute the alignment.
void	compute_empty_query_sequence ()
	Special case if query sequence is empty.
template<bool with_carry>
void	compute_kernel (compute_state &state, size_t const block_offset, size_t const current_block) noexcept
	A single compute step in the current column at a given position.
bool	large_patterns ()
	Pattern is larger than one machine word. Use overflow aware computation.
bool	on_hit () noexcept
	Will be called if a hit was found (e.g., score <= max_errors).
bool	small_patterns ()
	Pattern is small enough that it fits into one machine word. Use faster computation with less overhead.

Static Private Member Functions
template<bool with_carry>
static void	compute_step (compute_state &state) noexcept
	A single compute step in the current column.

Private Attributes
score_type	_score {}
	The score of the current column.
std::vector< word_type >	bit_masks {}
	The machine words which translate a letter of the query into a bit mask.
align_config_t	config
	The configuration.
database_t	database
	The horizontal/database sequence.
database_iterator	database_it {}
	The current position in the database.
database_iterator	database_it_end {}
	The end position of the database.
query_t	query
	The vertical/query sequence.
word_type	score_mask {0u}
	The mask with a bit set at the position where the score change.
std::vector< word_type >	vn {}
	The machine word which stores the negative vertical differences.
std::vector< word_type >	vp {}
	The machine word which stores the positive vertical differences.

Static Private Attributes
static constexpr word_type	hn0 = 0u
	How to pre-initialise hn.
static constexpr word_type	hp0 = is_global ? 1u : 0u
	How to pre-initialise hp.
static constexpr word_type	vn0 = 0u
	How to pre-initialise vn.
static constexpr word_type	vp0 = ~word_type{0u}
	How to pre-initialise vp.

Friends
template<typename other_derived_t , typename other_edit_traits >
class	edit_distance_unbanded_global_policy
	Allows seqan3::detail::edit_distance_unbanded_global_policy to access this class.
template<typename other_derived_t , typename other_edit_traits >
class	edit_distance_unbanded_max_errors_policy
	Allows seqan3::detail::edit_distance_unbanded_max_errors_policy to access this class.
template<typename other_derived_t , typename other_edit_traits >
class	edit_distance_unbanded_score_matrix_policy
	Allows seqan3::detail::edit_distance_unbanded_score_matrix_policy to access this class.
template<typename other_derived_t , typename other_edit_traits >
class	edit_distance_unbanded_semi_global_policy
	Allows seqan3::detail::edit_distance_unbanded_semi_global_policy to access this class.
template<typename other_derived_t , typename other_edit_traits >
class	edit_distance_unbanded_trace_matrix_policy
	Allows seqan3::detail::edit_distance_unbanded_trace_matrix_policy to access this class.

Related Symbols
(Note that these are not member symbols.)
Type deduction guides
template<typename database_t , typename query_t , typename config_t , typename traits_t >
	edit_distance_unbanded (database_t &&database, query_t &&query, config_t config, traits_t) -> edit_distance_unbanded< database_t, query_t, config_t, traits_t >
	Deduce the type from the provided arguments.

Additional Inherited Members
Public Types inherited from seqan3::detail::default_edit_distance_trait_type< database_t, query_t, align_config_t, is_semi_global_t, word_t >
using	align_config_type = std::remove_reference_t< align_config_t >
	The type of the alignment config.
using	alignment_result_type = typename alignment_traits_type::alignment_result_type
	The alignment result type generated by the algorithm.
using	alignment_traits_type = alignment_configuration_traits< align_config_type >
	The alignment algorithm traits over the alignment configuration type.
using	database_iterator = std::ranges::iterator_t< database_type >
	The type of an iterator of the database sequence.
using	database_type = std::remove_reference_t< database_t >
	The type of the database sequence.
using	query_alphabet_type = std::remove_reference_t< std::ranges::range_reference_t< query_type > >
	The alphabet type of the query sequence.
using	query_type = std::remove_reference_t< query_t >
	The type of the query sequence.
using	result_value_type = typename alignment_result_value_type_accessor< alignment_result_type >::type
	The alignment result value type.
using	score_matrix_type = edit_distance_score_matrix_full< word_type, score_type, is_semi_global, use_max_errors >
	The type of the score matrix.
using	score_type = typename alignment_traits_type::original_score_type
	The type of the score.
using	trace_matrix_type = edit_distance_trace_matrix_full< word_type, is_semi_global, use_max_errors >
	The type of the trace matrix.
using	word_type = word_t
	The type of one machine word.
Static Public Attributes inherited from seqan3::detail::default_edit_distance_trait_type< database_t, query_t, align_config_t, is_semi_global_t, word_t >
static constexpr bool	compute_begin_positions
	Whether the alignment configuration indicates to compute and/or store the begin positions.
static constexpr bool	compute_end_positions
	Whether the alignment configuration indicates to compute and/or store the end positions.
static constexpr bool	compute_matrix = compute_score_matrix || compute_trace_matrix
	Whether the alignment configuration indicates to compute and/or store the score or trace matrix.
static constexpr bool	compute_score = true
	Whether the alignment configuration indicates to compute and/or store the score.
static constexpr bool	compute_score_matrix = false
	Whether the alignment configuration indicates to compute and/or store the score matrix.
static constexpr bool	compute_sequence_alignment = alignment_traits_type::compute_sequence_alignment
	Whether the alignment configuration indicates to compute and/or store the alignment of the sequences.
static constexpr bool	compute_trace_matrix = compute_begin_positions || compute_sequence_alignment
	Whether the alignment configuration indicates to compute and/or store the trace matrix.
static constexpr bool	is_global = !is_semi_global
	Whether the alignment is a global alignment or not.
static constexpr bool	is_semi_global = is_semi_global_t::value
	Whether the alignment is a semi-global alignment or not.
static constexpr bool	use_max_errors = align_config_type::template exists<align_cfg::min_score>()
	When true the computation will use the ukkonen trick with the last active cell and bounds the error to config.max_errors.
static constexpr uint8_t	word_size = bits_of<word_type>
	The size of one machine word.
Protected Types inherited from seqan3::detail::edit_distance_unbanded_semi_global_policy< derived_t, edit_traits >
using	base_t = edit_distance_unbanded_global_policy< derived_t, edit_traits >
	The base policy of this policy.
Protected Member Functions inherited from seqan3::detail::edit_distance_unbanded_global_policy< derived_t, edit_traits >
	edit_distance_unbanded_global_policy () noexcept=default
	Defaulted.
	edit_distance_unbanded_global_policy (edit_distance_unbanded_global_policy const &) noexcept=default
	Defaulted.
	edit_distance_unbanded_global_policy (edit_distance_unbanded_global_policy &&) noexcept=default
	Defaulted.
edit_distance_unbanded_global_policy &	operator= (edit_distance_unbanded_global_policy const &) noexcept=default
	Defaulted.
edit_distance_unbanded_global_policy &	operator= (edit_distance_unbanded_global_policy &&) noexcept=default
	Defaulted.
	~edit_distance_unbanded_global_policy () noexcept=default
	Defaulted.
void	score_init () noexcept
	Initialises global policy.
bool	is_valid () const noexcept
	Returns true if the computation produced a valid alignment.
seqan3::detail::advanceable_alignment_coordinate	invalid_coordinate () const noexcept
	Returns an invalid_coordinate for this alignment.
void	update_best_score () noexcept
	Update the current best known score if the current score is better.
size_t	end_positions_first () const noexcept
	Returns the first component of the end_positions.
Protected Member Functions inherited from seqan3::detail::edit_distance_unbanded_semi_global_policy< derived_t, edit_traits >
	edit_distance_unbanded_semi_global_policy () noexcept=default
	Defaulted.
	edit_distance_unbanded_semi_global_policy (edit_distance_unbanded_semi_global_policy const &) noexcept=default
	Defaulted.
	edit_distance_unbanded_semi_global_policy (edit_distance_unbanded_semi_global_policy &&) noexcept=default
	Defaulted.
edit_distance_unbanded_semi_global_policy &	operator= (edit_distance_unbanded_semi_global_policy const &) noexcept=default
	Defaulted.
edit_distance_unbanded_semi_global_policy &	operator= (edit_distance_unbanded_semi_global_policy &&) noexcept=default
	Defaulted.
	~edit_distance_unbanded_semi_global_policy () noexcept=default
	Defaulted.
void	score_init () noexcept
	Initialises semi-global policy.
void	update_best_score () noexcept
	Update the current best known score if the current score is better.
size_t	end_positions_first () const noexcept
	Returns the first component of the end_positions.
Protected Member Functions inherited from seqan3::detail::edit_distance_unbanded_score_matrix_policy< derived_t, edit_traits >
	edit_distance_unbanded_score_matrix_policy () noexcept=default
	Defaulted.
	edit_distance_unbanded_score_matrix_policy (edit_distance_unbanded_score_matrix_policy const &) noexcept=default
	Defaulted.
	edit_distance_unbanded_score_matrix_policy (edit_distance_unbanded_score_matrix_policy &&) noexcept=default
	Defaulted.
edit_distance_unbanded_score_matrix_policy &	operator= (edit_distance_unbanded_score_matrix_policy const &) noexcept=default
	Defaulted.
edit_distance_unbanded_score_matrix_policy &	operator= (edit_distance_unbanded_score_matrix_policy &&) noexcept=default
	Defaulted.
	~edit_distance_unbanded_score_matrix_policy () noexcept=default
	Defaulted.
void	score_matrix_init ()
	Initialises score-matrix policy.
Protected Member Functions inherited from seqan3::detail::edit_distance_unbanded_trace_matrix_policy< derived_t, edit_traits >
	edit_distance_unbanded_trace_matrix_policy () noexcept=default
	Defaulted.
	edit_distance_unbanded_trace_matrix_policy (edit_distance_unbanded_trace_matrix_policy const &) noexcept=default
	Defaulted.
	edit_distance_unbanded_trace_matrix_policy (edit_distance_unbanded_trace_matrix_policy &&) noexcept=default
	Defaulted.
edit_distance_unbanded_trace_matrix_policy &	operator= (edit_distance_unbanded_trace_matrix_policy const &) noexcept=default
	Defaulted.
edit_distance_unbanded_trace_matrix_policy &	operator= (edit_distance_unbanded_trace_matrix_policy &&) noexcept=default
	Defaulted.
	~edit_distance_unbanded_trace_matrix_policy () noexcept=default
	Defaulted.
void	trace_matrix_init (size_t block_count)
	Initialises trace-matrix policy.
Protected Member Functions inherited from seqan3::detail::edit_distance_unbanded_max_errors_policy< derived_t, edit_traits >
	edit_distance_unbanded_max_errors_policy () noexcept=default
	Defaulted.
	edit_distance_unbanded_max_errors_policy (edit_distance_unbanded_max_errors_policy const &) noexcept=default
	Defaulted.
	edit_distance_unbanded_max_errors_policy (edit_distance_unbanded_max_errors_policy &&) noexcept=default
	Defaulted.
edit_distance_unbanded_max_errors_policy &	operator= (edit_distance_unbanded_max_errors_policy const &) noexcept=default
	Defaulted.
edit_distance_unbanded_max_errors_policy &	operator= (edit_distance_unbanded_max_errors_policy &&) noexcept=default
	Defaulted.
	~edit_distance_unbanded_max_errors_policy () noexcept=default
	Defaulted.
void	max_errors_init (size_t block_count) noexcept
	Initialises max_errors policy.
bool	is_last_active_cell_within_last_row () const noexcept
	Returns true if the current active cell is within the last row.
bool	prev_last_active_cell () noexcept
	Decrement the last active cell position.
void	next_last_active_cell () noexcept
	Increment the last active cell position.
bool	update_last_active_cell () noexcept
	Use the ukkonen trick and update the last active cell.
Static Protected Member Functions inherited from seqan3::detail::edit_distance_unbanded_max_errors_policy< derived_t, edit_traits >
static size_t	max_rows (word_type const score_mask, unsigned const last_block, score_type const score, score_type const max_errors) noexcept
	Computes the number of max rows in the current column.
Protected Attributes inherited from seqan3::detail::edit_distance_unbanded_global_policy< derived_t, edit_traits >
friend	derived_t
	Befriends the derived type.
score_type	_best_score {}
	The best score of the alignment in the last row (if is_semi_global = true) or the last entry in the score matrix (if is_global = true).
Protected Attributes inherited from seqan3::detail::edit_distance_unbanded_semi_global_policy< derived_t, edit_traits >
friend	derived_t
	Befriends the derived type.
database_iterator	_best_score_col {}
	In which column the best score of the alignment is located. Will only be tracked if is_semi_global is true.
Protected Attributes inherited from seqan3::detail::edit_distance_unbanded_score_matrix_policy< derived_t, edit_traits >
friend	derived_t
	Befriends the derived type.
score_matrix_type	_score_matrix {}
	The score matrix of the edit distance alignment.
Protected Attributes inherited from seqan3::detail::edit_distance_unbanded_trace_matrix_policy< derived_t, edit_traits >
friend	derived_t
	Befriends the derived type.
std::vector< word_type >	hp {}
	The machine word which stores the positive horizontal differences.
std::vector< word_type >	db {}
	The machine word which stores if trace_directions::diagonal is true.
trace_matrix_type	_trace_matrix {}
	The trace matrix of the edit distance alignment.
Protected Attributes inherited from seqan3::detail::edit_distance_unbanded_max_errors_policy< derived_t, edit_traits >
friend	derived_t
	Befriends the derived type.
score_type	max_errors {255}
	Which score value is considered as a hit?
size_t	last_block {0u}
	The block containing the last active cell.
word_type	last_score_mask {}
	A mask with a bit set on the position of the last row.

Detailed Description

template<std::ranges::viewable_range database_t, std::ranges::viewable_range query_t, typename align_config_t, typename edit_traits>
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.

Template Parameters

database_t	The type of the database sequence.
query_t	The type of the query sequence.
align_config_t	The configuration type; must be of type seqan3::configuration.

Constructor & Destructor Documentation

edit_distance_unbanded() [1/2]

template<std::ranges::viewable_range database_t, std::ranges::viewable_range query_t, typename align_config_t , typename edit_traits >

seqan3::detail::edit_distance_unbanded< database_t, query_t, align_config_t, edit_traits >::edit_distance_unbanded ( )

delete

The class template parameter may resolve to an lvalue reference which prohibits default constructibility.

Defaulted.

edit_distance_unbanded() [2/2]

template<std::ranges::viewable_range database_t, std::ranges::viewable_range query_t, typename align_config_t , typename edit_traits >

seqan3::detail::edit_distance_unbanded< database_t, query_t, align_config_t, edit_traits >::edit_distance_unbanded ( database_t  _database, query_t  _query, align_config_t  _config, edit_traits const &  _traits  )

inline

Constructor.

Parameters

[in]	_database	The horizontal/database sequence.
[in]	_query	The vertical/query sequence.
[in]	_config	The configuration.
[in]	_traits	The traits object. Only the type information will be used.

Member Function Documentation

operator()()

template<std::ranges::viewable_range database_t, std::ranges::viewable_range query_t, typename align_config_t , typename edit_traits >

template<typename callback_t >

void seqan3::detail::edit_distance_unbanded< database_t, query_t, align_config_t, edit_traits >::operator() ( size_t const  idx, callback_t &&  callback  )

inline

Generic invocable interface.

Parameters

[in]	idx	The index of the currently processed sequence pair.
[in]	callback	The callback function to be invoked with the alignment result.

Member Data Documentation

bit_masks

template<std::ranges::viewable_range database_t, std::ranges::viewable_range query_t, typename align_config_t , typename edit_traits >

std::vector<word_type> seqan3::detail::edit_distance_unbanded< database_t, query_t, align_config_t, edit_traits >::bit_masks {}

private

The machine words which translate a letter of the query into a bit mask.

Each bit position which is true (= 1) corresponds to a match of a letter in the query at this position.

score_mask

template<std::ranges::viewable_range database_t, std::ranges::viewable_range query_t, typename align_config_t , typename edit_traits >

word_type seqan3::detail::edit_distance_unbanded< database_t, query_t, align_config_t, edit_traits >::score_mask {0u}

private

The mask with a bit set at the position where the score change.

If use_max_errors is true this corresponds to the last active cell.

vn

template<std::ranges::viewable_range database_t, std::ranges::viewable_range query_t, typename align_config_t , typename edit_traits >

std::vector<word_type> seqan3::detail::edit_distance_unbanded< database_t, query_t, align_config_t, edit_traits >::vn {}

private

The machine word which stores the negative vertical differences.

vp

template<std::ranges::viewable_range database_t, std::ranges::viewable_range query_t, typename align_config_t , typename edit_traits >

std::vector<word_type> seqan3::detail::edit_distance_unbanded< database_t, query_t, align_config_t, edit_traits >::vp {}

private

The machine word which stores the positive vertical differences.

---

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

• edit_distance_unbanded.hpp