gatb.core-API-1.4.2
TraversalTemplate< Node, Edge, Graph > Class Template Referenceabstract

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

#include <Traversal.hpp>

Inheritance diagram for TraversalTemplate< Node, Edge, Graph >:
Inheritance 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:

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