Dividindo e conquistando com simetrias em geometria de distâncias
Felipe Delfini Caetano Fidalgo
TESE
T/UNICAMP F448d
[Divinding and conquering with symmetries in distance geometry]
Campinas, SP : [s.n.], 2015.
168 p. : il.
Orientador: Carlile Campos Lavor
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica
Resumo: Motivado por estudos em estruturas 3D de proteínas, biomoléculas imprescindíveis no estudo da vida, surgiu um problema chamado Discretizable Molecular Distance Geometry Problem (DMDGP) que provou ser NP-Difícil. Para resolvê-lo, existe um algoritmo da literatura, Branch & Prune (BP), que...
Ver mais
Resumo: Motivado por estudos em estruturas 3D de proteínas, biomoléculas imprescindíveis no estudo da vida, surgiu um problema chamado Discretizable Molecular Distance Geometry Problem (DMDGP) que provou ser NP-Difícil. Para resolvê-lo, existe um algoritmo da literatura, Branch & Prune (BP), que utiliza uma estratégia combinatória de exploração de uma árvore binária de soluções associada ao problema. Além disso, foram descobertas relações de simetria que permitem obter uma solução, a partir de outra, através de reflexões nos chamados vértices de simetria. Alguns pesquisadores passaram a realizar este trabalho em paralelo (ParallelBP), dividindo uma instância em sub-instâncias, resolvendo localmente com o BP (o que pode ser feito em duas direções) e unindo as sub-soluções com movimentos rígidos, com o intuito de determinar as soluções em menor tempo. Nossa proposta é fornecer uma estratégia Dividir-e-Conquistar para resolver o DMDGP, de modo a melhorar a abordagem em paralelo. Ela possui três estágios. Inicialmente, dividimos uma instância em sub-instâncias duas-a-duas sobrepostas através dos vértices de simetria. Depois, utiliza-se os chamados gaps para decidir a direção em que o BP deve fornecer a solução local. Por fim, utilizamos rotações baseadas na Álgebra de Quatérnios para combinar as sub-soluções em soluções factíveis
Ver menos
Abstract: Motived by studies in 3D structures of proteins, essential biomolecules for Life, arised a problem called Discretizable Molecular Distance Geometry Problem (DMDGP) which proved to be NP-Hard. Aiming to solve it, there is an algorithm in the literature, Branch & Prune (BP), which uses a...
Ver mais
Abstract: Motived by studies in 3D structures of proteins, essential biomolecules for Life, arised a problem called Discretizable Molecular Distance Geometry Problem (DMDGP) which proved to be NP-Hard. Aiming to solve it, there is an algorithm in the literature, Branch & Prune (BP), which uses a combinatorial strategy of exploring a binary tree of solutions that is associated to the problem. Moreover, some symmetry relations have been discovered which allows the obtainance of one solution from the other one by means of reflections in the so-called symmetry vertices. Some researchers started to do this work using parallel computing (ParallelBP), dividing one instance into sub-instances, solving the problem locally with the BP (what can be done in two directions) and joining the sub-solutions with rigid movements, with the objective of determining the solutions in a smaller time. Our purpose, thus, is to provide a Divide-and-Conquer strategy to solve the DMDGP in order to improve the parallel version. It has three stages. Initially, the instance is divided into sub-instances two-by-two overlapping by means of the symmetry vertices. After, the so-called gaps are used to decide the direction that the BP ought to provide the local solution. Finally, we propose to use Quaternion Rotations to combine sub-solutions into feasible solutions
Ver menos
Lavor, Carlile Campos, 1968-
Orientador
Costa, Sueli Irene Rodrigues
Avaliador
Miqueles, Eduardo Xavier Silva, 1982-
Avaliador
Guardia, Giuliano Gadioli La
Avaliador
Bonates, Tibérius de Oliveira e
Avaliador
Dividindo e conquistando com simetrias em geometria de distâncias
Felipe Delfini Caetano Fidalgo
Dividindo e conquistando com simetrias em geometria de distâncias
Felipe Delfini Caetano Fidalgo
Exemplares
Nº de exemplares: 2
Não existem reservas para esta obra