search

maickrau / GraphAligner

MIT License
255 stars 30 forks source link

getting stuck in universal graph motifs #16

Open ekg opened 4 years ago

ekg commented 4 years ago

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.

maickrau commented 4 years ago

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.