chain_items.hpp File Reference

#include "extract_containing_graph.hpp"
#include "../gbwt_extender.hpp"
#include "../snarl_seed_clusterer.hpp"
#include "../handle.hpp"
#include "../explainer.hpp"
#include "../utility.hpp"
#include <bdsg/hash_graph.hpp>

Classes
class	vg::algorithms::Anchor
class	vg::algorithms::TracedScore

Namespaces
	vg
	vg::algorithms
	std
	Hash functor to hash NodeSides using std::hash.

Functions
ostream &	vg::algorithms::operator<< (ostream &out, const Anchor &anchor)
	Explain an Anchor to the given stream. More...
vg::algorithms::TracedScore	std::max (const vg::algorithms::TracedScore &a, const vg::algorithms::TracedScore &b)
	Allow maxing TracedScore. More...
ostream &	vg::algorithms::operator<< (ostream &out, const TracedScore &value)
	Print operator. More...
void	vg::algorithms::sort_and_shadow (const std::vector< Anchor > &items, std::vector< size_t > &indexes)
void	vg::algorithms::sort_and_shadow (std::vector< Anchor > &items)
TracedScore	vg::algorithms::chain_items_dp (vector< TracedScore > &best_chain_score, const VectorView< Anchor > &to_chain, const SnarlDistanceIndex &distance_index, const HandleGraph &graph, int gap_open, int gap_extension, size_t max_lookback_bases, size_t min_lookback_items, size_t lookback_item_hard_cap, size_t initial_lookback_threshold, double lookback_scale_factor, double min_good_transition_score_per_base, int item_bonus, size_t max_indel_bases)
vector< size_t >	vg::algorithms::chain_items_traceback (const vector< TracedScore > &best_chain_score, const VectorView< Anchor > &to_chain, const TracedScore &best_past_ending_score_ever)
pair< int, vector< size_t > >	vg::algorithms::find_best_chain (const VectorView< Anchor > &to_chain, const SnarlDistanceIndex &distance_index, const HandleGraph &graph, int gap_open, int gap_extension, size_t max_lookback_bases, size_t min_lookback_items, size_t lookback_item_hard_cap, size_t initial_lookback_threshold, double lookback_scale_factor, double min_good_transition_score_per_base, int item_bonus, size_t max_indel_bases)
int	vg::algorithms::score_best_chain (const VectorView< Anchor > &to_chain, const SnarlDistanceIndex &distance_index, const HandleGraph &graph, int gap_open, int gap_extension)
size_t	vg::algorithms::get_graph_distance (const Anchor &from, const Anchor &to, const SnarlDistanceIndex &distance_index, const HandleGraph &graph)
	Get distance in the graph, or std::numeric_limits<size_t>::max() if unreachable. More...
size_t	vg::algorithms::get_read_distance (const Anchor &from, const Anchor &to)
	Get distance in the read, or std::numeric_limits<size_t>::max() if unreachable. More...

Detailed Description

Algorithms for chaining subalignments into larger alignments.

To use these algorithms, decide on the type (Anchor) you want to chain up.

Then, make a ChainingSpace<Anchor>, or a ChainingSpace<Anchor, Source> if your Items need to be interpreted in the context of some source object (like a seed hit needs to be interpreted in the context of its source minimizer).

Then, make a dynamic programming table: vector<TracedScore>.

Then, call chain_items_dp() to fill in the dynamic programming table and get the score of the best chain.

You can use chain_items_traceback() to get a traceback of the chain's items in order.

Helper entry points are find_best_chain() and score_best_chain() which set up the DP for you and do the traceback if appropriate.