Universidade Federal de Pernambuco
Centro de Informática
IF672 - Algoritmos e Estruturas de Dadosjunho a setembro de 2002
Entrega:
Segunda-feira, dia 09 de setembro de 2002
Faça um programa para encontrar um alinhamento ótimo de duas cadeias de
caracteres dadas.
O alinhamento pode ser global ou semi-global, sendo este um parâmetro de
entrada.
O custo das operações de edição são: Match = + 3, Substituição = - 1, Inserção = - 3, Remoção = - 3.
Caso haja mais de um alinhamento com o mesmo custo, dar prioridade às operações na ordem: Match > Substituição > Inserção > Remoção.
PARÂMETROS DE ENTRADA:
PROCESSAMENTO
As possibilidades de alinhamento que usaremos para a lista 4 são: global e semi-global.
O alinhamento global consiste em inicializar a primeira linha com -- 3 * j, e a primeira coluna com -- 3 * i.
O preenchimento de cada célula pega o valor máximo das três opções indicadas no slide do algoritmo M.
O alinhamento é feito backwards, da posição (m,n) da matriz até a posição (0,0).
O alinhamento semi-global vai rodar duas variações da construção da tabela M abaixo. Aquela que der um
escore maior será escolhida. As duas tabelas serão construídas da seguinte forma.
1. IGNORA INSERÇÕES NO INÍCIO E REMOÇÕES NO FIM DE s.
s: ---------------------------------XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
t: YYYYYYYYYYYYYYYYYYYYYYYY---------------------------------------------------------------------
> Inicializa a primeira linha com zeros. (Ou seja, não cobra por inserções no início de s.)
> Procura o máximo na última coluna. (Ou seja, ignora as remoções no final de s.)
2. IGNORA REMOÇÕES NO INÍCIO E INSERÇÕES NO FIM DE s
s: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---------------------------------------------------
t: --------------------------------------------YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY
> Inicializa a primeira coluna com zeros. (Ou seja, não cobra por remoções no início de s.)
> Procura o máximo na última linha. (Ou seja, ignora as inserções no final de s.)
Alinhamento semi-global.
Note que o alinhamento semi-global é feito da mesma forma que o alinhamento global,
ou seja, começando na posição (m, n) da matriz e prosseguindo pois ambas as seqüências
completas, s e t,
precisam ser colocadas em align-s e align-t, respectivamente, para serem
posteriormente impressas.
ENTRADA
A entrada irá conter uma série de casos (pares de cadeias) para serem tratados.
Cada caso conterá três dados:
- Tipo de alinhamento desejado: Global (1) ou Semi-global (2),
- Cadeia s
- Cadeia t.
SAÍDA
A saída deve conter um alinhamento que seja ótimo entre as seqüências s
e t, baseado no tipo do alinhamento escolhido e nos custos
definidos na entrada.
FORMATO DA ENTRADA E SAÍDA
A entrada irá conter uma série de casos (pares de cadeias) para serem tratados.
Cada caso conterá três dados: Tipo de alinhamento (1 ou 2), cadeia s e cadeia t.
O final da série será indicado por um valor 0 (zero) no início de um caso.
Para cada caso da entrada, a saída deve conter três linhas, uma com o custo de alinhar s e t, uma com a seqüência align-s, outra com a seqüência align- t, que contêm as seqüências s e t originais, com " -" onde ocorrer uma inserção ou remoção, como descrito em sala de aula. Após listar cada tripla (custo,align-s, align- t), deixar uma linha em branco.
