Helse- og sosialsektoren

Nesta seção, é descrita a variante do algoritmo do DIALIGN (seção 2.4.5) que foi projetada de modo a permitir que o alinhamento possa ser recuperado pelo hardware em espaço linear. 5.7.1.1 Visão geral

A idéia principal é a seguinte. Na primeira fase, são calculadas as matrizes escore e prec do algoritmo original (seção 2.4.5). Além disto, um vetor contendo um elemento para cada coluna armazena o maior escore encontrado nesta coluna, a linha onde o mesmo ocorre, e a linha e coluna onde ocorre o fragmento anterior. Ao término da primeira fase, verifica-se qual é o maior escore global, bem como suas posições na matriz (linha e coluna). Essas posições marcam o final do último fragmento que compõe o alinhamento ótimo. A partir daí, recuperam-se os fragmentos anteriores e compara-se com a posição do fragmento de maior escore encontrado naquela coluna. Se as posições forem as mesmas, o fragmento é adicionado ao alinhamento ótimo. Caso contrário, é feito o re-processamento de parte das matrizes até que seja atingido o final do fragmento que deveria ter sido o último recuperado. Esse procedimento é repetido até que o alinhamento seja totalmente obtido.

A figura 5.16 mostra um exemplo de alinhamento de duas seqüências CCCTTACCGGCCCT e CCCGGACCTACCT utilizando a variante projetada nesta tese para o DIALIGN.

Figura 5.16 - Exemplo de alinhamento utilizando a variante do DIALIGN

Na figura 5.16, os fragmentos são mostrados em linhas pretas e a eles são atribuídos nomes como F1, F2, F3, F4 e F5. Estão indicados na figura o alinhamento ótimo F1-F2-F5 e dois alinhamentos sub-ótimos F1-F3 e F4.

Na última coluna, marcado com um quadrado e uma seta está o fragmento F5 que é o último fragmento do melhor alinhamento. O fragmento F5 possui informação sobre o fragmento anterior que é F2, indicado por uma seta. Na coluna em que termina F2, existe outro fragmento (F3) cujo escore do alinhamento parcial é maior que o escore do alinhamento parcial que termina em F2. O vetor guarda o maior alinhamento parcial na coluna e, portanto, F3. Assim, não é possível recuperar o alinhamento na primeira rodada pois F2 não está na oitava coluna. Na segunda rodada, será feito o alinhamento de duas subseqüências cujo final (linha e coluna) é o mesmo de F2, garantindo que este fragmento estará no alinhamento. A segunda rodada é mostrada na figura 5.17.

Figura 5.17 - Segunda rodada no alinhamento utilizando a variante do DIALIGN

A figura 5.17 mostra que o alinhamento ótimo das subseqüências termina com F2. O fragmento anterior é F1 que pôde ser recuperado diretamente pois F1 é o melhor subalinhamento na terceira coluna. Como F1 não tem fragmento anterior então ele é o último fragmento. Uma vez recuperados todos os fragmentos, o alinhamento final é dado na figura 5.18.

C C C t t A C C g g c C C T

C C C g g A C C t - a C C T

Figura 5.18 – Alinhamento final

Na figura 5.18, as posições onde há coincidência são indicadas por bases com letras maiúsculas, as substituições são indicadas por ambas as bases estarem com letra minúscula e as inserções e remoções são indicadas por uma letra minúscula e um “-“. Como o DIALIGN não contabiliza espaços no seu escore, a posição dos espaços inseridos não é levada em

5.7.1.2 Detalhamento do algoritmo

O objetivo da variante do DIALIGN proposta é obter o alinhamento de duas seqüências A e B de tamanhos R e S respectivamente. O alinhamento final será o alinhamento de vários fragmentos (seqüência contendo apenas coincidências) que dão o melhor escore em termos do número total de coincidências. Para serem adicionados ao alinhamento, estes fragmentos deverão estar acima de um limiar T, definido pelo usuário. O algoritmo é composto de duas matrizes M[i,j] e N[i,j] sendo que 0 ≤ i ≤ R, 0 ≤j ≤ S onde R e S são os tamanhos máximos da linha e coluna respectivamente.

