Cum imbunatatesc algoritmul Needleman Wunsch de string matching ?

Pentru aliniamentul a doua siruri vreau o versiune a sa ce permite inserari de spatii goale si in sirul mare pentru cazul in care distanta e mai mica cand inserez in ambele siruri pentru a crea o potrivire mai buna.

Exemplu:  AAABCDDDE si ABCCCDEEE.

Dati-mi o idee va rog, sau pm cine e pasionat de algoritmica si imi poate zice unde sa caut.

Edited by urgenta, 01 January 2015 - 20:31.

#! usr/bin/env python
# -*- coding: utf-8 -*-
from score import Score
from sequence import Sequence
class NeedlemanWunsch:
	def __init__(self, firstSequence, secondSequence, score, openingGap, extendingGap):
		self.firstSequence_=firstSequence
		self.secondSequence_=secondSequence
		self.score_=score
		self.openingGap_=openingGap
		self.extendingGap_=extendingGap
		self.solutions_=[]
		self.V_=self.initMatrix() #Représentent les 3 matrices vues au cours
		self.W_=self.initMatrix()
		self.S_=self.initMatrix()
		self.calculS() #Calcul la matrice S
		self.findAlignement(len(self.firstSequence_)-1, len(self.secondSequence_)-1)
	def initMatrix(self, val=0):
		matrix=[]
		for i in range(len(self.firstSequence_)+1) :
			line=[]
			for j in range(len(self.secondSequence_)+1) :
				line+=[val]
			matrix.append(line)
		return matrix
	def calculS(self):
		for i in range(1, len(self.firstSequence_)+1):
			self.V_[i][0]=self.openingGap_+(i-1)*self.extendingGap_
			self.W_[i][0]=self.openingGap_+(i-1)*self.extendingGap_
			self.S_[i][0]=self.openingGap_+(i-1)*self.extendingGap_
		for j in range(1, len(self.secondSequence_)+1):
			self.V_[0][j]=self.openingGap_+(j-1)*self.extendingGap_
			self.W_[0][j]=self.openingGap_+(j-1)*self.extendingGap_
			self.S_[0][j]=self.openingGap_+(j-1)*self.extendingGap_
		for i in range(1, len(self.firstSequence_)+1):
			for j in range(1, len(self.secondSequence_)+1):
				self.V_[i][j]=max((self.S_[i-1][j]+self.openingGap_+self.extendingGap_), (self.V_[i-1][j]+self.extendingGap_))
				self.W_[i][j]=max((self.S_[i][j-1]+self.openingGap_+self.extendingGap_), (self.W_[i][j-1]+self.extendingGap_))
				self.S_[i][j]=max((self.S_[i-1][j-1]+self.score_.get(self.firstSequence_[i-1], self.secondSequence_[j-1])), (self.V_[i][j]), (self.W_[i][j]))
	def findAlignement(self, i, j, sequenceA="", sequenceB="", matching=""):
		if(i==0 or j==0):
			while(i>0):
				sequenceA=self.firstSequence_[i-1]+sequenceA
				sequenceB="-"+sequenceB
				matching=" "+matching
				i-=1
			while(j>0):
				sequenceA="-"+sequenceA
				sequenceB=self.secondSequence_[j-1]+sequenceB
				matching=" "+matching
				j-=1
			#Enregistrement dans la liste des résultats
			self.solutions_.append([self.S_[-1][-1], sequenceA, matching, sequenceB])
		else:
			if(self.S_[i][j]==(self.S_[i-1][j-1]+self.score_.get(self.firstSequence_[i-1], self.secondSequence_[j-1]))): #Diagonale
				if(self.firstSequence_[i-1]==self.secondSequence_[j-1]):
					match="|"
				else:
					match=" "
				self.findAlignement(i-1, j-1, self.firstSequence_[i-1]+sequenceA, self.secondSequence_[j-1]+sequenceB, match+matching)
			if(self.S_[i][j]==self.V_[i][j]): #Haut
				self.findAlignement(i-1, j, self.firstSequence_[i-1]+sequenceA, "-"+sequenceB, " "+matching)
			if(self.S_[i][j]==self.W_[i][j]): #Bas
				self.findAlignement(i, j-1, "-"+sequenceA, self.secondSequence_[j-1]+sequenceB, " "+matching)
	def __str__(self):
		solution=(str(len(self.solutions_))+" alignement(s) au total, de score: "+str(self.solutions_[0][0])+"\n")
		for i in range(len(self.solutions_)):
			solution+=("\n"
				+(self.solutions_[i][1])+"\n"
				+(self.solutions_[i][2])+"\n"
				+(self.solutions_[i][3])+"\n")
		return solution
if __name__ == '__main__':
	score=Score("blosum62.txt")
	sequences=Sequence("PDZ-sequences.fasta")
	openingGap=-14
	extendingGap=-4
	print(NeedlemanWunsch(sequences.getSequence(0), sequences.getSequence(1), score, openingGap, extendingGap))

Asta am facut pentru facultate anu trecut. E in python, calculeaza scorul de similaritate, la nevoie iti baga spatii in oricare din stranduri

Edited by dilo00o, 26 February 2015 - 16:09.