search

lh3 / bwa

Burrow-Wheeler Aligner for short-read alignment (see minimap2 for long-read alignment)
GNU General Public License v3.0
1.53k stars 555 forks source link

Trace Back Pointers in Smith Waterman #166

Closed vijay4454 closed 6 years ago

vijay4454 commented 6 years ago

Hello

I have recently started looking into sequence alignment algorithms in general and bwa-mem in particular. I have a basic question about the ksw_extend2 function in ksw.c in the bwa-mem codebase. At the outset, I must admit that I have a somewhat abstract understanding of the codebase and the ksw_extend2.

Now, as I understand, the ksw_extend2 applies seed extension using smith-waterman algorithm. In standard smith waterman, trace back pointers need to be computed in order to trace back the best matching path in the matrix. But I do not see any trace back pointers being computed in ksw_extend2 (or perhaps it is being computed and I do not understand which variable represents the trace back pointer)? Are these being computed somewhere else in the code?

Thanks in Advance Vijay

lh3 commented 6 years ago

Traceback is done by ksw_global() at the end, not by ksw_extend2.