vg
tools for working with variation graphs
Classes | Public Member Functions | Private Member Functions | Private Attributes | List of all members
vg::XdropAligner Class Reference

#include <xdrop_aligner.hpp>

Classes

struct  graph_pos_s
 
struct  OrderedGraph
 

Public Member Functions

 XdropAligner (int8_t _match, int8_t _mismatch, int8_t _gap_open, int8_t _gap_extension, int32_t _full_length_bonus, uint32_t _max_gap_length)
 
 XdropAligner (const int8_t *_score_matrix, int8_t _gap_open, int8_t _gap_extension, int32_t _full_length_bonus, uint32_t _max_gap_length)
 
 XdropAligner ()
 
 ~XdropAligner (void)
 
void align (Alignment &alignment, const HandleGraph &graph, const vector< handle_t > &topological_order, const vector< MaximalExactMatch > &mems, bool reverse_complemented) const
 
void align (Alignment &alignment, const HandleGraph &graph, const vector< MaximalExactMatch > &mems, bool reverse_complemented) const
 Implementation of align() that automatically wraps up a topologically-ordered Protobuf graph as an OrderedGraph. More...
 
void align_pinned (Alignment &alignment, const HandleGraph &g, bool pin_left) const
 
void align_pinned (Alignment &alignment, const HandleGraph &g, const vector< handle_t > &topological_order, bool pin_left) const
 
 XdropAligner (XdropAligner const &)
 
XdropAligneroperator= (XdropAligner const &)
 
 XdropAligner (XdropAligner &&)
 
XdropAligneroperator= (XdropAligner &&)
 

Private Member Functions

graph_pos_s calculate_seed_position (const OrderedGraph &graph, const vector< MaximalExactMatch > &mems, size_t query_length, bool direction) const
 
graph_pos_s calculate_max_position (const OrderedGraph &graph, const graph_pos_s &seed_pos, size_t max_node_index, bool direction, dz_s *dz, const vector< const dz_forefront_s * > &forefronts) const
 
graph_pos_s scan_seed_position (const OrderedGraph &graph, const string &query_seq, bool direction, dz_s *dz, vector< const dz_forefront_s * > &forefronts) const
 
size_t push_edit (Mapping *mapping, uint8_t op, const char *alt, size_t len) const
 
size_t extend (const OrderedGraph &graph, const dz_query_s *packed_query, const vector< graph_pos_s > &seed_positions, bool right_to_left, dz_s *dz, vector< const dz_forefront_s * > &forefronts) const
 
void calculate_and_save_alignment (Alignment &alignment, const OrderedGraph &graph, const vector< graph_pos_s > &head_positions, size_t tail_node_index, bool left_to_right, dz_s *dz, const vector< const dz_forefront_s * > &forefronts) const
 
void align_downward (Alignment &alignment, const OrderedGraph &graph, const vector< graph_pos_s > &head_positions, bool left_to_right, dz_s *dz, vector< const dz_forefront_s * > &forefronts) const
 

Private Attributes

int8_t * score_matrix = nullptr
 4 x 4 matrix of match/mismatch scores More...
 
uint16_t gap_open = 0
 Amount paid in addition to gap_extend on first base of a gap. More...
 
uint16_t gap_extend = 0
 Amount paid on each base of a gap. More...
 
int32_t full_length_bonus = 0
 
uint32_t max_gap_length = 0
 

Detailed Description

Align to a graph using the xdrop algorithm, as implemented in dozeu.

The underlying Dozeu library is fundamentally based around semi-global alignment: extending an alignment from a known matching position (what in other parts of vg we call "pinned" alignment).

To simulate non-pinned alignment, we align in two passes in different directions. One from a guess of a pinning position, to get a more accurate "head" pinning position for the other end, and once back from where the previous pass ended up, to get an overall hopefully-optimal alignment.

If the input graph is not reverse-complemented, direction = false (reverse, right to left) on the first pass, and direction = true (forward, left to right) on the second. If it is reverse complemented, we flip them.

This won't actually work in theory to get the optimal local alignment in all cases, but it works well in practice.

