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

Hirschberg #40

Closed Martinsos closed 8 years ago

Martinsos commented 8 years ago

Implemented Hirschberg's algorithm for finding alignment path. This will allow us to align huge sequences because memory consumption for alignment is not quadratic anymore, but is linear. Hiscgberg's algorithm is used to split the problem of alignment into smaller sub-problems, and when they are small enough, they are solved with traceback algorithm (one I was using so far, normal algorithm for alignment). Also, alignment is somewhat faster then befare, which was somewhat unexpected but is a nice bonus :)!

Martinsos commented 8 years ago

I should go through the code, see if there is anything I can refactor / optimize, and also comment it real well since there is some complicated logic here, especially in hirschberg's algorithm.