Subject: [Boost-users] [graph] Query for interest: implicit de Bruijn graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-01-18 10:39:23
Would any Boost.Graph users be interested if I implemented an implicit de
Bruijn graph? The graph would have the following benefits and drawbacks:
- Would not use any storage, but would act as a d^k-vertex, d^(k+1)-edge
(for alphabet size d and word length k) graph.
- Would be exactly the de Bruijn graph (with no vertex merging or
filtering); those features could be added on top, using filtered_graph
and/or another wrapper layer.
- A filtered_graph based on a sparse property map could "enable"
vertices and edges to process in a given algorithm.
- A separate layer could enable processing of chains of vertices
together.
- I could provide a reverse complement map for the base-4 case, as well as
conversions between vertices and edges and strings of the correct
length.
If anyone is interested, I have a few questions as well:
- What should the performance tradeoff be between accessing a vertex's
incident edges vs. computing reverse complements?
- Does the k-mer size (word length) need to be chosen at run-time, or
would a compile-time setting be acceptable?
-- Jeremiah Willcock