I am looking for an algorithm to find the "best" alignment between two sequences of integers similar to how one aligns nucleic acids or amino acids for homology comparisons. For example, the best alignment for the two sequences below is:
10 06 13 91 22 16 06 | | | | | | | 01 01 02 10 04 11 92 22 17 05
or an example with gaps:
10 _ _ 91 22 16 06 22 12 | | | | | | | 11 02 10 04 11 92 22 17 05
The alignment would be based on the distance between each number similar to aligning amino acid sequences where one would prefer to align a hydrophobic amino acid with another hydrophobic amino acid because they are more "similar". I hope this explanation makes sense.
Another way to think about this problem is if you took the 20 amino acids and replaced them with a number from 1-20 instead of their single letter abbreviation and then tried to align 2 sequenced based on how close the numbers where, how would someone align them? In this example the alignment is based on how close two integers are from one another whereas when aligning amino acids the alignment is based on the chemical similarity of the amino acids, ie leucine is very similar to isoleucine whereas valine is very dissimilar to tryptophan.
I've been experimenting with using the biopython pairwise library and trying to utilize it for my problem. There is a similar approach to what I am looking for here:
This solution solves my problem, but only for the single character digits [0-9] and my numbers are more than one character.
Does anyone know of an approach (algorithm, package, library) to align sequences of integers? Ideally, I am looking for something in Python with a minimal working example.