Improvements in the score matrix calculation in multiple sequence

Transcrição

Improvements in the score matrix calculation in multiple
sequence alignments
Geraldo F. D. Zafalon
Evandro A. Marucci
José R. A. Amazonas
Liria M. Sato
José M. Machado
Geraldo F. D. Zafalon Evandro A. Marucci José
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
() sequence alignments
1 / 22
Sumário
1
Introdução
2
Definições
3
Problemática
4
Algoritmos e análises
5
Resultados
6
Conclusões
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
2 / 22
Sumário
1
Introdução
2
Definições
3
Problemática
4
5
Resultados
6
Conclusões
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
3 / 22
Motivação
Grande necessidade do uso de técnicas computacionais para resolução
de problemas biológicos cada vez mais complexos;
Busca por regiões que possam identificar pontos de cura de doenças
ou bloqueio de doenças;
Grandes perspectivas de aplicações em outras áreas.
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
4 / 22
Sumário
1
Introdução
2
Definições
3
Problemática
4
5
Resultados
6
Conclusões
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
5 / 22
Alinhamentos de Sequências
Técnicas que objetivam tratar dessas sequências de caracteres;
O tratamento dado por esses alinhamentos visa comparar as
sequências e buscar entre elas um rearranjo, tentando obter uma
número máximo de coincidências entre esses caracteres;
Inferências podem ser realizadas sobre as partes similares encontradas;
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
6 / 22
Alinhamentos Múltiplos
Um dos algoritmos de alinhamentos múltiplos mais utilizado é o
Progressivo [1, 2];
Dividido em três fases:
Alinhamento par-a-par;
Construção da árvore guia;
Alinhamento múltiplo;
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
7 / 22
Alinhamentos Múltiplos
Execução sequencial do algoritmo se torna inviável com o aumento do
número de sequências;
Utilização de técnicas de programação paralela;
Fase de alinhamento par-a-par é a mais crı́tica e a mais custosa
computacionalmente.
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
8 / 22
Sumário
1
Introdução
2
Definições
3
Problemática
4
5
Resultados
6
Conclusões
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
9 / 22
Proposta do trabalho
Otimizar a execução da fase de alinhamento par-a-par;
Utilização de um algoritmo progressivo com programação dinâmica,
adequando o seu paralelismo para grão-grosso;
Implementação do método de estimativa de pontuação [3]
paralelizado, para a fase de alinhamento par-a-par;
Avaliação do desempenho das duas estratégias, objetivando a redução
da complexidade computacional.
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
10 / 22
Algoritmo com Programação Dinâmica
Programação Dinâmica Paralela
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
11 / 22
Algoritmo com Estimativa de Pontuação
Estimativa de Pontuação Paralela
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
12 / 22
Sumário
1
Introdução
2
Definições
3
Problemática
4
5
Resultados
6
Conclusões
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
13 / 22
Contexto
Ambas as abordagens, foram executadas sob o mesmo conjunto de
testes;
As demais fases do alinhamento múltiplo, que são a construção da
árvore filogenética e o alinhamento múltiplo, foram providas pelas
mesmas estratégias para ambas;
Testes executados em cluster Beowulf de Athlon XP 2100+, com 1GB
de memória por nó, com 9 nós disponı́veis.
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
14 / 22
Avaliação de Desempenho
Nucleotı́deos
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
15 / 22
Avaliação de Desempenho
Aminoácidos
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
16 / 22
Qualidade dos alinhamentos
Estimativas de Pontuação (EP) X Programação Dinâmica (PD)
Genes
1ad3 ref1
1cpt ref1
1fmb ref4
1tis ref5
1ppn ref5
1gdoA ref5
1ubi ref3
1thm ref5
kinase ref4
Num. Seq.
4
9
9
18
26
42
48
49
62
EP
0.929
0.787
0.882
0.898
0.906
0.877
0.797
0.794
0.802
PD
0.899
0.845
0.852
0.867
0.893
0.823
0.786
0.775
0.804
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
17 / 22
Sumário
1
Introdução
2
Definições
3
Problemática
4
5
Resultados
6
Conclusões
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
18 / 22
Conclusões
Os resultados apresentados mostram um ganho de desempenho da
estratégia de estimativas de pontuação, em relação à programação de
dinâmica;
O ganho de desempenho foi da ordem de 15% no teste com
nucleotı́deos e 12% no teste com amino-ácidos.
Trata-se de um ganho significativo.
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
19 / 22
Conclusões
Nos testes de qualidade, abordagem de estimativas de pontuação
também apresentou melhores resultados;
Em quase todos os testes, a sua pontuação foi superior ao da
programação dinâmica;
Na média, apresentando melhores resultados.
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
20 / 22
Referências Bibliográficas
R. C. Edgar and S. Batzoglou, “Multiple sequence alignment,” Current
Opinion in Structural Biology, no. 16, pp. 368–373, 2006.
I. M. Wallace, G. Blackshields, and D. G. Higgins, “Multiple sequence
alignment,” Current Opinion in Structural Biology, no. 15,
pp. 261–266, 2005.
Y. Chen, Y. Pan, J. Chen, W. Liu, and L. Chen, “Partitioned
optimization algorithms for multiple sequence alignment,” in
Proceedings of the 20th International Conference on Advanced
Information Networking and Applications (AINA ’06), 2006.
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
21 / 22
Agradecimentos
OBRIGADO PELA ATENÇÃO!
Improvements
R. A. Amazonas
in theLiria
scoreM.matrix
Sato José
calculation
M. Machado
in multiple
22 / 22

Improvements in the score matrix calculation in multiple sequence

Transcrição

Documentos relacionados

NOME DA RUA ATUAL NOMES ANTERIORES RUA BARRETO

despacho - Tribunal de Justiça do Estado do Rio de Janeiro

recadastramento 2013 regularização da situação

fevereiro/16

resolução nº

Fundação de Apoio à Universidade Federal de São

Ministério das Comunicações - Busca CEP

Mato Grosso

Orientador de Disciplina - Araraquara

BOLETIM DE ANIVERSARIO FEVEREIRO 2016.pub

Sequences