Constructor & Destructor Documentation

◆ XdropAligner() [1/5]

XdropAligner::XdropAligner ( int8_t  _match,
int8_t  _mismatch,
int8_t  _gap_open,
int8_t  _gap_extension,
int32_t  _full_length_bonus,
uint32_t  _max_gap_length 
)

◆ XdropAligner() [2/5]

XdropAligner::XdropAligner ( const int8_t *  _score_matrix,
int8_t  _gap_open,
int8_t  _gap_extension,
int32_t  _full_length_bonus,
uint32_t  _max_gap_length 
)

◆ XdropAligner() [3/5]

XdropAligner::XdropAligner ( )

◆ ~XdropAligner()

XdropAligner::~XdropAligner ( void  )

◆ XdropAligner() [4/5]

XdropAligner::XdropAligner ( XdropAligner const &  rhs)

◆ XdropAligner() [5/5]

XdropAligner::XdropAligner ( XdropAligner &&  rhs)

Member Function Documentation

◆ align() [1/2]

void XdropAligner::align ( Alignment alignment,
const HandleGraph graph,
const vector< handle_t > &  topological_order,
const vector< MaximalExactMatch > &  mems,
bool  reverse_complemented 
) const

align query: forward-backward banded alignment

Compute an alignment of the given Alignment's sequence against the given topologically sorted graph, using (one of) the given MEMs to seed the alignment.

reverse_complemented is true if the topologically sorted graph we have was reverse-complemented when extracted from a larger containing graph, and false if it is in the same orientation as it exists in the larger containing graph. The MEMs and the Alignment are interpreted as being against the forward strand of the passed subgraph no matter the value of this setting.

reverse_complemented true means we will compute the alignment forward in the topologically-sorted order of the given graph (anchoring to the first node if no MEMs are provided) and false if we want to compute the alignment backward in the topological order (anchoring to the last node).

All the graph edges must go from earlier to later nodes, and from_start and to_end must alsways be false.

First the head (the most upstream) seed in MEMs is selected and extended downward to detect the downstream breakpoint. Next the alignment path is generated by second upward extension from the downstream breakpoint.

The MEM list may be empty. If MEMs are provided, uses only the begin, end, and nodes fields of the MaximalExactMatch objects. It uses the first occurrence of the last MEM if reverse_complemented is true, and the last occurrence of the first MEM otherwise.

◆ align() [2/2]

void XdropAligner::align ( Alignment alignment,
const HandleGraph graph,
const vector< MaximalExactMatch > &  mems,
bool  reverse_complemented 
) const

Implementation of align() that automatically wraps up a topologically-ordered Protobuf graph as an OrderedGraph.

◆ align_downward()

void XdropAligner::align_downward ( Alignment alignment,
const OrderedGraph graph,
const vector< graph_pos_s > &  head_positions,
bool  left_to_right,
dz_s *  dz,
vector< const dz_forefront_s * > &  forefronts 
) const
private

After doing the upward pass and finding head_pos to anchor from, do the downward alignment pass and traceback. If left_to_right is set, goes left to right and traces back the other way. If it is unset, goes right to left and traces back the other way.

◆ align_pinned() [1/2]

void XdropAligner::align_pinned ( Alignment alignment,
const HandleGraph g,
bool  pin_left 
) const

Compute a pinned alignment, where the start (pin_left=true) or end (pin_left=false) end of the Alignment sequence is pinned to the start of the first (pin_left=true) or end of the last (pin_left=false) node in the graph's topological order.

Does not account for multiple sources/sinks in the topological order; whichever comes first/last ends up being used for the pin.

◆ align_pinned() [2/2]

void XdropAligner::align_pinned ( Alignment alignment,
const HandleGraph g,
const vector< handle_t > &  topological_order,
bool  pin_left 
) const

Version of align_pinned that allows you to pass your own topological order. The topological order MUST be left to right, no matter whether you are pinning left or right. If alignment needs to proceed backward, it will be reversed internally.

◆ calculate_and_save_alignment()

