Next: Resultados Up: BlastPhen Agrupamento por similaridade Previous: Blast
O programa passa as seqüências ao Blast para comparar os genomas uns com os outros, de maneira par a par. O Blast compara segmentos de um genoma com segmentos de outro, e a cada uma dessas comparações é atribuído um valor (score) que indica a similaridade desses segmentos. Quanto mais alto o score, maior a similaridade. O BlastPhen utiliza os resultados do Blast para construir distribuições de scores por sua freqüência para cada par de genomas. (Para mais informações sobre o Blast veja a seção 3.2 ou [2].)
As distribuições são analisadas através das medidas estatísticas descritas em 3.1.
Para as medidas média, mediana e moda, submetemos dois genomas ao Blast, obtendo uma distribuição de scores por sua freqüência. Calculamos então a média, a mediana e a moda dessa distribuição, que são candidatas a distância entre os genomas.
Para as métricas de comparação de distribuições, o procedimento de cálculo da estimativa de distância genética é um pouco mais complexo. Seja G1 um genoma. Para calcular as distâncias entre G1 e os demais genomas procederemos da seguinte maneira. Primeiramente comparamos G1 com ele mesmo, através do Blast, obtendo então uma distribuição de scores D11. Em seguida, para descobrir a distância entre G1 e Gn compararemos os genomas com o Blast, obtendo outra distribuição de scores D1n, e então compararemos as duas distribuições obtidas (D11 e D1n).
Após compararmos todos os genomas e utilizarmos as métricas estatísticas mencionadas, obtemos uma matriz de distâncias (para cada métrica). Observemos que essa matriz não é simétrica (isso se deve à maneira como o Blast calcula os scores). Para simetrizar a matriz, fazemos a média aritmética dos elementos correspondentes. Depois, subtraímos o elemento da diagonal principal dos demais elementos da linha. Com isso obtemos uma matriz simétrica que, além disso, terá zeros em sua diagonal principal. A explicação para esse procedimento é que podemos entender os valores da diagonal como sendo a menor distância que um genoma pode ter até outro, ou seja, a menor distância que um genoma G pode ter a um outro qualquer é a distância que ele tem até si próprio. Pela maneira como são calculados os scores e pelo método como o BlastPhen calcula as distâncias, um genoma não terá distância zero até si próprio, ao contrário do que esperaríamos. Encaramos esse valor como um fator de ajuste, por isso o subtraímos das demais distâncias entre esse genoma e os outros. Através de testes com as bases de dados mencionados observamos que esse procedimento é válido.
Opcionalmente, o BlastPhen permite a criação de bonsais. Os bonsais são equivalentes a cliques da teoria dos grafos: são grupos de vértices dois a dois adjacentes. Na genética, um bonsai é um grupo de organismos que possui uma relação ancestral (i.e. distância finita) com todos os outros organismos desse grupo. Essa separação de organismos é possível porque às vezes o Blast não pode detectar scores significativos entre dois ou mais organismos, pois seus genomas podem ser muito diferentes.
O algoritmo para criação de bonsais é simples. Tendo um conjunto de organismos em mãos, que inicialmente é o conjunto de todos os organismos passados ao BlastPhen, procuramos por uma distância infinita entre dois elementos. Se acharmos uma distância infinita entre O1 e O2, separamos os organismos em dois grupos: um deles contendo todos os organismos menos O1 e o outro contendo todos menos O2.
O problema é que esse algoritmo é exponencial. Assim, se existirem muitos bonsais essa etapa pode ser muito demorada.
Depois de separar os organismos em Bonsais, o BlastPhen gera diversas matrizes de distâncias, uma para cada bonsai.
Tendo a(s) matriz(es) de distâncias do BlastPhen, o usuário pode utilizar o programa neighbor (do pacote de programas Phylip, disponível em [3]), ou qualquer outro programa similar, para gerar as árvores filogenéticas. Neste projeto as árvores foram geradas com o programa citado utilizando a técnica de UPGMA (mais informações sobre essa técnica em [5]).
Com o intuito de otimizar o desempenho do BlastPhen, seu código foi programado para utilizar diversas máquinas com diferentes números de processadores. A idéia inicial era utilizar o padrão MPI [1] para realizar a comunicação entre as máquinas. Tentamos utilizar a implementação mpich [4], mas ela não se comportou bem com algumas arquiteturas. Tentamos então o lam-mpi [8], mas ela não conseguia lidar com firewalls, algo imprescindível no projeto, pois uma das máquinas se localizava no IME enquanto que as outras se encontravam no ICB. Por fim, optou-se por utilizar sockets para realizar a comunicação.
A parte do processo que se beneficia da paralelização é a submissão dos genomas ao Blast. Um processo servidor controla a distribuição de genomas aos processos clientes, que por sua vez os submetem ao Blast. Quando todas as seqüências forem utilizadas, o processo servidor reúne os resultados e o BlastPhen prossegue com seus cálculos.
Ricardo Nishikido Pereira 2004-12-06