search

Martinsos / edlib

Lightweight, super fast C/C++ (& Python) library for sequence alignment using edit (Levenshtein) distance.
http://martinsos.github.io/edlib
MIT License
514 stars 167 forks source link

Combine Myers with Landau Vishkin #19

Open Martinsos opened 10 years ago

Martinsos commented 10 years ago

Since Landau Vishkin is so fast when query and target are very similar, maybe it would be good idea to first start calculation with Landau Vishkin for a few small k, then if it does not produce result I can switch to Myers. Reason for this is that Myers is actually not very efficient for small k because it will calculate whole block anyway, although band is maybe very small.

Martinsos commented 10 years ago

This idea is really good. It would be vise to try with Landau Vishkin until we reach k = 64, and if no solution is found then continue with Myers. Of course we should try moving this boundary of 64, but I believe it could be good. This way we would get the most of both methods! Of course this is all just for SHW alignment mode.