gatb.core-API-0.0.0: TraversalTemplate< Node, Edge, Graph

Class that traverse nodes of a Graph. More...

#include <Traversal.hpp>

Inheritance diagram for TraversalTemplate< Node, Edge, Graph >:

Public Member Functions
virtual std::string	getName () const =0

int	traverse (Node &node, Direction dir, Path_t< Node > &resulting_sequence)

int	traverse (Node &startingNode, Node &endingNode, Direction dir, Path_t< Node > &resulting_sequence)

unsigned int	getMaxDepth () const

unsigned int	getMaxBreadth () const

const std::vector< std::pair< int, int > > &	getBubbles () const

Public Member Functions inherited from SmartPointer
void	use ()

void	forget ()

Public Member Functions inherited from ISmartPointer
virtual	~ISmartPointer ()

Static Public Member Functions
static TraversalTemplate< Node, Edge, Graph > *	create (tools::misc::TraversalKind type, const Graph &graph, TerminatorTemplate< Node, Edge, Graph > &terminator, int max_len=defaultMaxLen, int max_depth=defaultMaxDepth, int max_breadth=defaultMaxBreadth)

static TraversalTemplate< Node, Edge, Graph > *	create (const std::string &type, const Graph &graph, TerminatorTemplate< Node, Edge, Graph > &terminator, int max_len=defaultMaxLen, int max_depth=defaultMaxDepth, int max_breadth=defaultMaxBreadth)

static float	needleman_wunch (const Path_t< Node > &a, const Path_t< Node > &b)

Additional Inherited Members
Protected Member Functions inherited from SmartPointer
	SmartPointer ()

virtual	~SmartPointer ()

Detailed Description

template<typename Node, typename Edge, typename Graph>
class gatb::core::debruijn::impl::TraversalTemplate< Node, Edge, Graph >

Class that traverse nodes of a Graph.

The Traversal class traverses the graph according to several criteria (think of contigs and unitigs).

This is done through the 'traverse' method. As a result, one gets a Path object that holds the traversed path information. Typically, you start from a node in the graph, and you call traverse() from that node with a direction (forward or reverse). The function returns a path in the graph that corresponds to a sequence.

There are two kinds of traversal:

tools::misc::TRAVERSAL_UNITIG : one gets only the non-branching paths in the graph
tools::misc::TRAVERSAL_CONTIG : one gets contigs, according to the method implemented in Minia version 1

More specifically, TRAVERSAL_CONTIG attempts to ignore tips and bubbles. Note that this traversal isn't used in Minia versions 2 and 3 anymore. Since we can now simplify the graph, we just remove tips and bulge and then perform a TRAVERSAL_UNITIG in the simplified graph.

But anyway, TRAVERSAL_CONTIG is still provided here, as it can be of independent interest. Say, if you want to quickly create contigs in a targeted assembly scenario.

A factory method create is available and should be used by end users to instantiate this class.

This class is abstract since it doesn't implement avance. It is subclassed according to the wanted kind of traversal.

Example of use : we create a fake bank, build its graph and traverse the graph:

    const char* seqs[] =
    {
        "CGCTACAGCAGCTAGTTCATCATTGTTTATCAATGATAAAATATAATAAGCTAAAAGGAAACTATAAATA",
        "CGCTACAGCAGCTAGTTCATCATTGTTTATCGATGATAAAATATAATAAGCTAAAAGGAAACTATAAATA"
        //      SNP HERE at pos 31      x
    };
    // We create a fake bank with a SNP
    IBank* bank = new BankStrings (seqs, ARRAY_SIZE(seqs));
    // We load the graph
    Graph graph = Graph::create (bank, "-abundance-min 1  -kmer-size 15  -verbose 0");
    // We create a Terminator object
    BranchingTerminator terminator (graph);
    // We create a Traversal instance according to the chosen traversal kind
    Traversal* traversal = Traversal::create (traversalKind, graph, terminator);
    LOCAL (traversal);
    // We create a node from the start of the first sequence
    Node node = graph.buildNode (seqs[0]);
    Path path;
    int len = traversal->traverse (node, DIR_OUTCOMING, path);
    // We dump the length, the starting node and the path
    cout << "length=" << len << " " << graph.toString (node) << path << endl;

