maickrau
getting stuck in universal graph motifs
I've been running into trouble with GraphAligner recently on graphs that contain "universal" motifs. These are small graph components that have the right combination of edges and node sequences which allow them to simulate any DNA sequence.
Is there any way to convince GraphAligner to drive through them rather than consuming the entire query sequence while aligning to them?
The alternative (removing them) is less trivial than I had hoped.
Is there any way to convince GraphAligner to drive through them rather than consuming the entire query sequence while aligning to them?
No easy way as far as I can see. I'm not sure how this could be implemented. Trying to force the path to not repeat through the universal motif isn't possible with the current DP formulation and looks NP-hard. The only way I see is to make sure the graph doesn't have them but I don't have a way of detecting them.
