Depth-first search on a graph about gatb-core

[rchikhi]

Hi Michael,

Actually the reason why you'd want to do a BFS in such a case, is because doing a DFS might get you to traverse the whole graph due to repeated kmers. BFS enables to control the depth of traversal, related to genomic proximity. I.e. BFS with depth at most 1000 guarantees that you will find all paths of length at most 1000. DFS over at most, say 100,000 nodes, might get stuck following a repeated kmer and end up at a completely different location in your genome. Does that make sense?

Rayan

[mbhall88]

Hi Rayan,

Thanks for the quick response.

In my current example I do want to traverse the entire graph to ensure I have found every possible way of getting from my start kmer to my end kmer. Additionally, I don't expect these dBGs to be very large, they will most likely be built from sequences that should not span more than ~1000bp (in many cases will likely only be in the order of 50bp).

Another reason we were leaning towards DFS was it's ability to detect cycles.

Michael

[rchikhi]

I see. Actually, I cannot find an example of DFS in our code, only BFS. It could be easier to just fix your current DFS code, can you paste the part regarding cycle detection?

[rchikhi]

Found some (old) code that does a simple DFS using recursion:

gatb-core/gatb-core/src/gatb/debruijn/impl/Simplifications.cpp

Line 701 in 4958e3f

void Simplifications<GraphType,Node,Edge>::heuristic_most_covered_path_old(

[mbhall88]

Thanks Rayan - I really appreciate you taking the time.

I think I may have fixed my implementation. Will do some more rigorous testing on some corner cases tomorrow. If not, I will provide some code.

[rchikhi]

sure, just let us know

[mbhall88]

Yes, it seems to be working now. Apologies for taking up your time. And thank you again for your assistance.