Member Function Documentation

TraversalTemplate< Node, Edge, Graph > * create	(	tools::misc::TraversalKind	type,
		const Graph &	graph,
		TerminatorTemplate< Node, Edge, Graph > &	terminator,
		int	max_len = `defaultMaxLen`,
		int	max_depth = `defaultMaxDepth`,
		int	max_breadth = `defaultMaxBreadth`
	)

static

Factory method that creates an instance of Traversal

Parameters

[in]	type	: kind of traversal
[in]	graph	: graph object to be traversed
[in]	terminator	: object used to tag traversed nodes
[in]	max_len	: maximum length of the traversal
[in]	max_depth	: maximum depth of the traversal
[in]	max_breadth	: maximum depth of the traversal

TraversalTemplate< Node, Edge, Graph > * create	(	const std::string &	type,
		const Graph &	graph,
		TerminatorTemplate< Node, Edge, Graph > &	terminator,
		int	max_len = `defaultMaxLen`,
		int	max_depth = `defaultMaxDepth`,
		int	max_breadth = `defaultMaxBreadth`
	)

static

Factory method that creates an instance of Traversal

Parameters

[in]	type	: type of traversal
[in]	graph	: graph object to be traversed
[in]	terminator	: object used to tag traversed nodes
[in]	max_len	: maximum length of the traversal
[in]	max_depth	: maximum depth of the traversal
[in]	max_breadth	: maximum depth of the traversal

const std::vector<std::pair<int, int> >& getBubbles ( ) const

inline

Get the bubbles found during traversal. One bubble is defined by the [begin,end] positions in the path.

Returns: vector of positions ranges.

unsigned int getMaxBreadth ( ) const

inline

Get the maximum allowed breadth

Returns: maximum breadth

unsigned int getMaxDepth ( ) const

inline

Get the maximum allowed depth

Returns: maximum depth

virtual std::string getName ( ) const

pure virtual

Get the name of the traversal.

Returns: traversal name.

Implemented in MonumentTraversalTemplate< Node, Edge, Graph >, SimplePathsTraversalTemplate< Node, Edge, Graph >, and NullTraversalTemplate< Node, Edge, Graph >.

float needleman_wunch	(	const Path_t< Node > &	a,
		const Path_t< Node > &	b
	)

static

Compute a global alignment between two path. NOTE: could be moved to Path class.

Parameters

[in]	a	: first path
[in]	b	: second path.

int traverse	(	Node &	node,
		Direction	dir,
		Path_t< Node > &	resulting_sequence
	)

inline

Traverse the graph starting from one node for a given direction. As a result, one gets a Path object

Parameters

[in]	node	: starting node of the traversal.
[in]	dir	: direction of the traversal
[out]	resulting_sequence	: path of the traversal

int traverse	(	Node &	startingNode,
		Node &	endingNode,
		Direction	dir,
		Path_t< Node > &	resulting_sequence
	)

Traverse the graph starting from one node for a given direction. As a result, one gets a Path object. We get also the last traversed node.

Parameters

[in]	startingNode	: starting node of the traversal.
[out]	endingNode	: starting node of the traversal.
[in]	dir	: direction of the traversal
[out]	resulting_sequence	: path of the traversal

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

/builds/workspace/publish-doc-api-gitlab/gatb-core/src/gatb/debruijn/impl/Traversal.hpp
/builds/workspace/publish-doc-api-gitlab/gatb-core/src/gatb/debruijn/impl/Traversal.cpp

Public Member Functions

Static Public Member Functions

Additional Inherited Members

Detailed Description

template<typename Node, typename Edge, typename Graph> class gatb::core::debruijn::impl::TraversalTemplate< Node, Edge, Graph >

Member Function Documentation

template<typename Node, typename Edge, typename Graph>
class gatb::core::debruijn::impl::TraversalTemplate< Node, Edge, Graph >