Manipulação de cliques em processos de predição estrutural de moléculas complexas

Neste trabalho, o processo de predição estrutural de moléculas complexas, como as proteínas, é abordado, com enfoque na fase de pré-processamento onde as instâncias são obtidas através da tecnologia de Ressonância Magnética Nuclear (RMN) e, por consequência, apenas um subconjunto das distâncias interatômicas são conhecidas, tornando o processo de reconstrução completa da molécula desafiador e NP-difícil computacionalmente. O Problema de Geometria de Distâncias Moleculares (PGDM) é um problema derivado da elucidação estrutural da geometria de distâncias que pode ser definido como a obtenção de uma configuração tridimensional para a molécula respeitando as distâncias euclidianas conhecidas, ou seja, encontrar as posições $x_{1}, x_{2},\ldots, x_{n}$ para os átomos respeitando as distâncias conhecidas. Se o conjunto é arbitrário, ou seja, são conhecidas somente as distâncias entre alguns átomos da molécula, esse problema é NP-completo para imersão em uma dimensão $ PGDM_{1} $ e NP-difícil para imersão em dimensões maiores que 1 $ PGDM_{k} $ para $k>1$ . A estrutura tridimensional é conseguida através da imersão dos átomos no $\mathbb{R}^{3}$. Considerando a posição do ponto como $p=(u,v,w)$, imergir um ponto significa encontrar os valores das dimensões $u$, $v$ e $w$ para o ponto. Deste modo, um pré-processamento que possa prover uma ordem dos átomos que facilite a execução de técnicas algorítmicas é buscado, com várias propostas na literatura. O objetivo deste trabalho é explorar algoritmos de geração de cliques, subgrafos completos, de modo a primeiramente entender o comportamento das moléculas obtidas via RMN e, em seguida, fornecer estruturas parcialmente construídas para otimizar métodos de resolução do Problema de Geometria Molecular de Distância (MDGP), como a modificação realizada no processo de enumeração do algoritmo contínuo Geometric Build-Up, e na geração de instâncias para versões discretizadas do problema, indicando que a abordagem é promissora.