|
vg
tools for working with variation graphs
|
#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, 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. 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... | |
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.
|
private |
| 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
| 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
| vg::BandedGlobalAligner< IntType >::~BandedGlobalAligner |
|
private |
Internal constructor that the public constructors funnel into.
| 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)
|
private |
Constructor helper function: compute which diagonals the bands cover on each node's matrix.
|
private |
Constructor helper function: compute the longest and shortest path to a sink for each node.
|
private |
Constructor helper function: compute the shortest path from a source to each node.
|
private |
Traceback through dynamic programming matrices to compute alignment.
|
private |
Use base quality adjusted scoring for alignments?
|
private |
The primary alignment.
|
private |
Vector for alternate alignments, or null if not making any.
|
private |
Dynamic programming matrices for each node.
|
private |
|
private |
Number of alignments to compute, including the optimal alignment.
|
private |
Map from node IDs to the index used in internal vectors.
|
private |
Sink nodes in the graph.
|
private |
Source nodes in the graph.
|
private |
A topological ordering of the nodes.
1.8.17