Hustruenes ulike roller i Gesta Danorum

Antes do preenchimento da matriz de similaridades foi desencadeado, aquando da leitura da sequência a analisar, um processo de construção de listas ligadas para guardar as distâncias de ocorrência de cada base. No concreto foram criadas quatro listas, uma por cada tipo de base existente, que guarda nos seus nós informação sobre a distância da próxima ocorrência em número de bases, com excepção do primeiro nó que indica a que distância do início da sequência se encontra a primeira ocorrência dessa base. Estas quatro listas ligadas são o recurso usado para o ulterior preenchimento da matriz de similaridades.

A abordagem seguida para a descoberta de padrões de forma optimizada usa tabelas parciais para registar as similaridades presentes em segmentos da sequência (de dimensão m), face ao resto da sequência a analisar/comprimir. O algoritmo de preenchimento de cada matriz é simples e pode descrever-se pelos seguintes passos:

1. A tabela, uma matriz quadrada de dimensão m*m, é inicializada com todas a células iguais a zero.

2. Para cada base analisada, que está representada por uma coluna da tabela, são assinaladas com 1s, as células dessa coluna, nas linhas que correspondam às distâncias a que se encontram as ocorrências seguintes dessa mesma base. Em rigor a pesquisa exaustiva apenas necessita de ser feita a primeira vez que se pesquisa cada base diferente (a,c,g,t). Nas seguintes ocorrências, a lista da ocorrências a jusante já é conhecida, o que pode poupar tempo de processamento.

Em relação aos algoritmos clássicos da programação dinâmica, a simplicidade do algoritmo propicia uma elevada rapidez de execução, o que o torna utilizável em análise de sequências longas.

Considerando a sequência x=”tatccgcattatgcgata” de tamanho n=18, vejamos como proceder para calcular o número de 1s a preencher na matriz de análise, bem como a complexidade temporal associada. O número total de 1s a preencher na matriz pode ser calculado pelo seguinte teorema.

Teorema 4.1

Sendo n?=1+2+3+4+5+...+n, com n∈ , descrito como somatorial de n, tomando Ν como válida para o seu cálculo a fórmula

2 ) 1 ( ?= n n+ n , e considerando os somatórios

das ocorrências dos símbolos/bases na sequência a analisar como n1 (para as ocorrências de “A”), n2 (para as ocorrências de “C”), n3 (para as ocorrências de “G”), e n4 (para as ocorrências de “T”), a fórmula de cálculo dos 1s a preencher seria:

Número de 1s=(n1-1)?+ (n2-1)?+ (n3-1)?+ (n4-1)?

Para o exemplo do segmento x=”tatccgcattatgcgata”, com n=n1+n2+n3+n4=18 onde

n1=5, n2=4, n3=3 e n4=6, o número de células assinaladas seria:

Número de 1s=(4)?+ (3)?+ (2)?+ (5)?=10+6+3+15=34

Analisando a complexidade temporal associada a esta tarefa computacional, no pior caso, que ocorre quando todas as bases da sequência a analisar são iguais, temos para uma sequência de tamanho n, um complexidade temporal de O((n-1)?). No caso médio, o mais realista, teremos O(4((n/4)-1)?). Se considerar-mos analisar uma sequência de 1000 bases igualmente repartidas, e uma matriz de análise com um milhão de células (1000*1000) para preencher, teremos, em média, 4(249?)=124500 células a preencher com 1s. Considerando ainda, que para preparar a matriz para a análise de uma nova sequência teremos de a inicializar (recolocar todas as células a 0), a forma mais expedita de o fazer é reassinalar as células que antes colocamos a 1, agora a 0. Desta forma a complexidade temporal para um processo contínuo de análise, como acontece na realidade, por análise parcial das sub-sequências que compõem a sequência integral, deverá ser em média O(8((n/4)-1)?)

A matriz de análise irá conter informação útil relativa a padrões (denotada por sequências/concentrações de 1s) no seu triângulo superior. O triângulo inferior pode ser ignorado aquando da análise da presença de padrões. Vejamos o exemplo seguinte (Tabela 4.15), onde é analisado o segmento x=”tatccgcattatgcgata” de tamanho n=18.

T A T C C G C A T T A T G C G A T A 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 2 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 3 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 6 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 8 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 9 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 11 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Tabela 4.15 – Matriz de análise de similaridades.

Os padrões existentes revelam-se pelas sucessões de 1s, sem interrupções para os padrões exactos, e com interrupções para os padrões com mutações. A localização das repetições é obtida mediante a observação do número da linha onde se identifica o padrão, esse número indica a distância entre um padrão e a sua repetição. Mais adiante serão descritas em pormenor as metodologias para a análise e descoberta de padrões a partir da tabela de similaridades preenchida. Como exemplo, veja-se o padrão assinalado na Tabela 4.15, acima, onde o padrão “tatccg” se repete mais adiante (9 bases depois) e contém uma mutação na sua 4ª base.

Para o caso de sequências longas, cuja dimensão e respectiva necessidade de memória não permita a análise numa única tabela, o método subdivide a tabela em sub-tabelas de dimensão computável. Os padrões descobertos são mais tarde analisados para apurar as suas verdadeiras extensões através de eventuais contiguidades, emergindo os padrões máximos e globais. Reiterando a dispensa de processamento do triângulo inferior da

matriz de análise de similaridades, no caso do exemplo anterior é possível ter a análise fraccionada em sub-matrizes 3*3, tal como apresentada na Tabela 4.16.

T A T C C G C A T T A T G C G A T A 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 2 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 3 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 1 1 0 6 0 1 1 0 0 0 0 0 0 0 0 0 7 0 0 1 0 0 1 1 0 0 1 1 8 1 0 0 0 0 0 0 1 1 0 9 1 1 1 0 1 1 0 0 0 10 0 0 0 1 0 0 0 1 11 1 0 0 0 0 0 0 12 0 0 0 0 0 0 13 0 0 0 0 0 14 0 1 1 0 15 0 0 0 16 1 1 17 0 18

Tabela 4.16 – Subdivisão da matriz de análise de similaridades.

O número de matrizes de similaridade a preencher e analisar pelo SimSearch pode ser previsto em face da dimensão da sequência a analisar (n) e da dimensão das sub-tabelas (t) a usar. Recorrendo à fórmula do somatorial, presente no Teorema 4.1, o número de sub-tabelas corresponderá a (n/t)?. Comparativamente com os algoritmos de programação dinâmica, cuja complexidade temporal corresponde a O(mn), sendo m e n, os comprimentos das sequências a comparar, o algoritmo desenvolvido apenas percorre metade da matriz, e de uma forma geral a complexidade temporal poderia ser

O((mn)/2). Esta redução corresponde à isenção de pesquisa de padrões no triangulo

inferior da matriz global de similaridades. Acrescenta-se igualmente que as tabelas do SimSearch são binárias, o que evita operações aritméticas, relacionadas com esquemas de pontuação, no seu preenchimento.

Terminada a primeira fase do SimSearch para a obtenção da matriz de similaridades, o passo seguinte é definir um esquema de pontuação (scoring scheme) para valorizar cada um dos padrões (in)exactos descobertos dentro da sequência analisada, com a finalidade de os seleccionar como consideráveis, ou no caso especifico da utilização do SimSearch para a compressão, verificar se o padrão descoberto tem potencial para constituir uma entrada no dicionário ou, pelo contrário deve ser descartado.