Uma proposta de adaptação do algoritmo Branch-and-Prune usando a interseção de quatro esferas para o Problema de Geometria de Distâncias Moleculares

• Clarice de Souza Santos UFAM
• Rosiane de Freitas Rodrigues UFAM
• Kelson Mota UFAM

Resumo

O problema de determinar a estrutura tridimensional de uma molécula, posicionando no espaço todos os átomos que a compõem, é denominado de Problema de Geometria de Distâncias Moleculares. Determinar tal estrutura geométrica partindo-se de um conjunto arbitrário incompleto de distâncias é um problema NP-difícil computacionalmente, onde conseguir uma solução viável em um tempo de execução razoável é um interessante desafio matemático e computacional. Neste trabalho, está sendo proposto uma adaptação do algoritmo de Branch-and-Prune, considerando o cálculo da interseção de quatro esferas através de sistema de equações lineares de distâncias Euclideanas interatômicas e sistema de matrizes de coordenadas internas da molécula, envolvendo ângulos de ligação e torção. Este é um resultado preliminar de uma pesquisa em andamento, ainda em estágio inicial, mas com promissores resultados, onde, a estrutura 3D parcial de proteínas da base PDB pôde ser determinada em tempo linear.

Referências

Dong, Q. and Wu, Z. (2002). A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances. Journal of Global Optimization, 22:365–375.

Dong, Q. and Wu, Z. (2003). A geometric build-up algorithm for solving the molecular distance geometry problem with sparse distance data. Journal of Global Optimization.

Lavor, C., Liberti, L., Maculan, N., and Mucherino, A. (2011). The discretizable molecular distance geometry problem. Comput Optim Appl.

Mucherino, A., Liberti, L., Lavor, C., and Maculan, N. MD-jeep: a software tool for Distance Geometry. http://www.antoniomucherino.it/en/mdjeep.php.

PDB (2013). Protein data bank. Disponível em http://www.rcsb.org/pdb/home/home.do. Acessado em fevereiro de 2013.

Saxe, J. (1979). Embeddability of weighted graphs in k-space is strongly np-hard. Proceedings of 17th Allerton Conference in Communications, Control and Computing, pages 480–489.

Silva, W. and Lavor, C.and Ochiand, L. S. (2008). Cálculo de estruturas de proteínas. Simpósio Brasileiro de Pesquisa Operacional.