[Boost-users] [graph] Query for interest: implicit de Bruijn graph

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