vg::BandedGlobalAligner< IntType > Class Template Reference

#include <banded_global_aligner.hpp>

Classes
class	BAMatrix
class	AltTracebackStack
class	BABuilder

Public Member Functions
	BandedGlobalAligner (Alignment &alignment, const HandleGraph &g, int64_t band_padding, bool permissive_banding=false, bool adjust_for_base_quality=false, uint64_t max_cells=std::numeric_limits< uint64_t >::max())
	BandedGlobalAligner (Alignment &alignment, const HandleGraph &g, vector< Alignment > &alt_alignments, int64_t max_multi_alns, int64_t band_padding, bool permissive_banding=false, bool adjust_for_base_quality=false, uint64_t max_cells=std::numeric_limits< uint64_t >::max())
	~BandedGlobalAligner ()
void	align (int8_t *score_mat, int8_t *nt_table, int8_t gap_open, int8_t gap_extend)

Private Types
enum	matrix_t { Match , InsertCol , InsertRow }
	Matrices used in Smith-Waterman-Gotoh alignment algorithm. More...

Private Member Functions
	BandedGlobalAligner (Alignment &alignment, const HandleGraph &g, vector< Alignment > *alt_alignments, int64_t max_multi_alns, int64_t band_padding, bool permissive_banding=false, bool adjust_for_base_quality=false, uint64_t max_cells=std::numeric_limits< uint64_t >::max())
	Internal constructor that the public constructors funnel into.
void	traceback (int8_t *score_mat, int8_t *nt_table, int8_t gap_open, int8_t gap_extend, IntType min_inf)
	Traceback through dynamic programming matrices to compute alignment.
void	path_lengths_to_sinks (vector< int64_t > &shortest_path_to_sink, vector< int64_t > &longest_path_to_sink)
	Constructor helper function: compute the longest and shortest path to a sink for each node.
void	find_banded_paths (bool permissive_banding, int64_t band_padding, vector< bool > &node_masked, vector< pair< int64_t, int64_t > > &band_ends)
	Constructor helper function: compute which diagonals the bands cover on each node's matrix.
void	shortest_seq_paths (vector< int64_t > &seq_lens_out)
	Constructor helper function: compute the shortest path from a source to each node.

Private Attributes
const HandleGraph &	graph
Alignment &	alignment
	The primary alignment.
vector< Alignment > *	alt_alignments
	Vector for alternate alignments, or null if not making any.
int64_t	max_multi_alns
	Number of alignments to compute, including the optimal alignment.
bool	adjust_for_base_quality
	Use base quality adjusted scoring for alignments?
vector< BAMatrix * >	banded_matrices
	Dynamic programming matrices for each node.
unordered_map< int64_t, int64_t >	node_id_to_idx
	Map from node IDs to the index used in internal vectors.
vector< handle_t >	topological_order
	A topological ordering of the nodes.
vector< handle_t >	source_nodes
	Source nodes in the graph.
vector< handle_t >	sink_nodes
	Sink nodes in the graph.

Detailed Description

template<class IntType>
class vg::BandedGlobalAligner< IntType >

The outward-facing interface for banded global graph alignment. It computes optimal alignment of a DNA sequence to a DAG with POA. The alignment will start at any source node in the graph and end at any sink node. It is also restricted to falling within a certain diagonal band from the start node. Any signed integer type can be used for the dynamic programming matrices, but there are no checks for overflow.

THIS IS A COMPONENT OF THE ALIGNER CLASS.

Use Aligner::align_global_banded() instead.

Member Enumeration Documentation

matrix_t

template<class IntType>

enum vg::BandedGlobalAligner::matrix_t

private

Matrices used in Smith-Waterman-Gotoh alignment algorithm.

Enumerator
Match
InsertCol
InsertRow

Constructor & Destructor Documentation

BandedGlobalAligner() [1/3]

template<class IntType>

vg::BandedGlobalAligner< IntType >::BandedGlobalAligner	(	Alignment &	alignment,
		const HandleGraph &	g,
		int64_t	band_padding,
		bool	permissive_banding = false,
		bool	adjust_for_base_quality = false,
		uint64_t	max_cells = std::numeric_limits<uint64_t>::max() )

Initializes banded alignment

Args: alignment empty alignment with a sequence (and possibly base qualities) g graph to align to; no dangling edges are permitted band_padding width to expand band by permissive_banding expand band, not necessarily symmetrically, to allow all node paths adjust_for_base_quality perform base quality adjusted alignment (see QualAdjAligner) max_cells limit maximum allocated matrix entries or throw BandMatricesTooBigException

BandedGlobalAligner() [2/3]

template<class IntType>

vg::BandedGlobalAligner< IntType >::BandedGlobalAligner	(	Alignment &	alignment,
		const HandleGraph &	g,
		vector< Alignment > &	alt_alignments,
		int64_t	max_multi_alns,
		int64_t	band_padding,
		bool	permissive_banding = false,
		bool	adjust_for_base_quality = false,
		uint64_t	max_cells = std::numeric_limits<uint64_t>::max() )

