Rust implementation of sequence alignment / Levenshtein distance by A* acceleration of the DP algorithm
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.

Sequence Alignment With A* Example

This is an example of using A* path finding to accelerate a dynamic programming algorithm, in this case the sequence alignment problem, which Levenshtein distance is a specific instance of.

Unlike the standard Levenshtein distance algorithm, this runs in something like O(n * e^2) time where n is the input length and e is the edit distance. It does this by using a heuristic like A* to explore only promising states along the diagonal of the grid and not the whole O(n^2) grid.

It is substantially faster for large files with few edits than the naive O(n^2) dynamic programming algorithm it is based on, but is still much slower than specialized and highly optimized global sequence alignment programs like Edlib. The difference is I wrote this in two hours and it's 150 lines of code including tests, debugging routines and examples.

It is written in Rust and contains two example programs:

  • seqalign: Reads to FASTA format genetic sequence files and prints the alignment distance.
  • seqalign_plain: Reads two plain text files and prints the alignment distance.