mengyao / Complete-Striped-Smith-Waterman-Library

294 stars 112 forks source link

Fix Back Trace Error in Alignment #78

Closed evolvedmicrobe closed 2 years ago

evolvedmicrobe commented 3 years ago

We encountered a bug in the library, which can be reproduced as follows: Given this reference and query files:

>ref
AGTGTAAACTGTACCTGATGGCTAA
>probe
ATGTAAACTGTACCTGATGGCTAA

The alignment produced by this command is clearly incorrect, though the alignment score appears correct for the "right" alignment:

python pyssw.py ref.fa query.fa -c -m 3 -x 2 -o 2 -e 1
target_name: ref
query_name: probe
optimal_alignment_score: 70 suboptimal_alignment_score: 22  strand: +   target_begin: 1 target_end: 25  query_begin: 1  query_end: 24

Target:       1 AGTGTAAACTGTACCTGATGGCTA    24
                |****||******|*****|***|
Query:        1 ATGTAAACTGTACCTGATGGCTAA    24

Making this change produces the correct alignment, as it appeared the issue was due to the traceback terminating too early:

target_name: ref
query_name: probe
optimal_alignment_score: 70 suboptimal_alignment_score: 22  strand: +   target_begin: 1 target_end: 25  query_begin: 1  query_end: 24

Target:       1 AGTGTAAACTGTACCTGATGGCTAA   25
                | |||||||||||||||||||||||
Query:        1 A-TGTAAACTGTACCTGATGGCTAA   24

I didn't have time to audit the code thoroughly enough to know if this solution was always valid, but it appeared to work on several tested examples.

martin-steinegger commented 3 years ago

This PR should fix https://github.com/mengyao/Complete-Striped-Smith-Waterman-Library/issues/61

mengyao commented 2 years ago

Thank you so much for pointing out this. This point makes sense, however your code doesn't work at my place. I manually made your recommended change in my code. I will update the master branch with this change soon.