Initializes banded multi-alignment, which computes the top scoring alternate alignments in addition to the optimal alignment

Args: alignment empty alignment with a sequence (and possibly base qualities) g graph to align to; no dangling edges are permitted alt_alignments an empty vector to store alternate alignments in, the first element will be a copy of the primary alignment max_multi_alns the maximum number of alternate alignments (including the primary) band_padding width to expand band by permissive_banding expand band, not necessarily symmetrically, to allow all node paths adjust_for_base_quality perform base quality adjusted alignment (see QualAdjAligner) max_cells limit maximum allocated matrix entries or throw BandMatricesTooBigException

~BandedGlobalAligner()

template<class IntType>

vg::BandedGlobalAligner< IntType >::~BandedGlobalAligner

(

)

BandedGlobalAligner() [3/3]

template<class IntType>

vg::BandedGlobalAligner< IntType >::BandedGlobalAligner ( Alignment & alignment, const HandleGraph & g, vector< Alignment > * alt_alignments, int64_t max_multi_alns, int64_t band_padding, bool permissive_banding = false, bool adjust_for_base_quality = false, uint64_t max_cells = std::numeric_limits<uint64_t>::max() )

private

Internal constructor that the public constructors funnel into.

Member Function Documentation

align()

template<class IntType>

void vg::BandedGlobalAligner< IntType >::align	(	int8_t *	score_mat,
		int8_t *	nt_table,
		int8_t	gap_open,
		int8_t	gap_extend )

Adds path and score to the alignment object given in the constructor. If a multi-alignment vector was also supplied, fills the vector with the top scoring alignments as well.

Note: the score arguments are not <IntType> so that they can interact easily with the Aligner

Args: score_mat matrix of match/mismatch scores from Aligner (if performing base quality adjusted alignment, use QualAdjAligner's adjusted score matrix) nt_table table of indices by DNA char from Aligner gap_open gap open penalty from Algner (if performing base quality adjusted alignment, use QualAdjAligner's scaled penalty) gap_extend gap extension penalty from Algner (if performing base quality adjusted alignment, use QualAdjAligner's scaled penalty)

find_banded_paths()

template<class IntType>

void vg::BandedGlobalAligner< IntType >::find_banded_paths ( bool permissive_banding, int64_t band_padding, vector< bool > & node_masked, vector< pair< int64_t, int64_t > > & band_ends )

private

Constructor helper function: compute which diagonals the bands cover on each node's matrix.

path_lengths_to_sinks()

template<class IntType>

void vg::BandedGlobalAligner< IntType >::path_lengths_to_sinks ( vector< int64_t > & shortest_path_to_sink, vector< int64_t > & longest_path_to_sink )

private

Constructor helper function: compute the longest and shortest path to a sink for each node.

shortest_seq_paths()

template<class IntType>

void vg::BandedGlobalAligner< IntType >::shortest_seq_paths ( vector< int64_t > & seq_lens_out )

private

Constructor helper function: compute the shortest path from a source to each node.

traceback()

template<class IntType>

void vg::BandedGlobalAligner< IntType >::traceback ( int8_t * score_mat, int8_t * nt_table, int8_t gap_open, int8_t gap_extend, IntType min_inf )

private

Traceback through dynamic programming matrices to compute alignment.

Member Data Documentation

adjust_for_base_quality

template<class IntType>

bool vg::BandedGlobalAligner< IntType >::adjust_for_base_quality

private

Use base quality adjusted scoring for alignments?

alignment

template<class IntType>

Alignment& vg::BandedGlobalAligner< IntType >::alignment

private

The primary alignment.

alt_alignments

template<class IntType>

vector<Alignment>* vg::BandedGlobalAligner< IntType >::alt_alignments

private

Vector for alternate alignments, or null if not making any.

banded_matrices

template<class IntType>

vector<BAMatrix*> vg::BandedGlobalAligner< IntType >::banded_matrices

private

Dynamic programming matrices for each node.

graph

template<class IntType>

const HandleGraph& vg::BandedGlobalAligner< IntType >::graph

private

max_multi_alns

template<class IntType>

int64_t vg::BandedGlobalAligner< IntType >::max_multi_alns

private

Number of alignments to compute, including the optimal alignment.

node_id_to_idx

template<class IntType>

unordered_map<int64_t, int64_t> vg::BandedGlobalAligner< IntType >::node_id_to_idx

private

Map from node IDs to the index used in internal vectors.

sink_nodes

template<class IntType>

vector<handle_t> vg::BandedGlobalAligner< IntType >::sink_nodes

private

Sink nodes in the graph.

source_nodes

template<class IntType>

vector<handle_t> vg::BandedGlobalAligner< IntType >::source_nodes

private

Source nodes in the graph.

topological_order

template<class IntType>

vector<handle_t> vg::BandedGlobalAligner< IntType >::topological_order

private

A topological ordering of the nodes.

---

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

• src/banded_global_aligner.hpp
• src/banded_global_aligner.cpp