memz

func BlockAlign ¶

func BlockAlign(a, b []byte)

This is a heuristic alignment. This does not do global alignemtn but does a hybrid.

For two given sequences, split it into 'blocks', where the blocks are of variable size and are marked by checkpoints in a rolling hash.

The rolling hash checkpoints are marked when the low order bits are all zero of a Rabin fingerprint. The number of low order bits for the fingerprint is taken to be:

1 + floor( sqrt( min(length(a), length(b)) ) )

When a sub sequence is marked by it's endpoints in the rolling hash, the CRC32 checksum is calculated and stored.

The two sequences checksums are then compared and an attempt to align matching checksums is made on the assumption that both sequences are mostly the same with some minor alterations in the middle.

Runs of sub sequence that don't have aligned checksums are recursively passed into Memz which a lower threshold set to mark when true global alignment should be performed.

If the mismatch run is found to be the length of the sequence, this function fails.

If the checksum alignment step fails, this function fails.

**THIS IS NOT GLOBAL ALIGNEMT**. This is a heuristic. This is primarily meant to be run on long strings that are relatively similar to each other. Though this isn't global alignemtn, some applications may find the alignment produced (if this heuristic succeeds) good enoug.