Lightning

When converting to some variant difference format (GFF, gVCF, etc.) from FastJ, there is an alignment step that takes place to align the FastJ tile to the reference tile to produce the variant difference format. Often times these sequences are nearly identical, with only a few bases difference either from a SNP or small INDEL, for example. Naive dynamic programming can be done in O(N^2) time and space. Using Hirschberg's algorithm, space can be reduced to O(N) but still takes O(N^2) time.

It would be better to have an output sensitive algorithm that only uses time/space proportional to the number of differences in the two sequences. Such an algorithm is well known. I believe Ukkonen's algorithm is one such method. There is also work on using a checkpointing scheme.

Implementing one or both of these would significantly speed up conversion from FastJ to (e.g.) VCF. Most conversions are of ~250bp but there are a few which are in the ~10k region which slow down conversion and do not make arbitrary conversion from FastJ to VCF (etc.) fast.

The goal would be to extend something like memz with an output sensitive dynamic programming function or to create another stand alone library/function. Input should be a simple byte array. User specified fixed gap, match and mismatch costs should be allowed. Pairwise alignment would be desirable but not necessary.

Other References:

• An extension of Ukkonen's enhanced dynamic programming ASM algorithm
• Algorithms for Approximate String Matching
• A versatile divide and conquer technique for optimal string alignment