void XdropAligner::calculate_and_save_alignment ( Alignment alignment,
const OrderedGraph graph,
const vector< graph_pos_s > &  head_positions,
size_t  tail_node_index,
bool  left_to_right,
dz_s *  dz,
const vector< const dz_forefront_s * > &  forefronts 
) const
private

After all the alignment work has been done, do the traceback and save into the given Alignment object.

If left_to_right is true, the nodes were filled left to right, and the internal traceback will come out in left to right order, so we can emit it as is. If it is false, the nodes were filled right to left, and the internal traceback comes out in right to left order, so we need to flip it.

◆ calculate_max_position()

XdropAligner::graph_pos_s XdropAligner::calculate_max_position ( const OrderedGraph graph,
const graph_pos_s seed_pos,
size_t  max_node_index,
bool  direction,
dz_s *  dz,
const vector< const dz_forefront_s * > &  forefronts 
) const
private

Given the index of the node at which the winning score occurs, find the position in the node and read sequence at which the winning match is found.

◆ calculate_seed_position()

XdropAligner::graph_pos_s XdropAligner::calculate_seed_position ( const OrderedGraph graph,
const vector< MaximalExactMatch > &  mems,
size_t  query_length,
bool  direction 
) const
private

Given the subgraph we are aligning to, the MEM hist against it, the length of the query, and the direction we are aligning the query in (true = forward), select a single anchoring match between the graph and the query to align out from.

This replaces scan_seed_position for the case where we have MEMs.

◆ extend()

size_t XdropAligner::extend ( const OrderedGraph graph,
const dz_query_s *  packed_query,
const vector< graph_pos_s > &  seed_positions,
bool  right_to_left,
dz_s *  dz,
vector< const dz_forefront_s * > &  forefronts 
) const
private

Do alignment. Takes the graph, the sorted packed edges in ascending order for a forward pass or descending order for a reverse pass, the packed query sequence, the index of the seed node in the graph, the offset (TODO: in the read?) of the seed position, and the direction to traverse the graph topological order.

Note that we take our direction as right_to_left, whole many other functions take it as left_to_right.

If a MEM seed is provided, this is run in two passes. The first is left to right (right_to_left = false) if align did not have reverse_complement set and the second is right to left (right_to_left = true).

If we have no MEM seed, we only run one pass (the second one).

Returns the index in the topological order of the node with the highest scoring alignment.

Note that if no non-empty local alignment is found, it may not be safe to call dz_calc_max_qpos on the associated forefront!

◆ operator=() [1/2]

XdropAligner & XdropAligner::operator= ( XdropAligner &&  rhs)

◆ operator=() [2/2]

XdropAligner & XdropAligner::operator= ( XdropAligner const &  rhs)

◆ push_edit()

size_t XdropAligner::push_edit ( Mapping mapping,
uint8_t  op,
const char *  alt,
size_t  len 
) const
private

Append an edit at the end of the current mapping array. Returns the length passed in.

◆ scan_seed_position()

XdropAligner::graph_pos_s XdropAligner::scan_seed_position ( const OrderedGraph graph,
const string &  query_seq,
bool  direction,
dz_s *  dz,
vector< const dz_forefront_s * > &  forefronts 
) const
private

If no seeds are provided as alignment input, we need to compute our own starting anchor position. This function does that. Takes the topologically-sorted graph, the query sequence, and the direction. If direction is false, finds a seed hit on the first node of the graph. If it is true, finds a hit on the last node.

This replaces calculate_seed_position for the case where we have no MEMs.

Member Data Documentation

◆ full_length_bonus

int32_t vg::XdropAligner::full_length_bonus = 0
private

◆ gap_extend

uint16_t vg::XdropAligner::gap_extend = 0
private

Amount paid on each base of a gap.

◆ gap_open

uint16_t vg::XdropAligner::gap_open = 0
private

Amount paid in addition to gap_extend on first base of a gap.

◆ max_gap_length

uint32_t vg::XdropAligner::max_gap_length = 0
private

◆ score_matrix

int8_t* vg::XdropAligner::score_matrix = nullptr
private

4 x 4 matrix of match/mismatch scores


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