Expected alternative alignment not shown

[JianjunJin]

Dear developers,

Thank you for developing this excellent tool!

Test Data

• the assembly graph file: snp.graph.gfa.txt
• a 15009-bp single-read file: test_reads.11_13946.fastq.txt

Problem Description

In the above assembly graph, as visualized, the difference between 2 and 3 is only one SNP (A vs G). So if a read is best aligned to <1>2<1, it was expected to have an alternative alignment of <1>3<1 . However, I always only got the best path to be <1>2<1 or 1. <1>3<1 never showed up in the result. I tried setting the --multimap-score-fraction to as low as 0.01, as well as other options (--seeds-mum-count, --seeds-mxm-windowsize, --seeds-minimizer-length, which triggered #77, and I used the solution described there), but it still does not generate <1>3<1.

How do we fine-tune the parameters so that GraphAligner can generate the expected alternative alignment of <1>3<1? Please help!

Thanks in advance! Jianjun

[maickrau]

This is a limitation of the DP backtrace used in GraphAligner. It will only produce one alignment per backtrace which is forced to be the best alignment path, so alternative alignments to different bubbles in the same region are not reported.

[Kinggerm]

Thank you very much for the quick reply and clear explanation! Would you have plans for other implementations that could potentially solve this problem? Do you know other algorithms that could possibly solve this problem?

[maickrau]

There's no concrete plan for fixing this in the near future. It's definitely something I'd like to have fixed, but so far I haven't come across any solution that would solve this in the general case (including alternate alignments through any arbitrary tangles).

[Kinggerm]

Thanks for the reply. I see it is difficult. Looking forward to your solution in the future. Feel free to close this issue, or leave it open if you plan to solve it.