Autores

5451
Warley Gramacho da Silva
2487,44,872
5452
2487,44,872
5453
2487,44,872

Informações:

Publicações do PESC

Título
Algoritmos Sequenciais e Paralelos para Problemas de Geometria Molecular
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
11/7/2013
Resumo

Neste trabalho, propomos uma versão paralela do algoritmo Branch & Prune (BP) para o Discretizable Distance Geometry Problem (DDGP), que consiste em uma subclasse do Distance Geometry Problem (DGP) que pode ser discretizada. A idéia principal é dividir uma instância DDGP em sub-instâncias tantas quanto o número de processos envolvidos na computação paralela e chamar a versão sequencial do BP em cada processo. Devido à flexibilidade de discretização de instâncias DDGP, a subdivisão da instância original pode ser realizada de modo que todas as soluções geradas, para todas as sub-instâncias, são representadas em um sistema de coordenadas comum. Desta forma, a fase de comunicação do algoritmo paralelo, onde as soluções locais são combinadas para gerar o conjunto final de soluções, é muito eficiente. Apresentamos alguns experimentos computacionais, usando proteínas, e estudamos o comportamento do algoritmo em relação ao número de processos considerados. Para o DDGP relacionado a proteínas, o Discretizable Molecular Distance Geometry Problem (DMDGP), utilizando distâncias intervalares, conhecido como Interval Discretizable Molecular Distance Geometry Problem iDMDGP, propomos uma nova ordem para os átomos da cadeia principal de uma molécula de proteína, que permite a aplicação do Interval Branch & Prune (iBP) que resolve instâncias do iDMDGP. Por fim, propomos também um novo algoritmo para o Discretizing Vertex Order Problem (DVOP), que é uma importante etapa de pré-processamento do DDGP. Apresentamos alguns resultados computacionais que mostram que o novo algoritmo resolve de forma eficiente o DVOP.

Abstract

In this work, we propose a parallel version of the Branch & Prune (BP) algorithm for the Discretizable Distance Geometry Problem (DDGP), which consists in a subclass of Distance Geometry Problems (DGPs) that can be discretized. The main idea is to split a DDGP instance in as many subinstances as the number of processors involved in the computation, and to invoke the sequential version of BP on each processor. Due to the flexibility of the discretization of DDGP instances, the subdivision of the original instance can be performed so that all solutions generated locally solving the several subinstances are represented in a common coordinate system. This way, the communication phase of the parallel algorithm, where the local solutions are combined in order to generate the final set of solutions, is very efficient. We present some computational experiments, using proteins, and study the behavior of the algorithm in relation to the number of considered processors. For DDGP related proteins, The Discretizable Molecular Distance Geometry Problem (DMDGP) using interval distances, known as Interval Discretizable Molecular Distance Geometry Problem (iDMDGP) we propose a new handcrafted order for the protein backbones, which allows the application of the Interval Branch & Prune (iBP) algorithm that resolves instances of iDMDGP. Finally, we also propose a new algorithm for the Discretizing Vertex Order Problem (DVOP), which is an important pre-processing step for the solution of DDGP. We present some computational results showing that the new algorithm efficiently solves the DVOP.

Topo