Artur Lira – [email protected] Thiago Rocha – [email protected] Contexto Reconstrução Filogenética Por DNA Por ordem dos genes. Maximum Parsimony Breakpoint Analysis GRAPPA Impactos Na Biologia Computacional Conclusão Referências Filogenia hipóteses de relações evolutivas(relações filogenéticas) entre diferentes espécies. Representação em árvore Orangotango Gorila Chimpanzé Humano Reconstrução Filogenética Processo de inferir as relações evolutivas de um determinado conjunto de espécies a partir de conhecimentos em genética. ▪ Seqüenciamento de DNA ▪ Ordem dos genes (Whole Genome Based Phylogeny Reconstruction) Cada espécie é representada por sua seqüência genética Assume-se que cada caractere tem o potencial de evoluir Substituições A <-> T <-> G <-> C AAGACTT AAGGCCT AGGGCAT AGGGCAT -2 106 anos TGGACTT TAGCCCT TAGCCCA -3 106 anos TAGACTT AGCACTT AGCACAA AGCGCTT -1 106 anos Atualmente Nós da árvore são permutações dos genes da espécie 1 –5 3 4 -2 -6 ou 6 2 -4 –3 5 –1 A A C D X B E Y E Z C F B D W F 1 2 3 4 5 6 7 8 9 10 3 –8 –7 –6 –5 -4 9 10 8 10 • Inversão 1 2 • Transposição 1 2 3 9 4 5 6 7 • Transposição Invertida 1 2 3 9 -8 –7 –6 –5 –4 10 Raras mudanças genômicas Baixa freqüência de eventos evolutivos se comparado com substituições nas seqüências de DNA. ▪ Evoluções muito profundas podem ser inferidas com maior fidelidade Problemas NP-Hard N° de árvores possíveis é gigantesco ▪ (2x-5)!! = 3 * 5 * 7 * ... * (2x-5), onde x = n° de espécies Anos para se resolver maioria dos conjuntos de espécies estudados. Resultado não necessariamente é um ótimo global. Ótimo local Score Ótimo global Árvores Filogenéticas Busca minimizar (a partir de um critério) o número de pontos de mutação necessário para explicar as relações evolutivas entre as espécies. Definição: Dado um conjunto S de strings de mesmo comprimento e alfabeto, encontre uma árvore T como folhas sendo elementos de S e todos os nós internos strings de mesmo comprimento e alfabeto de S, de forma que tal árvore minimize o somatório dos comprimentos das arestas. ACT GTA ACA ACT GTT ACA GTT GTA ACA GTA ACT GTT ACT GTT 2 GTT GTA 1 2 GTA ACA ACA GTT ACT ACA ACT 1 3 3 MP score = 7 MP score = 5 ACA ACT GTA ACA GTA 2 1 1 MP score = 4 Melhor Opção GTT GTA A 2 X 3 B C 2 E Y 5 Z 2 J 6 2 2 C 3 D MP score = 27 2 2 W B E K 3 L 2 2 2 F 2 D MP score = 19 E 2 P 2 B A 2 F 2 A Q 1 R 2 2 1 2 2 D MP score = 16 Melhor Opção S B 2 M F Breakpoint: Dois genomas G e G’ com o mesmo conjunto de genes Existe um breakpoint em (gi , gj) de G se e somente se: ▪ (gi , gj) e (-gj , -gi) não aparecem em G’ Breakpoint Distance (BD) Número de breakpoints entre dois genomas Mediana de 3 genomas O genoma que minimiza o BD entre 3 genomas A partir de 3 permutações com sinal A, B e C, encontre uma quarta permutação D que: Minimize a soma das distâncias d(A;D) + d(B;D) + d(C;D) NP hard A D C B Implementação desenvolvida em 1997 por Sankoff e Blanchette Lida com dados simples e específicos Organismos com apenas um cromossomo ou organelas com um único cromossomo. Cada cromossomo representado por uma ordem orientada de genes Enumera todas as (2n-5)!! árvores de n nós. Utiliza redução de MPB para TSP (Travelling Salesman Problem) Representação de cada gene por um par de cidades conectadas por uma aresta. Complexidade computacional é exponencial para qualquer número de genomas. • Estima-se 200 anos para amostra de 13 genomas com 105 genes cada num único processador. Para cada árvore T do conjunto de árvores Inicialmente defina um nó para cada permutação Repita Para cada nó interno v com vizinhos A,B,C Resolva a MPB A B, C que gera D Se colocar D em v melhora o score da árvore T, altere a árvore e marque v como visitado. enquanto existir um nó interno de T não visitado Genome Rearrangement Analysis under Parsimony and other Phylogenetic Algorithms Bernard M.E. Moret, David A. Bader, Tandy Warnow ▪ University of New Mexico http://www.cs.unm.edu/~moret/GRAPPA/ Segue a idéia de BPAnalysis, mas com otimizações: Re-Engenharia Paralelismo Heurísticas semelhantes ao hill-climbing e Maximum Parsimony que busquem solucionar problemas NPHard de forma otimizada Identificação de gargalos na implementação Exemplos: a. loop unrolling, reduzindo o tempo de execução em um fator maior que 6. b. Reuso de Memória alocada. c. Métodos mais eficientes para cálculo de distâncias entre genomas em tempo polinomial. Eficiente geração paralela das árvores de BPAnalysis Cada processador manipula uma fração das árvores. Divide-To-Conquer Possibilidade de “pausar” o processamento. Aumento de desempenho na ordem de 1 milhão. Cache Sensitivo a. BPAnalysis: 60MB b. GRAPPA: 1.8MB Princípio de Localidade a. BPAnalysis: pobre localidade região de alta localidade em 12MB b. GRAPPA : boa localidade, região de alta localidade em 600KB Teste com plantas aquáticas da família Campanulaceae 13 genomas, 105 genes cada 1997: BPAnalysis : 200 anos em um único processador (est.) 2000: GRAPPA v1.1 usando o “512-processor Los Lobos Supercluster machine”: 2 minutos. Melhoria em fator de 200.000 por processador. 2003: GRAPPA v2: 2 minutos em um único processador. Melhoria num fator de 1 bilhão. Implementação mais eficiente que BPAnalysis Redução do tempo de análise em média de 2 anos para um dia. Redução de custos na pesquisa e desenvolvimento de drogas. Reconstrução Filogenética abre um novo e complexo campo de pesquisa na biologia computacional Problemas complexos que demandam algoritmos de alta performance e grande escala para serem solucionados. SETUBAL, J. C.; MEIDANIS, J. C. Introduction to Computational molecular biology. 1° ed. Thomson. 1997. GRAPPA. Disponível em: http://www.cs.unm.edu/~moret/GRAPPA/ A High-Performance Computational Tool For Phylogeny Reconstruction From Gene-Order Data. Disponível em: http://www.cs.unm.edu/~moret/botsoc.pdf. Último acesso: 9 Jan 2008 MORET, B. M. E. ; WYMAN, S. ; BADER, A. B. ; WARNOW, T.; YAN, M. Phylogenies from Gene Order Data: A Detailed Study of Breakpoint Analysis (2001). Disponível em: http://citeseer.ist.psu.edu/466513.html . Último acesso: 9 Jan 2008 Artur Lira – [email protected] Thiago Rocha – [email protected]
Download
