Algoritmos para Problemas de Geometria Molecular
Sessão de Otimização
Felipe Fidalgo
[email protected]
Carlile Lavor
[email protected]
Instituto de Matemática, Estatística e Computação Cientíca
Universidade Estadual de Campinas
1
Introdução
As proteínas formam uma classe importante de moléculas. São codicadas nos genes e produzidas nas células
por um processo chamado de tradução. Essas, depois de formadas, é que atuarão nas mais variadas funções de
nosso organismo como determinação de caracteristicas hereditárias, transporte de nutrientes e metabólitos,
composição das células, entre outros.
Em relação à geometria protéica, a maioria das proteínas naturais têm estruturas tridimensionais especícas que estão intimamente ligadas às suas funções biológicas. Dessa forma, a determinação da estrutura
geométrica tornou-se um passo importante para a compreensão das propriedades biológicas de todas as proteínas [1].
Neste trabalho, analisamos um algoritmo da literatura para o Molecular Distance Geometry Problem
(MDGP) e propomos um novo algoritmo que mantém a qualidade das soluções obtidas pelo anterior, apresentando ganhos em termos de eciência computacional.
O MDGP consiste em determinar as posições dos átomos de uma molécula, no espaço tridimensional, a
partir de um conjunto de distâncias entre eles. As proteínas são uma boa motivação para o trabalho, já que
sua estrutura geométrica é de grande importância.
Podemos dividir este problema em duas classes: a primeira contém aqueles com conjunto completo de
distâncias, isto é, todas as distâncias são conhecidas, e a segunda contém aqueles com conjunto arbitrário de
distâncias, ou seja, onde na maioria das vezes o conjunto de distâncias é incompleto.
Os problemas da primeira classe podem ser resolvidos em tempo polinomial. Os que estão na segunda
são NP-difíceis. A classe que mais nos interessa é a segunda, porque abrange uma quantidade maior de casos
práticos.
Tal problema tem uma importante aplicação em biologia molecular e bioquímica e, em particular, na
determinação e predição da estrutura de proteínas [5].
Descrevemos dois métodos neste trabalho, sendo o segundo a nossa proposta para resolver o problema.
Ambos são baseados na resolução de sistemas lineares. Ao nal, comparamos a ecácia e o tempo de execução
deles.
2
Molecular Distance Geometry Problem (MDGP)
I = {1, ..., n}. Queremos determinar as coordenadas
x1 , ..., xn , onde xi = (xi,1 , xi,2 , xi,3 ), xi,k ∈ R (k = 1, 2, 3), indica a posição do átomo i
3
em R , para cada i ∈ I , usando um conjunto S de pares (i, j), com i, j ∈ I , para os quais conhecemos
a distância di,j ∈ R entre eles. Então, dadas as distâncias di,j entre os átomos i e j , as coordenadas das
posições x1 , ..., xn dos n átomos são solução do sistema não-linear de equações
Sejam
n
o número de átomos em uma dada molécula e
de tais átomos,
kxi − xj k = di,j ,
1
(i, j) ∈ S.
(1)
Logo, o problema é determinar tais soluções de modo eciente. Tal problema é chamado de Molecular
Distance Geometry Problem (MDGP).
Na prática, os valores das distâncias podem não ser exatos, isto é, eles podem conter erros. De forma
mais geral, os dados conhecidos para o MDGP podem ser cotas superiores (ui,j ) e inferiores (li,j ) para as
distâncias
di,j
de modo que
li,j ≤ kxi − xj k ≤ ui,j ,
(i, j) ∈ S.
(2)
Neste trabalho, apenas os casos onde as distâncias são dadas exatamente serão considerados.
As distâncias entre muitos dos pares de átomos em uma proteína podem ser determinadas a partir de
um certo conhecimento em Química usando, por exemplo, comprimentos e ângulos de ligações e, também,
experimentos de Ressonância Magnética Nuclear (RMN) [1]. Se conseguirmos obter um conjunto de distâncias
inter-atômicas sucientemente grande, então a estrutura de tal proteína pode ser determinada via resolução
de um MDGP [2].
A partir deste modelo, seguem dois métodos para lidar com sua resolução a m de determinar a estrutura
molecular desejada.
2.1
Algoritmo Iterativo de Determinação Geométrica
O primeiro método a ser descrito é o Algoritmo Iterativo de Determinação Geométrica (originalmente publicado como Geometric Buildup Algorithm ) apresentado por Dong e Wu em [3].
Iterativamente, para cada átomo ainda indeterminado,
xi , encontramos quatro átomos, a saber x1 , x2 , x3 , x4 ,
já posicionados cujas distâncias entre quaisquer dois deles sejam conhecidas e que sejam não-coplanares em
R3 . Logo, podemos denir o sistema linear




2
2
(kx1 k − kx2 k ) − (d2i,1 − d2i,2 )
(x2 − x1 )T


−2 (x3 − x1 )T  · xi = (kx1 k2 − kx3 k2 ) − (d2i,1 − d2i,3 )
T
2
2
(x4 − x1 )
(kx1 k − kx4 k ) − (d2i,1 − d2i,4 )
(3)
xi .
na incógnita
A matriz dos coecientes deste sistema é não-singular e, assim, o mesmo tem solução única.
2.2
Algoritmo T
O segundo método é a proposta que temos neste trabalho, apresentada em [4]. A estrutura deste tem muitas
das características do anterior. A principal modicação está no modo como se obtém o sistema linear a partir
do sistema não-linear.
A cada iteração, temos um átomo indeterminado, digamos
xj .
Encontramos, também, quatro átomos
cujas distâncias entre quaisquer pares dentre eles sejam conhecidas, não-coplanares e determinados cujas
coordenadas são
Assim,
xj
x1 , x2 , x3 , x4 .
integra a solução do sistema linear

1
1
−2 
1
1
onde
tj = −
kxj k
2



2
d2j,1 − kx1 k
xT1  2
2
tj
xT2 
dj,2 − kx2 k 

=

,
xT3  xTj
d2j,3 − kx3 k2 
2
xT4
d2 − kx4 k
j,4
é um termo de controle da solução.
As matrizes dos coecientes destes sistemas também são não-singulares. Desta forma, os sistemas lineares
deste método geram soluções únicas. Este sistema tem vantagens teóricas e computacionais, descritas em [4].
2
Referências
a edição, Freeman and Company, 1993.
[1] T. Creighton: Proteínas: estruturas e propriedades moleculares , 2
[2] G. Crippen and T. Havel: Distance Geometry and Molecular Conformation , John Wiley and Sons, 1988.
[3] Q. Dong and Z. Wu: A geometric build-up algorithm for solving the molecular distance geometry problem
with sparse distance data , Journal of Global Optimization, Volume 26, p. 321 - 333, 2003.
[4] F. Fidalgo and C. Lavor Algoritmos para Problemas de Geometria Molecular , Dissertação de Mestrado,
IMECC - UNICAMP, 2011.
[5] Z. Wu and D. Wu: An updated geometric build-up algorithm for solving the molecular distance geometry
problems with sparse distance data , Journal of Global Optimization, Volume 37, p. 661 - 673, 2007.
3