chain_items.hpp File Reference

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

Classes
class	vg::algorithms::Anchor
class	vg::algorithms::TracedScore
struct	vg::algorithms::transition_info
	Represents a possible transition between anchors. More...
struct	vg::algorithms::ChainScoringScheme
struct	vg::algorithms::ChainWithRec
struct	vg::algorithms::ChainsResult

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

Typedefs
using	vg::algorithms::path_flags_t = uint64_t
using	vg::algorithms::transition_iteratee = std::function<void(const transition_info& transition)>
using	vg::algorithms::transition_iterator = std::function<void(const VectorView<Anchor>& to_chain, const SnarlDistanceIndex& distance_index, const HandleGraph& graph, size_t max_indel_bases, const transition_iteratee& callback)>

Functions
ostream &	vg::algorithms::operator<< (ostream &out, const Anchor &anchor)
	Explain an Anchor to the given stream.
vg::algorithms::TracedScore	std::max (const vg::algorithms::TracedScore &a, const vg::algorithms::TracedScore &b)
	Allow maxing TracedScore.
ostream &	vg::algorithms::operator<< (ostream &out, const TracedScore &value)
	Print operator.
void	vg::algorithms::sort_anchor_indexes (const std::vector< Anchor > &items, std::vector< size_t > &indexes)
transition_iterator	vg::algorithms::zip_tree_transition_iterator (const std::vector< SnarlDistanceIndexClusterer::Seed > &seeds, const ZipCodeTree &zip_code_tree, size_t max_graph_lookback_bases, size_t max_read_lookback_bases)
std::vector< transition_info >	vg::algorithms::generate_zip_tree_transitions (const std::vector< SnarlDistanceIndexClusterer::Seed > &seeds, const ZipCodeTree &zip_code_tree, size_t max_graph_lookback_bases, size_t max_read_lookback_bases, size_t max_indel_bases, const VectorView< Anchor > &to_chain, const std::unordered_map< size_t, size_t > &seed_to_starting, const std::unordered_map< size_t, size_t > &seed_to_ending)
void	vg::algorithms::add_transition_if_legal (vector< transition_info > &transitions, const VectorView< Anchor > &to_chain, size_t max_read_lookback_bases, size_t max_indel_bases, size_t from_anchor, size_t to_anchor, size_t graph_distance)
void	vg::algorithms::chain_items_dp (vector< TracedScore > &chain_scores, const VectorView< Anchor > &to_chain, const SnarlDistanceIndex &distance_index, const HandleGraph &graph, const transition_iterator &for_each_transition, const ChainScoringScheme &scheme, size_t max_indel_bases, bool show_work)
vector< pair< vector< size_t >, int > >	vg::algorithms::chain_items_traceback (const vector< TracedScore > &chain_scores, const VectorView< Anchor > &to_chain, const ChainScoringScheme &scheme, size_t max_tracebacks)
ChainsResult	vg::algorithms::find_best_chains (const VectorView< Anchor > &to_chain, const SnarlDistanceIndex &distance_index, const HandleGraph &graph, const transition_iterator &for_each_transition, const ChainScoringScheme &scheme, size_t max_chains, size_t max_indel_bases, bool show_work)
pair< int, vector< size_t > >	vg::algorithms::find_best_chain (const VectorView< Anchor > &to_chain, const SnarlDistanceIndex &distance_index, const HandleGraph &graph, const transition_iterator &for_each_transition, const ChainScoringScheme &scheme, size_t max_indel_bases)
int	vg::algorithms::score_chain_gap (size_t distance_difference, size_t base_seed_length)
int	vg::algorithms::check_recombination (const Anchor &from, const Anchor &to)
size_t	vg::algorithms::get_graph_distance (const Anchor &from, const Anchor &to, const SnarlDistanceIndex &distance_index, const HandleGraph &graph, size_t distance_limit=std::numeric_limits< size_t >::max())
	Get distance in the graph, or std::numeric_limits<size_t>::max() if unreachable or beyond the limit.
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.
ostream &	vg::algorithms::operator<< (ostream &out, const BenchmarkResult &result)
ostream &	vg::algorithms::operator<< (ostream &out, const BenchmarkResult &result)

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 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.