CODEWITHSUNDEEP
algorithmsequence-alignment
Chakib Mataoui
Chakib Mataoui

Reputation: 31

Algorithm to align numerical sequences

Hi
I have two sequence of numerical data let's say :
S1 : 1,6,4,9,8,7,5 and S2 : 6,9,7,5
And i'd like to find a sequence alignment in both sense left-right and right-left.
So i used 2 techniques before asking i actually used the hungarian algorithm but it's not sequencial so it doesn't give good results
And i used a modified version of the Needleman–Wunsch algorithm but i think i'm maybe doing it wrong or something and i've been digging for at least 4 months for anything that could help me but i only find genetic algorithms which may be helpful but i was wondering if there's a algorithm that exists that i may haven't seen yet ?
So to formalise my question : How would you align two positive numerical (integer or double) sequences ?

Upvotes: 2

Views: 767

Answers (1)

Ghoti
Ghoti

Reputation: 759

I believe you can accomplish your objective with the following:

import string
from Bio import pairwise2
from Bio.pairwise2 import format_alignment

seq1 = "1649875"
seq2 = "6975"

numDict = {}
for x in range(0,10):
    for y in range(0,10):
        numDict[(str(x),str(y))] = -abs(x-y)
#print(numDict)

for a in pairwise2.align.globalds(seq1, seq2, numDict, -3, -1):
    print(format_alignment(*a)) #prints alignment with best score

#for a in pairwise2.align.globalms(seq1, seq2, 5, -5, -3, -1):
    print(format_alignment(*a))

The globalds alignment allows you to use a custom dictionary (in this case, I created a dictionary containing numbers ranging from 1-9 and found the absolute value of their difference when paired). If you just want a flat yes/no scoring system, you could do something like globalms, where a success is +5 and a failure is -5. Note, I advise using gap penalties when performing alignments. Also familiarize yourself with 'global' and 'local' alignments. More information on the Pairwise2 biopython module can be found here: http://biopython.org/DIST/docs/api/Bio.pairwise2-module.html

Upvotes: 1

Related Questions