vg
tools for working with variation graphs
Classes | Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
vg::BandedGlobalAligner< IntType > Class Template Reference

#include <banded_global_aligner.hpp>

Classes

class  AltTracebackStack
 
class  BABuilder
 
class  BAMatrix
 

Public Member Functions

 BandedGlobalAligner (Alignment &alignment, const HandleGraph &g, int64_t band_padding, bool permissive_banding=false, bool adjust_for_base_quality=false)
 
 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)
 
 ~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)
 Internal constructor that the public constructors funnel into. More...
 
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. More...
 
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. More...
 
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. More...
 
void shortest_seq_paths (vector< int64_t > &seq_lens_out)
 Constructor helper function: compute the shortest path from a source to each node. More...
 

Private Attributes

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

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 
)

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)

◆ 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 
)

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)

◆ ~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 
)
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:
Generated by   doxygen 1.8.17