A matriz M corresponde a matriz de escore do DIALIGN original (seção 2.4.5) onde é feito o cálculo dos escores dos fragmentos individuais (seqüência de coincidências). É calculada através de programação dinâmica utilizando a fórmula 5.1:

M(i,j) = M(i-1,j-1) +1 , se Ai = Bj (5.1)

0, caso contrário

Os fragmentos são estendidos enquanto o elemento da seqüência A na posição i coincidir com o elemento da seqüência B na posição j. O valor 1 é atribuído para cada coincidência.

Os valores das diagonais w(D), de acordo com a fórmula 2.7, serão calculados na matriz M com a diferença que os valores abaixo do limiar T simplesmente não são utilizados em Cálculo_fase_1, como será detalhado depois. Para o cálculo de E(l,m) (fórmula 2.6), será utilizado log2 ao invés de ln pois a base dois é mais adequada para representação em

computadores digitais. No caso, l = m pois só existem “matches” (coincidências) nos fragmentos recuperados por esta versão do algoritmo. Assim, E(l,m) = -log2((0.25)m)= -log2

((2-2)m_{) que sempre será um número inteiro que exige menor espaço de representação no}

A matriz N corresponde à matriz prec (fórmula 2.12) no DIALIGN original. Cada posição i,j na matriz N contém três valores: o maior escore de alinhamento naquela posição, incluindo o último fragmento, linha_anterior e coluna_anterior que indicam a posição onde o penúltimo fragmento do alinhamento foi obtido. Eles são chamados respectivamente de N.escore, N.linha_anterior e N.coluna_anterior.

No primeiro passo, os campos de N(i,j) terão seus valores iniciais calculados em hardware através de programação dinâmica segundo a fórmula 5.2:

N(i-1,j-1).escore

N(i,j) = Max N(i-1,j).escore (5.2) N(i,j-1).escore

No cálculo inicial do valor de N(i,j), este terá seus três campos de valores equivalentes aos três campos de valores da posição entre N(i-1,j-1), N(i-1,j), N(i,j-1) que tiver o maior campo escore. Por exemplo, se N(i-1,j-1).escore for o maior em (5.2) então N(i,j).escore = N(i-1,j- 1).escore, N(i,j).linha_anterior = N(i-1,j-1).linha_anterior e N(i,j).coluna_anterior = N(i-1,j-1). coluna_anterior. Em caso de igualdade de escore, os valores que estão em N(i,j-1) tem preferência sobre N(i-1,j) e este sobre N(i-1,j-1) como em [Mor96]. O valor de cada posição N(i,j) pode mudar posteriormente no algoritmo.

Na variante proposta, o valor de σ(Di,j) (fórmula 2.11) é calculado e colocado em N(i,j).escore.

O fragmento precedente ao atual prec(i,j) (fórmula 2.12) é indicado através dos campos N[i,j].linha_anterior e N[i,j].coluna_anterior.

Além disto, são calculados quatro vetores de tamanho S que correspondem ao número de colunas. O vetor Maior_Escore, com posições de 1 até S =, armazena o maior escore obtido em cada coluna bem como a coluna do último fragmento do alinhamento. O vetor Linha_Maior_Escore armazena a linha onde foi obtido o último fragmento adicionado ao alinhamento parcial de maior escore. O vetor Coluna_Frag_Anterior armazena a coluna do

linha do penúltimo fragmento do alinhamento. Para recuperar o alinhamento, é necessário recuperar todos os fragmentos que o compõem bem como suas posições e seus escores. O conteúdo dos vetores está resumido na tabela 5.1.

Tabela 5.1 Conteúdo dos vetores

Nome Conteúdo

j coluna onde termina um fragmento

Maior_Escore[j] maior escore de alinhamento cujo último fragmento termina na coluna j

Linha_Maior_Escore[j] linha do último fragmento do alinhamento na coluna j Coluna_Frag_Anterior[j] coluna do fragmento anterior ao que termina em j Linha_Frag_Anterior[j] linha do fragmento anterior ao que termina em j

O cálculo dos vetores para cada posição i e j é feito conforme o algoritmo da figura 5.19: Cálculo_fase_1 (Seqüência A, Seqüência B, Tam_Linha, Tam_Coluna, Limiar T)

1: Inicializa todas as posições de M, N e dos vetores com zero 2: Para todo i