|
| 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 &) |
|
XdropAligner & | operator= (XdropAligner const &) |
|
| XdropAligner (XdropAligner &&) |
|
XdropAligner & | operator= (XdropAligner &&) |
|
|
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 |
|
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.
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.
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!