search

Martinsos / edlib

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

Adds basic implementation of the landau vishin prefix algorithm #119

Closed donikv closed 4 years ago

donikv commented 6 years ago

The implementation of the Landau-Vishkin algorithm, integrated into edlib, for calculating prefix edit distance. Please note that test scripts have been modified but cannot be used as is (hradcoded path to original implementation)

donikv commented 6 years ago

@Martinsos yeah, unfortunately at their current speed, infix and global algorithms are slower than edlib. On the other hand, performance improvements of the prefix algorithm are quite good, please check them out in the results section in the paper: https://github.com/donikv/Zavrsni_Rad/blob/master/Paper/zavrsni.pdf. Also I will remove the unnecessary perf_test scripts, I actually planned to do that before I opened this PR, but I forgot.

Martinsos commented 6 years ago

No prob thx I will check it out! Let me know when you are ready for another round of review.

Martinsos commented 6 years ago

Hey @donikv, hope you are doing well! How is the status, do you think we could end up merging this some time soon?

donikv commented 6 years ago

Hey @Martinsos, yeah sorry I had a lot of things I had to do for collage last few weeks. I was hoping to get it done by the end of the week.

Martinsos commented 6 years ago

No problem, just checking if it still on!

Martinsos commented 4 years ago

I will close this one for now since so much time passed, but we can reopen it if there will be interest.