Problema do Alinhamento de Sequências (ou da Distância de Edição)

Entrada:

 - duas sequências, X = x1...xm e Y = y1...yn
 
    - Ambas definidas sobre um mesmo alfabeto \Sigma

 - penalidades \alpha_ab >= 0 paga por casar os símbolos a e b do alfabeto \Sigma
 
    - em geral, \alpha_ab = 0 se a = b

 - e penalidade \alpha_gap >= 0 paga por casar um símbolo com um espaço

Solução:

 - um alinhamento de custo mínimo
 
    - um alinhamento é uma modificação das sequências originais que:

       - pode inserir espaços entre símbolos
	   
	   - mas não pode inverter ou remover quaisquer símbolos



Exemplo 1:

 - X = A G G G C T e Y = A G G C A
 
    - neste caso, m = 6 e n = 5
	
	- \Sigma = {A, G, C, T}
	
 - Uma solução possível é

	A G G G C T
	A G G - C A

    - e seu custo é \alpha_gap + \alpha_AT



Note que uma solução pode envolver adição de espaços em ambas as sequências

Exemplo 2:

 - X = G G T C C e Y = A G G C C
 
 - Uma solução possível é

	- G G T C C
	A G G - C C
	
	- e seu custo é 2*\alpha_gap



Vamos usar I(m, n) para denotar uma entrada para o problema do Alinhamento de Sequências em que:

 - a primeira sequência (X) tem m itens

 - e a segunda sequência (Y) tem n itens
 
 - deixamos implícito os valores dos custos \alpha

Vamos usar o símbolo & para denotar um alinhamento, ou seja, 

 - X & Y indica um alinhamento das sequências X e Y
 
 - exatamente qual é esse alinhamento será definido pelo contexto



Encontrando a subestrutura ótima em busca da recorrência:

 - Considere uma entrada I(m, n) e um correspondente alinhamento ótimo X & Y
 
 - Vamos focar nossa atenção na última posição deste alinhamento. Temos três possibilidades:
 
    1) xm alinhado com yn
	
	2) xm alinhado com espaço
	
	3) yn alinhado com espaço
	
	* note que não consideramos a opção espaço alinhado com espaço, pois este caso se reduz a uma solução melhor (removendo a última posição)
	
 - Sejam X' = X - xm e Y' = Y - ym



 - Vamos analisar 1) primeiro
 
    - neste caso o alinhamento X' & Y' 
	
	   - que obtemos quando removemos a última posição do alinhamento ótimo X & Y
	   
	   - é uma solução ótima para o subproblema I(m-1, n-1)
	   
	   Prova: sendo P o custo do nosso alinhamento de X' & Y' e supondo, por contradição, que exista uma maneira melhor (mais barata) de alinhar X' com Y' cujo custo é P*, adicionando ao final deste alinhamento xm alinhado com ym teríamos um alinhamento melhor que X & Y, i.e., 
	   
			P* + \alpha_xmyn <= P + \alpha_xmyn = custo de X & Y (contradição já que X & Y é ótimo).
	   
	- Qual o valor da solução ótima em função da solução ótima dos subproblemas neste caso?


	   
 - Vamos analisar 2)
 
    - neste caso o alinhamento X' & Y 
	
	   - que obtemos quando removemos a última posição do alinhamento ótimo X & Y
	   
	   - é uma solução ótima para o subproblema I(m-1, n)
	   
	   Prova: sendo P o custo do nosso alinhamento de X' & Y e supondo, por contradição, que exista uma maneira melhor (mais barata) de alinhar X' com Y cujo custo é P*, adicionando ao final deste alinhamento xm alinhado com espaço teríamos um alinhamento melhor que X & Y, i.e., 

			P* + \alpha_gap <= P + \alpha_gap = custo de X & Y (contradição já que X & Y é ótimo).

	- Qual o valor da solução ótima em função da solução ótima dos subproblemas neste caso?


   
 - Análise do caso 3) é identica ao caso 2), exceto por trocar X' por Y' e Y por X.



Escrevendo a recorrência:

 - Como nossos subproblemas dependem:

    - tanto do tamanho da primeira sequência
	
	- quanto do tamanho da segunda sequência
	
 - nossa recorrência terá dois parâmetros i e j
 
 - A[i, j] corresponde ao valor de uma solução ótima para o problema do Alinhamento de Sequências em que:

    - a primeira sequência é o prefixo de tamanho i de X (i = 1, ..., m)

    - a segunda sequência é o prefixo de tamanho j de Y (j = 1, ..., n)

 - Seguindo nossa análise da subestrutura ótima, temos a seguinte recorrência
 
    - A[i, j] = min{A[i-1, j-i] + \alpha_xiyj, A[i-1, j] + \alpha_gap, A[i, j-1] + \alpha_gap}

	- Observe que os casos base dessa recorrência ocorrem quando
	
	   - i = 0 ou j = 0
	   
	   - nestes casos, a sequência cujo prefixo não é nulo terá de ser alinhada com espaços. Portanto, 
	   
	      - A[i, 0] = i * \alpha_gap , 0 <= i <= m
		  
		  - A[0, j] = j * \alpha_gap , 0 <= j <= n



Projetando o algoritmo de Programação Dinâmica a partir da recorrência:

alinhamentoSequencias(X, m, Y, n, \alpha) {

	para i = 0 até m
		A[i, 0] = i*\alpha_gap
	
	para j = 0 até n
		A[0, j] = j*\alpha_gap
	
	para i = 1 até m
		para j = 1 até n
			A[i, j] = min{A[i-1, j-i] + \alpha_xiyj, A[i-1, j] + \alpha_gap, A[i, j-1] + \alpha_gap}

	devolva A[m, n]
}

Prova de corretude: Por indução matemática usando como hipótese a recorrência que demonstramos antes

Eficiência: Theta(mn), por conta dos dois laços aninhados e do fato que a recorrência pode ser resolvida em tempo constante.



Reconstruíndo a solução:

 - Dada uma tabela A preenchida pelo algoritmo
 
    - Começamos na posição A[m, n]
	
	- E vamos voltando de acordo com o caso da recorrência usado para preencher aquela posição

recSol(X, m, Y, n, \alpha, A){
	i = m
	j = n
	
	enquanto i >= 1 e j >= 1
		se A[i, j] = A[i-1, j-i] + \alpha_xiyj // caso 1
			xi & yj
			i--
			j--
		senão se A[i, j] = A[i-1, j] + \alpha_gap // caso 2
			xi & espaço
			i--
		senão // A[i, j] = A[i, j-1] + \alpha_gap // caso 3
			yj & espaço
			j--
	
	enquanto i >= 0
		xi & espaço
		i--
		
	enquanto j >= 0
		yj & espaço
		j--
	
	devolva o alinhamento obtido
}

Eficiência: \Theta(m+n), pois em cada iteração do laço principal pelo menos i ou j são diminuidos de uma unidade.