Determinação da Estrutura de Proteínas através de

Universidade Nova de Lisboa
Faculdade de Ciências e Tecnologia
Departamento de Informática
Determinação da Estrutura de Proteínas através de
Programação por Restrições
Por:
Ludwig Krippahl
Dissertação apresentada na Faculdade de Ciências
e Tecnologia da Universidade Nova de Lisboa para
a obtenção do grau de Mestre em Inteligência
Artificial Aplicada.
Orientador Científico:
Professor Doutor Pedro Barahona
Lisboa, 1999
2
3
à Lena, pelas restrições que lhe impus durante este trabalho.
4
5
Agradecimentos
Agradeço antes de mais a ajuda do meu professor e orientador Pedro Barahona, e a sua paciência em
ensinar informática a um químico. Ao Brian Goodfellow e à Anjos Macedo agradeço a ajuda com os
dados e a técnica de RMN, e ao Nuno Palma o seu apoio e as indicações que me permitiram traduzir
para Português alguns termos que normalmente uso em Inglês. Pelas traduções eventualmente menos
felizes, assumo plena responsabilidade.
Este trabalho foi financiado em parte pela bolsa BM / 17904 / 98 do programa PRAXIS da Fundação
para a Ciência e Tecnologia
A figura 1.12 foi cedida por Brian Goodfellow.
A figura 1.8 foi criada com o programa RasMol, por R.Sayle
As imagens na figura 2.6 são propriedade de Land of Marbles, e foram usadas com autorização dos
proprietários.
As figuras 1.2, 1.3, 1.5, 1.6, 1.7, 1.9, 1.10, 2.1, 3.1, 3.15, 3.16, 3.17, 3.18, 3.19 e 3.20 foram criadas
com o programa CyberMol por Ludwig Krippahl e Nuno Palma.
6
7
Sumário
Nesta dissertação proponho uma abordagem baseada em técnicas de programação por restrições para
determinar estruturas de proteínas a partir de restrições de distância obtidas por Ressonância Magnética Nuclear (RMN). O primeiro capítulo é uma breve introdução à estrutura de proteínas. No segundo
capítulo descrevo o método proposto, que consiste essencialmente numa redução do espaço de possibilidades por técnicas de processamento de restrições, seguido por uma minimização. No terceiro capítulo mostro os resultados obtidos e um teste de comparação do desempenho do método com DYANA
("Dynamics algorithm for NMR applications” [17]), uma aplicação comercial baseada em técnicas de
minimização. Neste teste o tempo de cálculo para o DYANA foi de mais de seis horas, enquanto
método aqui proposto obteve resultados semelhantes em 8 minutos. Neste trabalho concluo que a aplicação de técnicas de Programação por Restrições podem reduzir significativamente o tempo de cálculo
para estes problemas
8
9
Abstract
In this dissertation I propose a constraint-based approach to determining protein structures compatible
with distance constraints obtained from Nuclear Magnetic Resonance (NMR) data. In the first chapter
I give a brief introduction to protein structure. The second chapter describes the method proposed,
which consists essentially of a constraint based reduction of the possibilities, followed by a local
search with an optimisation algorithm. In the third chapter, I show the results obtained, and compare
the performance of the algorithm with DYANA ("Dynamics algorithm for NMR applications” [17]) an
existing commercial application based on simulated annealing. In this test case, computation time for
DYANA was more than six hours, whereas the method proposed here produced similar results in 8
minutes. I conclude that the application of Constraint Programming techniques can greatly reduce
computation time in solving these distance constraint systems.
10
11
Índice
Introdução ...............................................................................................................................13
1. Estrutura de Proteínas ....................................................................................................15
1.1 Ligação Covalente........................................................................................................................ 15
1.2 Estrutura Primária ........................................................................................................................ 16
1.3 Estrutura Secundária. ................................................................................................................... 20
1.4 Estrutura Terciária........................................................................................................................ 22
1.5 Estrutura Quaternária ................................................................................................................... 23
1.6 Outros Elementos Estruturais....................................................................................................... 24
1.7 Quiralidade................................................................................................................................... 25
1.8 Ressonância Magnética Nuclear .................................................................................................. 25
2. Método .................................................................................................................................30
2.1 Modelação do Problema............................................................................................................... 30
2.2 Técnicas de Consistência ............................................................................................................. 32
2.3 Adaptação do Modelo .................................................................................................................. 40
2.4 Enumeração.................................................................................................................................. 46
2.5 Retrocesso .................................................................................................................................... 48
2.6 Minimização................................................................................................................................. 49
2.7 Verificação da Quiralidade........................................................................................................... 49
2.8 Discussão do Método ................................................................................................................... 50
3. Resultados ...........................................................................................................................52
3.1 Estrutura de Teste......................................................................................................................... 52
3.2 Representação dos Domínios ....................................................................................................... 54
3.3 Heurística de Enumeração............................................................................................................ 55
3.4 Sobreposição de Átomos.............................................................................................................. 59
3.5 Dependência das Restrições......................................................................................................... 61
3.6 Dimensão Final dos Domínios ..................................................................................................... 64
3.6 Desempenho................................................................................................................................. 66
3.7 Comparação com DYANA .......................................................................................................... 67
3.7 Outras Estruturas Testadas........................................................................................................... 70
4. Conclusão ............................................................................................................................76
Glossário ..................................................................................................................................78
Bibliografia..............................................................................................................................80
Apêndice A: Quadros .............................................................................................................84
12
13
Introdução
“A programação por restrições representa uma das melhores
aproximações que a informática já fez ao Cálice Sagrado da
programação: o utilizador expõe o problema, o computador resolve-o”
Eugene C. Freuder, CONSTRAINTS, Abril 1997
A Programação por Restrições (Constraint Programming) é um dos campos mais promissores na
informática moderna. A combinação de uma filosofia declarativa, eficiência e uma vasta aplicabilidade tornam estas técnicas uma ferramenta poderosa para a resolução de inúmeros problemas.
Com origem nos anos sessenta (6), as técnicas de Programação por Restrições evoluíram de soluções
para problemas específicos para um paradigma geral sobre a forma de resolver uma grande classe de
problemas. Determinantes para a concepção moderna de Programação por Restrições foram os trabalhos de Gallaire, Jaffar e Lassez (13, 22 em 6) em meados dos anos oitenta, que salientaram os muitos
elementos comuns entre a Programação em Lógica e a Programação por Restrições. Desde então a
formalização dos problemas de uma forma declarativa tem sido uma das ideias chave da Programação
por Restrições.
Esta noção não impede, no entanto, que as restrições sejam resolvidas de uma forma imperativa. O
recurso a linguagens imperativas, mesmo que apenas a baixo nível, é evidentemente inevitável. O importante neste conceito é que o utilizador possa expor o problema de forma declarativa. No trabalho
aqui descrito, como veremos adiante, foi precisamente esta a abordagem: a resolução das restrições foi
escrita numa linguagem imperativa (Object Pascal) mas a definição do problema a resolver consiste
apenas numa lista que declara as restrições a respeitar.
Outra noção fundamental na Programação por Restrições é a consistência entre valores de variáveis.
Uma restrição pode ser vista como um conjunto de combinações admissíveis para os valores das variáveis envolvidas. Os valores possíveis para cada variável dependem assim dos valores que outras
variáveis tomem. Garantindo a consistência entre os valores de grupos de variáveis consegue-se reduzir muito o espaço de pesquisa a percorrer para encontrar soluções admissíveis.
Nesta dissertação irei descrever o estudo de aplicabilidade destas técnicas à determinação de estruturas
de proteínas por Ressonância Magnética Nuclear (RMN). A motivação base para a procura de uma
forma mais eficiente de determinar a estrutura de proteínas não é apenas a curiosidade científica (excepto na opinião muito pessoal do autor). O campo da bioquímica estrutural tem muitas aplicações
práticas, em que qualquer melhoria no desempenho pode trazer muitas vantagens concretas e imediatas.
14
A industria farmacêutica moderna está cada vez mais dependente do conhecimento detalhado da
estrutura das macro-moléculas que formam os sistemas biológicos, entre as quais as proteínas se destacam pela sua importância. Em muitos campos da indústria proteínas desempenham papeis de grande
importância, desde os “glutões” do detergente, às enzimas que dão às “jeans” o “azul que a gente gosta” ou que catalisam a transformação de glicose em frutose na industria alimentar. Os recentes
desenvolvimentos na bioquímica e biologia molecular criaram uma nova indústria com um grande
crescimento económico, em que o conhecimento tem o potencial de se converter rapidamente em
dinheiro.
Em muitos casos a determinação estrutural de proteínas é o factor limitante na elucidação destes sistemas, pois é um processo demorado e muito exigente.
A tese que aqui defendo, suportada pelos resultados obtidos ao longo do trabalho, é que a aplicação de
técnicas de Programação por Restrições resulta num aumento significativo na eficiência, em relação
aos métodos até agora usados. Os métodos presentemente disponíveis assentam principalmente em
algoritmos de minimização. Um exemplo é a aplicação DYANA (17), neste momento a mais usada
para a resolução destes problemas na Faculdade de Ciências e Tecnologia. O algoritmo base desta
aplicação é o método de minimização simuilated annealing, partindo de uma estrutura gerada aleatoriamente. Desta forma são reduzidas progressivamente as violações às restrições impostas. As
desvantagens deste algoritmo são o enorme espaço de pesquisa que percorre e a propensão para ficar
preso em mínimos locais. Esta última torna necessário o cálculo de um número considerável de
estruturas (tipicamente 500) pois apenas uma pequena fracção destas é aceitável.
Nesta dissertação começarei por introduzir, no primeiro capítulo, as noções básicas de estrutura de
proteínas que são relevantes a este trabalho. No segundo capítulo o problema será formalizado como
um problema de processamento de restrições, e serão expostos os algoritmos usados para o resolver.
Os resultados obtidos e a parametrização do programa serão apresentados no terceiro capítulo. No
quarto e último capítulo serão discutidas as vantagens e limitações do presente método, bem como alguns desenvolvimentos já planeados para o futuro.
15
1. Estrutura de Proteínas
Staudinger
salientou
que
“as
macro-moléculas
possuem
propriedades que não podem ser previstas a partir das propriedades
das suas unidades constituintes”... Aparentemente o único obstáculo
para compreender a natureza da vida é a sua fantástica
complexidade. A Informática dá nos a esperança que um dia
possamos vencer também esta dificuldade
H.A. Krebs, Persp. Biol. Med., 1971
Desde muito cedo na história da química que as proteínas têm atraído a atenção dos investigadores (3).
Em algumas substancias orgânicas observaram a intrigante propriedade de solidificar com o calor,
algo contrário à maioria, que normalmente derrete quando aquecida. Em 1777 Pierre Maquer chamoulhes substâncias albuminosas, de albumen, o nome em latim para a clara do ovo, que partilha esta propriedade com outras então conhecidas (caseína do leite, globulina do sangue, etc...).
Em 1839 o químico holandês Gerardus Mulder determinou a fórmula química C40H62O12N10 como
sendo comum a todas as substâncias albuminosas. Ele propôs que todas estas substâncias se formavam
a partir de moléculas com esta composição, e chamou a este grupo proteína.
A palavra proteína deriva da palavra grega protos, significando “primeiro” ou “mais importante”.
Apesar de mais tarde se descobrir que a hipótese de Mulder não era correcta, o nome persistiu e é de
certa forma apropriado, pois apesar de constituírem apenas cerca de 20% da massa orgânica nos seres
vivos (15), são a mais versátil classe de compostos orgânicos. Os papéis que desempenham nos sistemas biológicos são muito diversos; catálise de reacções, transporte, suporte e movimento, resposta
imunitária, entre outros (33).
Neste capítulo irei descrever os elementos estruturais das proteínas, e a forma como a Ressonância
Magnética Nuclear nos permite elucidar estas estruturas. As técnicas de análise estrutural por Ressonância Magnética Nuclear podem ser aplicadas ao estudo de uma vasta gama de compostos orgânicos,
mas irei focar apenas o caso das proteínas, por ser o relevante para este trabalho.
1.1 Ligação Covalente
Uma molécula é um conjunto de átomos unidos por ligações covalentes. A ligação covalente é formada, numa descrição muito simplificada, quando dois átomos partilham electrões. Os electrões deixam
de ocupar orbitais atómicas (centradas no núcleo de um único átomo) para ocupar orbitais moleculares
(dispersas por vários átomos), ligando assim os átomos envolvidos. Estas orbitais moleculares têm
mínimos de energia em geometrias bem definidas, tendendo a forçar os átomos da molécula a formar
estruturas semi-rígidas. No entanto as ligações podem sofrer algumas distorções, sendo estas:
16
•
Compressão e Extensão quando varia o comprimento da ligação química.
•
Flexão quando varia o ângulo formado por duas ligações com um átomo em comum.
•
Torção quando varia o ângulo entre uma ligação e o plano definido pelas duas ligações consecutivas (ângulo diedro)
A Figura 1.1 ilustra estas variações na geometria duma molécula.
Compressão/Extensão
Torção
Flexão
Figura 1.1
Possíveis distorções à geometria de ligações covalentes.
As ligações covalentes são resistentes a distorções de Compressão, Extensão e Flexão, e por isso a
amplitude destas é, em geral, pequena. Muitas ligações têm uma liberdade significativa de Torção. As
ligações Carbono-Carbono e Carbono-Azoto em cada aminoácido (ver 1.2 Estrutura Primária adiante)
são um exemplo de ligações com grande liberdade de Torção, o que permite uma enorme diversidade
nas estruturas de proteínas.
1.2 Estrutura Primária
Cada proteína é formada por uma ou mais cadeias de aminoácidos, que são pequenas moléculas orgânicas contendo um grupo ácido (ácido carboxilico: COOH) e um grupo amina (NH2). Estes dois grupos estão ligados a um átomo de carbono que é designado como Cα (Carbono alfa). Esta região formada pelo grupo amina, o grupo carboxilico e Carbono alfa é comum a todos os aminoácidos que participam na formação de proteínas. Aminoácidos diferentes distingem-se pelo grupo de átomos ligado
ao Cα. Este grupo, formando a restante estrutura do aminoácido é designado por cadeia lateral.
Em solução aquosa, em condições fisiológicas, os grupos amina e ácido carboxilico encontram-se
normalmente na forma ionizada. O grupo ácido carboxilico (COOH) tende a ceder um ião H+ para a
água. Assim em solução este grupo encontra-se tipicamente na forma de carboxilato (COO-). O grupo
amina tende a ligar-se a um ião H+ em solução, e por isso em solução estará tipicamente na forma
17
NH3+. A associação/dissociação de iões H+ está dependente da concentração destes em solução, ou
seja, do pH da solução1, mas esta descrição é correcta na maioria dos casos em condições fisiológicas.
A Figura 1.2 mostra a estrutura de três aminoácidos (Glicina, Leucina e Tirosina) nestas condições,
salientando os grupos amina e ácido carboxilico aqui referidos. Como se pode ver nesta figura, uma
parte da estrutura é comum a todos os aminoácidos, e apenas as cadeias laterais distinguem os aminoácidos.
Glicina
Carboxilo
Leucina
Amina
Carboxilo
Cα
Tirosina
Amina
Cα
Carboxilo
Cα
Amina
C
N
O
Cadeias Laterais
H
Figura 1.2
Estrutura de três aminoácidos em solução. Os grupos ácido carboxilico e amina estão marcados em cada aminoácido, bem como o Carbono alfa. Estes formam a estrutura comum a todos os aminoácidos e compõem a cadeia
principal da proteína. Na região inferior estão representadas as cadeias laterais que distinguem os diferentes
aminoácidos.
Em sistemas biológicos já foram encontrados mais de 300 aminoácidos, mas regra geral as proteínas
contém apenas 20 aminoácidos diferentes (15). Por isso iremos apenas considerar estes 20 aminoácidos mais comuns. No entanto todos os algoritmos aqui descritos (ver 2. Método, página 30) podem ser
aplicados a proteínas com aminoácidos menos comuns ou mesmo outras moléculas (ver 1.6 Outros
Elementos Estruturais, página 24).
A Tabela 1.1 mostra os nomes destes aminoácidos, bem como as abreviaturas e os símbolos normalmente usados para os identificar. Neste documento serão utilizadas as abreviaturas de três letras para
referir os aminoácidos específicos.
A importância dos aminoácidos nos sistemas biológicos vem da capacidade que os grupos amina e
ácido carboxilico têm de formar uma ligação entre o Carbono do grupo carboxilico e o Azoto do grupo
amina.. Esta ligação é chamada ligação peptídica.
1
O valor de pH é o simétrico do logaritmo da concentração de iões H+.
18
Nome
Abreviatura
Símbolo
Ácido Aspártico
Asp
D
Ácido Glutâmico
Glu
E
Alanina
Ala
A
Arginina
Arg
R
Aspargina
Asn
N
Cisteína
Cys
C
Fenilalanina
Phe
F
Glicina
Gly
G
Glutamina
Gln
Q
Histidina
His
H
Isoleucina
Ile
I
Leucina
Leu
L
Lisina
Lys
K
Metionina
Met
M
Prolina
Pro
P
Serina
Ser
S
Tirosina
Tyr
Y
Treonina
Thr
T
Triptofano
Trp
W
Valina
Val
V
Tabela 1.1
Nomes, abreviaturas e símbolos para os 20 aminoácidos mais comuns (15,33).
O nome deriva de peptós, palavra grega para digestão, pois esta é a ligação quebrada na digestão de
proteínas. A Figura 1.3 ilustra a formação duma ligação peptídica entre uma Cisteina e uma Histidina.
Em condições fisiológicas a reacção é mais complexa do que a Figura 1.3 indica, não só pelo estado
ionizado dos grupos que reagem (ver acima) mas também porque estas reacções são catalisadas por
outras proteínas.
A Figura 1.3 mostra também (ilustração inferior) os dois aminoácidos ligados pela ligação peptídica.
Pode-se notar aqui uma sequência contínua formada pelos átomos Carbono do grupo ácido carboxilico, Carbono alfa e Azoto do grupo amina de cada aminoácido. Este padrão ...-C-Cα-N-C-Cα-N-...
repete-se por toda a cadeia de aminoácidos, e é designado como cadeia principal da proteína (backbone). Estes átomos estão marcados na Figura 1.3 (ilustração inferior). Esta propriedade permite a
agregação de aminoácidos em longas cadeias, contendo centenas ou milhares de átomos.
19
Amina
Carboxilo
Água
C
Cisteina
Histidina
N
O
C
N
Cα
C
N
Cα
H
S
Ligação
Peptídica
Figura 1.3
Formação da ligação peptídica entre Cisteína e Histidina. No topo está esquematizada a reacção de ligação entre
os dois aminoácidos. A figura abaixo representa a estrutura molecular formada pelos dois aminoácidos ligados
pela ligação peptídica.
A estrutura primária é a sequência de aminoácidos nas cadeias que formam a proteína. Na estrutura
primária incluí-se tipicamente também a informação sobre pontes de dissulfureto, mas estes elementos
estruturais serão focados mais adiante (ver 1.6 Outros Elementos Estruturais, página 24).
A assimetria da ligação peptídica e dos aminoácidos faz com que um dos extremos da cadeia contenha
sempre um grupo amina, e o outro um grupo ácido carboxilico. Por convenção, o aminoácido no extremo com o grupo amina livre é considerado o primeiro aminoácido. Esta convenção reflecte a ordem
pela qual os aminoácidos são adicionados na síntese das cadeias em sistemas biológicos.
A informação sobre a sequência primária das proteínas está contida no ADN (Ácido Desoxirribonucleico), que constitui o material genético dos seres vivos2.
A síntese de proteínas nas células processa-se em duas fases. Em primeiro lugar a sequência da zona
do ADN que codifica a proteína é replicada em ARN (Ácido Ribonucleico), num processo chamado
transcrição. Na segunda fase, a tradução, as cadeias de aminoácidos que formam a proteína são sintetizadas a partir do ARN. O ADN contém apenas 4 bases diferentes: Adenina, Guanina, Citosina, e
Timina. O ARN contém também Adenina, Guanina, e Citosina., mas contém Uracilo em vez de Timi2
O genoma de alguns vírus é composto por Ácido Ribonucleico (ARN)
20
Timina.. Como as proteínas contém 20 aminoácidos diferentes, cada aminoácido é codificado por
uma sequência de três bases, como se mostra na Tabela 1.2 (24).
Primeira Base
Segunda Base
U
C
A
G
U
UUU
UUC
UUA
UUG
Phe
Phe
Leu
Leu
UCU
UCC
UCA
UCG
Ala
Ala
Ala
Ala
UAU
UAC
UAA
UGA
Tyr
Tyr
Fim
Fim
UGU
UGC
UAG
UGG
Cys
Cys
Fim
Trp
C
CUU
CUC
CUA
CUG
Leu
Leu
Leu
Leu
CCU
CCC
CCA
CCG
Thr
Thr
Thr
Thr
CAU
CAC
CAA
CGA
His
His
Gln
Gln
CGU
CGC
CAG
CGG
Arg
Arg
Arg
Arg
A
AUU
AUC
AUA
AUG
Ile
Ile
Ile
Met
ACU
ACC
ACA
ACG
Pro
Pro
Pro
Pro
AAU
AAC
AAA
AGA
Asn
Asn
Lys
Lys
AGU
AGC
AAG
AGG
Ser
Ser
Arg
Arg
G
GUU
GUC
GUA
GUG
Val
Val
Val
Val
GCU
GCC
GCA
GCG
Ser
Ser
Ser
Ser
GAU
GAC
GAA
GGA
Asp
Asp
Glu
Glu
GGU
GGC
GAG
GGG
Gly
Gly
Gly
Gly
Tabela 1.2
Correspondência entre as sequências dos tripletos no ARN e os aminoácidos que estes codificam.
Hoje em dia existem assim duas abordagens possíveis para determinar a estrutura primária de uma
proteína:
•
A degradação química controlada das cadeias de aminoácidos permite a determinação directa da
sequência (degradação de Edman, 33).
•
A sequenciação do ADN/ARN que codifica a proteína permite determinar indirectamente a sequência desta.
A combinação destes dois métodos permitiu a determinação das estrutura primárias de muitas proteínas. Presentemente o número de estruturas primárias conhecidas aproxima-se de 100.000.
1.3 Estrutura Secundária.
O termo estrutura secundária refere-se ao conjunto de estruturas locais, estáveis, e que são elementos
comuns à maioria das proteínas (33). Por estas razões, é possível prever , com alguma confiança, estes
elementos estruturais, pelo que serão potencialmente uma importante fonte de informação acerca da
estrutura da proteína.
21
Apesar de a ligação peptídica ser uma ligação rígida, as ligações adjacentes Carbono-Carbono e
Carbono-Azoto (ver Figura 1.3) tem grande
liberdade
de
Torção
(ver
1.1
Ligação
...Ala-Leu-Ala-Met-Glu-Glu-Leu-His-Lys...
Covalente), permitindo à cadeia peptídica uma
grande variabilidade estrutural.
Essencialmente existem três elementos da estrutura secundária: hélice-α, folha-β e dobra-β.
Estas
estruturas
são
estabilizadas
pela
Figura 1.4
Na hélice-α as pontes de Hidrogénio ligam cada
aminoácido ao aminoácido quatro posições à frente na
sequência da cadeia.
formação de pontes de hidrogénio (ver 1.6 Outros
Elementos
Estruturais,
página
24)
entre
átomos
N
pertencentes à cadeia principal da proteína. São estruturas
O
estáveis e que podem ser previstas com alguma confiança
a partir da estrutura primária.
H
A hélice-α é uma espiral formada por pontes de
Ponte de
Hidrogénio
hidrogénio entre os átomos de Hidrogénio covalentemente
ligados aos átomos de Azoto, os átomos de Oxigénio
(grupo carbonilo) do aminoácido situado a quatro posições
à frente na sequência primária. A Figura 1.4 mostra
esquematicamente estas ligações. A Figura 1.5 mostra a
estrutura tridimensional da hélice-α. Nesta figura apenas
os átomos que participam na formação das pontes
Hidrogénio estão representados.
Figura 1.5
Hélice-α. Os átomos de Carbono e as
cadeias laterais não estão representados
para melhor claridade.
Ácido
Carboxilico
Amina
Amina
C
N
O
H
Cadeia Lateral
Ácido
Carboxilico
Figura 1.6
Folha-β. Nesta figura as cadeias laterais são representadas apenas por um átomo. Os terminais Amina
e Ácido Carboxilico estão identificados, ilustrando a orientação anti-paralela das cadeias.
22
A folha-β é formada por dois ou mais segmentos de cadeia
numa orientação paralela ou anti-paralela. Isto significa que
as cadeias estão paralelas, mas podem orientar-se no mesmo
sentido ou em sentidos opostos, ficando o extremo do grupo
C
amina de uma cadeia no sentido do grupo ácido carboxilico
da outra.
N
O
A Figura 1.6 mostra a estrutura de uma folha-β anti-paralela
H
formada por duas cadeias. Neste caso as pontes de
Hidrogénio são formadas entre aminoácidos que podem estar
Figura 1.7
Dobra-β. A ponte de Hidrogénio que
liga um aminoácido ao aminoácido três
posições adiante na sequência estabiliza
esta estrutura.
distantes na sequência, ou mesmo pertencerem a diferentes
cadeias.
O terceiro elemento da estrutura secundária é a dobra-β. Esta
estrutura forma uma curva apertada na cadeia da proteína, estabilizada pela presença de uma ponte de
Hidrogénio entre o Oxigénio do grupo Carbonilo de um aminoácido (este é o resultante do grupo ácido
carboxilico após a formação da ligação peptídica, como ilustrado na Figura 1.3, página 19) com um
átomo de Hidrogénio ligado ao Azoto do aminoácido três posições adiante na sequência. A Figura 1.7
ilustra este elemento da estrutura secundária.
Os elementos de estrutura secundária, pela sua estabilidade, conferem grande estabilidade estrutural às
proteínas. De certa forma pode-se dizer que sustentam a estrutura tridimensional da proteína. No entanto, as proteínas contêm também regiões que não participam na formação destas estruturas, e por
isso são potencialmente mais flexíveis. Este misto de rigidez e flexibilidade permite que as proteínas
possam ter uma vasta gama de formas, e mesmo mudar significativamente de forma por interacção
com outras moléculas. No entanto, as possibilidades quase ilimitadas de combinação destas estruturas
tornam a previsão da forma tridimensional uma tarefa muito complexa e de momento pouco fiável.
1.4 Estrutura Terciária
O termo Estrutura Terciária refere-se, formalmente, à relação espacial entre aminoácidos distantes na
sequência (33). Na prática, a fronteira entre estrutura secundária e terciária não é muito nítida (por
exemplo, uma folha-β contém relações espaciais entre aminoácidos distantes na sequência), mas podemos conceber a estrutura terciária como a forma tridimensional que uma cadeia de aminoácidos
toma, incluindo normalmente vários elementos de estrutura secundária.
A Figura 1.8 ilustra a estrutura terciária da quimotripsina (27). Esta representação salienta os diferentes elementos de estrutura secundária presentes na proteína. As setas amarelas representam as folhas-β,
indicando o sentido de cada segmento de cadeia. A vermelho estão representadas as hélices-α, com a
23
Figura 1.8
Representação estereoscópica da estrutura ternária da Quimotripsina. Os elementos da estrutura secundária estão representados com diferentes cores: Vermelho para hélices-α, amarelo para folhas-β e
azul para as dobras-β.
α, com a sua característica forma em espiral. As dobras-β estão representadas a azul, sendo os
segmentos a branco regiões sem estrutura secundária definida. A estrutura terciária é assim
determinada pela relação espacial entre todos estes elementos. O objectivo deste trabalho é a
determinação desta relação espacial entre átomos a partir de restrições às distâncias entre estes. Estas
restrições podem ser determinadas experimentalmente, como veremos adiante.
1.5 Estrutura Quaternária
Em muitos casos uma proteína é composta por mais que uma cadeia de aminoácidos. Nestas proteínas
Figura 1.9
Estrutura quaternária de duas proteínas. À direita a protease do vírus da imunodeficiência
humana, à esquerda a hemoglobina humana. As diferentes cadeias de aminoácidos estão
representadas em cores diferentes.
24
a relação espacial entre as várias cadeias é chamada estrutura quaternária. Na prática, as dificuldades à
determinação da estrutura quaternária são muito semelhantes ao caso da estrutura terciária, e no
âmbito deste trabalho não foi feita uma distinção explícita entre os dois casos. A Figura 1.9 mostra a
estrutura quaternária de duas proteínas: a protease do vírus da immunodeficiência humana (34) e a
hemoglobina humana(12).
1.6 Outros Elementos Estruturais
Nas secções anteriores mencionei alguns elementos que contribuem para a formação ou estabilização
das várias estruturas nas proteínas. Nesta secção irei detalhar um pouco mais três destes elementos
(33).
Pontes de Hidrogénio: As pontes de Hidrogénio formam-se entre dois átomos que partilham entre si
um átomo de Hidrogénio. Um exemplo é o dos grupos NH e CO na dobra-β. Neste caso o átomo de
Hidrogénio está fracamente ligado ao Azoto, podendo ser partilhado com o átomo de Oxigénio. Esta
partilha de ligações com o Hidrogénio força os átomos de Azoto e Oxigénio a aproximarem-se, efectivamente ligando-os. Neste caso o Azoto é o átomo dador, pois está covalentemente ligado ao Hidrogénio, e o Oxigénio é o receptor. Nas proteínas as pontes de Hidrogénio formam-se tipicamente entre
átomos de Azoto ou Oxigénio. Esta ligação é cerca de vinte vezes mais fraca do que as ligações covalentes, mas mesmo assim desempenha um papel importante na determinação da estrutura da proteína
devido ao seu elevado número, formando redes extensas em toda a proteína.
Pontes de Dissulfureto: A Cisteína é um aminoácido contendo um átomo de Enxofre que tem a capacapacidade de formar uma ligação covalente com o
Enxofre de outra Cisteína (ver Figura 1.3, página 13).
Esta ligação covalente entre os dois átomos de enxofre é
chamada
ponte
de
Dissulfureto,
permite
ligar
C
covalentemente duas cadeias de aminoácidos, ou uma
N
cadeia em regiões distantes na estrutura primária.
O
Fe
Grupos Prostéticos: Muitas proteínas contém mais que
aminoácidos. No caso da hemoglobina, por exemplo, é
um hemo contendo um átomo de Ferro (ilustrado na
Figura 1.10) que desempenha o papel crucial no transporte do Oxigénio. Nestes casos a estrutura química
Figura 1.10
Hemo da Hemoglobina humana. Os átomos de
Hidrogénio não estão representados
destes grupos deve ser considerada na determinação da
estrutura da proteína, bem como as suas ligações às
cadeias de aminoácidos que a formam.
25
1.7 Quiralidade
A quiralidade não é propriamente um elemento estrutural, mas sim uma característica de uma estrutura. A quiralidade foi definida por Kelvin (33) como:
"Eu designo qualquer figura geométrica, ou conjunto de pontos, como quiral, e digo que tem quiralidade, se a sua imagem num espelho plano, em condições ideais, não pode ser sobreposta de forma a
coincidir com o original."
Um exemplo de uma estrutura quiral é a mão. A mão direita é idêntica à imagem no espelho da mão
esquerda e vice-versa, mas ambas diferem da sua própria imagem no espelho. O termo quiral deriva
precisamente de cheir, palavra grega para mão.
Em geral, moléculas complexas como as proteínas, são quirais, ou seja, a imagem no espelho é diferente da estrutura. Além disso, normalmente partes da estrutura também têm quiralidade. Um exemplo
são os centros quirais nos aminoácidos, que conferem a estes últimos duas formas possíveis, designadas R e S (de rectus e sinister, latim para direita e esquerda). Em sistemas biológicos existe em geral
apenas uma das duas formas possíveis para cada aminoácido. As hélices-α, outro exemplo de uma
estrutura quiral dentro da proteína, também só existem em seres vivos numa das duas formas possíveis.
Não é necessária para este trabalho uma abordagem detalhada deste tema. O importante a ter em conta
é que as proteínas são estruturas quirais, por isso diferentes da sua imagem no espelho, mas em que
apenas uma das formas tem realidade biológica. Este factor é importante porque um conjunto de distâncias, mesmo que suficiente para determinar completamente a estrutura duma proteína, terá sempre
no mínimo duas soluções, uma das quais é a imagem do espelho da solução correcta. Mais adiante (2.7
adiante (2.7 Verificação da Quiralidade, Página 49)
irei referir como este problema foi resolvido.
Menor Energia α
1.8 Ressonância Magnética Nuclear
Um tratamento detalhado das técnicas de RMN estrutural estaria fora do âmbito desta dissertação. No
entanto, penso que é importante dar uma visão geral
Maior Energia β
dos princípios que permitem obter experimentalmente
as restrições necessárias para definir a estrutura de
uma proteína (14,4).
Muitos núcleos atómicos são dipolos magnéticos. O
mais importante destes, em bioquímica estrutural, é o
núcleo do Hidrogénio, composto apenas por um pro-
Campo Externo
Figura 1.11
Possíveis orientações para o vector de momento
magnético de um protão na presença de um campo externo.
26
protão.
Quando em presença de um campo magnético externo, o vector de momento magnético do protão
pode tomar uma de duas orientações, como mostrado na Figura 1.11. Para compreender este fenómeno
é preciso considerar que o protão está sujeito às leis da mecânica quântica. Por isso a sua energia está
quantizada, não podendo tomar valores arbitrários, o que apenas permite que este adopte uma de duas
orientações possíveis em relação ao eixo definido pelo vector do campo magnético externo (convencionarei este eixo como sendo o eixo z do sistema de coordenadas). Se a componente z do vector de
momento linear tiver o mesmo sentido que o campo magnético externo, o protão encontra-se num
nível de energia inferior (α). No caso oposto encontra-se no nível superior (β) devido à interacção
desfavorável com o campo magnético externo.
Além disto, pelo princípio de incerteza de Heisenberg, as componentes x, y, e z do vector de momento
magnético do protão não podem ser todas determinadas simultaneamente. A componente z é fixa pela
sua relação com a energia do sistema devido à presença do campo magnético externo, e por isso as
componentes x e y (no plano perpendicular ao vector do campo magnético externo) são indetermináveis.
Numa perspectiva clássica, podemos imaginar que o vector de momento magnético do protão gira em
torno do eixo formado pelo vector do campo magnético externo, descrevendo um cone no espaço,
como representado pela Figura 1.11. As componentes x e y do vector de momento magnético do protão estão assim a oscilar no plano perpendicular ao vector do campo magnético externo. Se aplicarmos
um outro campo magnético oscilatório com a mesma frequência e que oscile neste plano, este estará
em ressonância com as componentes x e y do vector de momento magnético do protão. Isto é conseguido irradiando a amostra com ondas de radiofrequência, cuja componente magnética oscila à frequência desejada.
Esta frequência de ressonância depende da diferença energética entre o nível α e o nível β, ou seja, da
magnitude do campo magnético no ponto onde o protão se encontra. Por sua vez o campo magnético
sentido pelo protão é resultado não só do campo magnético aplicado externamente mas também do
campo magnético gerado na vizinhança do protão pelo movimento dos electrões na molécula. Como
consequência a frequência de ressonância de um protão depende do ambiente químico em que este se
encontra, pelo que é normalmente possível identificar um protão e distingui-lo de outros na molécula.
Ao irradiar a amostra com radiação na frequência de ressonância, um protão no estado de energia mais
baixo (α na Figura 1.11) absorverá energia da radiação fornecida, passando para o estado de energia
mais alto. Por outro lado, um protão no estado mais energético (β na Figura 1.11) será estimulado a
emitir uma radiação do mesmo comprimento de onda e transitar assim para o nível inferior.
27
Se as populações nos estados α e β forem idênticas, nenhum efeito será observável. Felizmente existem muitos campos magnéticos oscilatórios, gerados pela oscilação térmica dos átomos da proteína,
cuja interacção com o protão permitem a transição entre estes dois níveis mesmo na ausência de radiação electromagnética externa. As populações no nível α e β encontram-se assim num equilíbrio térmico em que o nível α é mais populado que o nível β, e por isso é detectável uma absorção de radiação
na frequência de ressonância de cada protão.
Se a probabilidade de um protão transitar do nível β para o nível α for alterada, o equilíbrio entre as
duas populações será alterado, e a absorção total medida será diferente. É possível conseguir isto experimentalmente porque a oscilação de um protão irradiado na sua frequência de ressonância pode alterar
a probabilidade de transição dos protões na vizinhança; este é o efeito de Overhauser. Como as frequências de ressonância são geralmente diferentes para protões em posições diferentes, é possível
simultaneamente irradiar um protão e medir a absorção de outro protão.
Este é o princípio da RMN a duas dimensões,
e a Figura 1.12 mostra um espectro obtido
por esta técnica. Cada pico indica a variação
na
absorção
medida
à
frequência
de
ressonância de um protão quando outro
protão é irradiado. A intensidade destes picos
cruzados permite-nos calcular limites para a
distância entre os dois protões. Esta técnica
pode fornecer assim a informação necessária
para determinar a estrutura de uma proteína.
No entanto é evidente a complexidade dos
espectros obtidos por esta técnica quando
aplicada a proteínas. Por isso a tarefa de atribuir a cada pico o respectivo par de protões
está longe de ser trivial. Os átomos e os ami-
Figura 1.12
Espectro de NMR Bidimensional (Derivado de Níquel da Rubredoxina).
noácidos a que pertencem são identificados
identificados por padrões característicos. No entanto é comum haver ambiguidade na atribuição, como
por exemplo quando a proteína contém vários aminoácidos do mesmo tipo, caso em que pode ser
difícil distingui-los. Em geral as primeiras tentativas contêm atribuições erradas, ou muito
incompletas, e só tentando calcular a estrutura repetidas vezes é que é possível resolver estes
problemas. As atribuições provisórias são usadas para calcular uma estrutura, que por sua vez fornece
a informação sobre a vizinhança dos átomos que permite corrigir a atribuição. Este carácter iterativo
do processo torna particularmente importante a eficiência do cálculo da estrutura a partir das restrições.
28
29
30
2. Método
"Tudo deve ser feito tão simples quanto possível, mas não mais."
Albert Einstein
Para qualquer algoritmo existe um nível óptimo de complexidade. Tanto algoritmos demasiado complexos como demasiado simplificados sofrem degradação no desempenho e na qualidade dos resultados. A ideia central no desenvolvimento deste método foi precisamente tentar encontrar esse valor óptimo.
Assim, diversas simplificações foram feitas, nomeadamente a nível da modelação das restrições de
distância e da representação dos domínios. Outras simplificações, como a redução do problema a domínios finitos, pareceram à partida atraentes por terem sido usadas nem problemas relacionados, como
análise teórica de estruturas de proteínas (5), ou na atribuição de picos cruzados em NMR multidimensional (23,36). No entanto os resultados favoráveis obtidos com o presente método indicam que tal
simplificação é provavelmente excessiva no caso da determinação de estruturas.
A comparação de apenas dois métodos; a aplicação comercial DYANA (17) e o algoritmo aqui proposto, não permite concluir que este último está próximo do óptimo de desempenho. É evidente que
muitas alternativas ficam ainda por explorar. Este método é assim apenas um primeiro passo, mas que
cumpre já o objectivo de mostrar que as técnicas de programação por restrições são apropriadas para a
resolução deste problema.
2.1 Modelação do Problema
A informação acerca da estrutura a calcular é modelada pelo conjunto das
restrições de distância entre átomos e das variáveis de domínio representando as posições dos átomos que são consistentes com estas restrições
(2.3 Adaptação do Modelo, página 40). No modelo são considerados
todos os átomos excepto os átomos de Hidrogénio. Apesar de a informação de RNM a duas dimensões fornecer restrições às distâncias entre átomos 1H, estas são facilmente convertidas em restrições de distância entre
os átomos covalentemente ligados aos 1H, porque cada átomo de Hidrogénio está ligado a um e só um átomo. Isto permite reduzir para cerca de
metade o número de variáveis a considerar.
Figura 2.1
Algumas restrições
distância deduzidas
estrutura da Lisina.
de
da
De momento estão implementadas três fontes de restrições. A primeira é a
informação da estrutura primária (1.2 Estrutura Primária, Página16) da proteína. O conhecimento das
estruturas dos vários aminoácidos permite criar uma rede de restrições de distância entre pares de
31
átomos em qualquer um dos 20 aminoácidos. Estas restrições estão ilustradas na Figura 2.1. Como as
ligações químicas possuem alguma flexibilidade e algumas permitem a rotação em torno da ligação,
estas restrições de distância não representarão um valor único mas sim um intervalo de valores permitidos para a distância entre os átomos. Mais adiante (2.3 Adaptação do Modelo, Página 40) descreverei
como as restrições são implementadas para permitir esta modelação. Apesar de estas restrições constituírem cerca de metade das restrições usadas no cálculo de uma estrutura, não são por si só suficientes
para determinar o enrolamento da cadeia de aminoácidos, pois são restrições apenas dentro de aminoácidos e entre aminoácidos próximos na estrutura primária. Além disso são em grande parte restrições redundantes, pois o sistema de restrições gerado pela estrutura química de um aminoácido contém uma restrição para cada par de átomos diferentes no aminoácido. O uso de restrições redundantes
aumenta o desempenho na resolução do sistema pois permite a eliminação mais rápida de soluções
impossíveis quando não se garante uma consistência total (11). Esta é certamente uma técnica a
explorar de futuro, na sequência do trabalho aqui apresentado.
A segunda fonte de restrições é a informação de Ressonância Magnética Nuclear. A intensidade dos
picos cruzados permite estimar uma distância média entre os 1H em ressonância, que por sua vez permite criar um intervalo de distâncias permitidas entre os átomos ligados a estes átomos de Hidrogénio
(os átomos de Hidrogénio, como referido acima, não são incluídos no modelo). Estas restrições afectam muitas vezes aminoácidos em posições distantes na sequência da proteína, fornecendo por isso a
informação necessária para a determinação das estruturas de ordem superior (secundária, terciária e
quaternária, ver Estrutura de Proteínas, Página 15).
A terceira fonte de restrições é a própria estrutura a calcular. Obviamente, esta informação só pode ser
usada para testar o método, pois a estrutura tem que ser conhecida à partida. No entanto é extremamente simples medir numa estrutura as distâncias que se quer considerar e criar a partir destas as restrições necessárias. Este processo permite testar o método em qualquer uma das muitas estruturas disponíveis (normalmente determinadas por cristalografia de Raios X), sem exigir o acesso a dados experimentais de NMR. Além disto permitiu evitar inicialmente problemas de ambiguidade na atribuição
dos picos cruzados e de parametrização da conversão de distâncias entre 1H em restrições sobre os
átomos covalentemente ligados a estes. Sendo o objectivo principal deste trabalho estudar a aplicabilidade das técnicas de processamento de restrições à determinação de estruturas, foi bastante útil nesta
fase poder adiar a resolução destas pequenas dificuldades, avançando primeiro com o trabalho prioritário.
O sistema a resolver consiste assim num conjunto de variáveis correspondentes às posições dos átomos, e cujos valores se quer determinar, e um conjunto de restrições binárias (i.e. relações entre pares
de variáveis) de distância. Estas restrições permitem uma gama de valores e não apenas um valor único para a distância entre os dois átomos. A forma mais intuitiva de as modelar será como uma conjun-
32
conjunção de duas restrições: distância superior ou igual a um valor e distância inferior ou igual a
outro valor.
Relativamente a um átomo, um outro átomo terá que estar Fora de uma esfera com raio igual à distância mínima permitida pela restrição, e simultaneamente Dentro de outra esfera de raio igual à distância
máxima permitida. Esta será a designação usada para estas duas restrições, definidas analiticamente
como:
Dentro
( x1 − x 2 ) 2 + ( y1 − y 2 ) 2 + ( z1 − z 2 ) 2 ≤ k
Equação 2.1
Fora
( x1 − x2 ) 2 + ( y1 − y2 )2 + ( z1 − z2 )2 ≥ k
Equação 2.2
Estas restrições são suficientes para modelar toda a informação estrutural disponível à excepção da
quiralidade (1.7 Quiralidade, Página 25), que é considerada só após o cálculo da estrutura.
2.2 Técnicas de Consistência
O objectivo do método é gerar uma estrutura que respeite as restrições impostas. Essencialmente o
problema consiste em encontrar, num universo de inúmeras combinações de posições de átomos,
aquelas que cumprem o objectivo. Esta pesquisa pode ser imaginada como a exploração de uma
árvore. Cada ramificação corresponde à atribuição de valores a uma variável, com cada ramo
correspondendo a um valor específico para esta variável. Esta atribuição designa-se por enumeração,
sendo a solução final obtida quando todas as variáveis estão enumeradas. Como em cada ramificação é
escolhido um valor para uma variável, este momento no processo de procura é chamado ponto de
escolha. Durante a pesquisa vários pontos de escolha são criados, e possivelmente a execução terá que
retroceder a alguns destes para modificar a escolha feita.
A Figura 2.2 exemplifica esta pesquisa para o problema de colocar duas moedas de forma a que o número indicando o valor não seja visível. No inicio é desconhecida a posição de qualquer uma das
moedas. Na primeira ramificação é determinada a posição de uma moeda, e cada ramo corresponde a
um dos dois possíveis estados em que a moeda pode estar (enumeração). Para cada um destes, a
segunda moeda é enumerada. No total temos 22 possibilidades, que são examinadas uma a uma. Sempre que uma possibilidade incorrecta é descoberta, a pesquisa retrocede para a ramificação anterior,
escolhendo o ramo seguinte. Os números na Figura 2.2 indicam uma possível ordem de pesquisa, e as
letras indicam a ordem dos pontos de escolha gerados. Por exemplo, para passar da situação 2 para a
situação 3 é necessário retroceder até ao ponto de escolha B. Após todas as escolhas em B terem sido
exploradas, a execução retorna a A, onde será tomada a escolha 4, alternativa a 1.
33
2
?
B
3
1
?
?
A
5
?
C
4
6
Figura 2.2
Árvore de pesquisa para o problema de posicionar duas moedas de forma a que os números não sejam visíveis.
As setas azuis indicam o caminho na enumeração para a solução correcta.
Se em vez de duas moedas tivéssemos quatro dados de seis faces, teríamos 64 possibilidades. Generalizando, o número total de possibilidades será igual ao produto para todas as variáveis do número de
valores que cada variável pode tomar, ou seja uma complexidade para o pior caso de O(an), em que n
representa o número de variáveis e a a cardinalidade do domínio. É fácil ver que esta explosão combinatória faz com que na prática uma pesquisa ingénua não seja viável.
Para melhorar a eficiência podemos usar melhor a informação fornecida pelas restrições. Em vez de
usar as restrições apenas para testar as soluções enumeradas, a pesquisa pode ser guiada mantendo a
consistência das enumerações. No exemplo das moedas, temos uma restrição que impede que uma
face com o número esteja voltada para cima. Assim, na primeira ramificação da árvore de pesquisa
podemos logo eliminar o ramo superior (ver Figura 2.2), pois sabemos que nenhuma solução nesse
ramo poderá respeitar esta restrição. Se conseguirmos manter uma consistência completa com as restrições impostas, a árvore de pesquisa fica reduzida apenas às soluções que respeitam as restrições (o
caminho a azul na Figura 2.2). Mesmo que a consistência seja parcial podemos reduzir drasticamente
o número de hipóteses a enumerar, e por isso o tempo de pesquisa.
Em geral, o problema de satisfação de restrições é NP-completo. NP porque é possível para uma máquina não determinista resolver o problema em tempo polinomial, pois o número de operações
necessárias para verificar se uma solução está correcta é polinomial em relação aos dados do problema; mais formalmente, existe um polinómio p(n) que, para cada valor n da dimensão do problema, é
superior ao número de operações necessárias para determinar se uma solução é válida ou não (25).
NP-completo porque nenhum problema da classe NP pode ser mais difícil de resolver que um que o
problema de satisfação de restrições mais um factor polinomial; formalmente, um problema A é NPcompleto se e só se A for NP e para qualquer problema B∈NP exista uma função f calculável em
tempo polinomial tal que x∈B se e só se f(x)∈A. Este facto é importante, porque se algum algoritmo
resolver o problema geral de satisfação de restrições em tempo polinomial, todos os problemas NP são
34
problemas NP são de facto problemas P, ou seja, poderão ser resolvidos deterministicamente em
tempo polinomial.
A distinção entre P e NP merece ser clarificada; um problema ser NP quer dizer que, dada uma potencial solução, esta pode ser confirmada ou rejeitada em tempo polinomial. Isto nada diz acerca de como
encontrar a solução correcta. Como mostra o exemplo das moedas, o número de soluções potenciais
cresce exponencialmente com o número de variáveis, e mesmo que consigamos determinar em tempo
polinomial se as restrições são violadas, se enumerarmos todas as hipóteses podemos demorar um
tempo exponencial até encontrar a solução correcta. Se seleccionarmos as soluções de uma forma não
determinista, é possível acertar rapidamente na solução correcta, e assim resolver o problema em
tempo polinomial. Mas, se bem que possível, tal é em geral demasiado improvável.
O ideal seria conseguir um algoritmo determinista que garantisse que a solução correcta era encontrada em tempo polinomial. Tais algoritmos existem para alguns problemas NP. Por exemplo, virar todas
as moedas com o número para baixo é um algoritmo determinista que resolve o problema da Figura
da Figura 2.2 em tempo polinomial. No entanto este problema não é
NP completo, e por isso este algoritmo não terá sucesso idêntico no
caso geral. Desconhece-se ainda se é possível resolver todos os
A
B
problemas da classe NP de uma forma determinista em tempo
polinomial. No entanto, como vimos para o exemplo da Figura 2.2,
em muitos casos podemos resolver o problema em tempo útil de
uma forma determinista, se durante a pesquisa for mantida a
A≠B
A
consistência entre os valores das variáveis. Neste exemplo simples a
B ≠A
B
posição de cada moeda está restrita de uma forma independente da
Figura 2.3
posição da outra. Neste caso para garantir a consistência do sistema
Consistência de nó (grafo superior), no caso em que as moedas
não podem ter o número visível,
e de arco (grafo inferior), para o
caso que as faces visíveis têm
que ser diferentes.
basta considerar cada moeda individualmente. A isto chama-se
consistência de nó, em que cada variável é considerada
isoladamente quando eliminamos valores possíveis do seu domínio.
O nome deriva da representação do sistema de variáveis e restrições
como um grafo, em que os nós são as variáveis e os arcos são as
restrições. Temos também assim a noção de consistência de arco,
em que duas variáveis unidas por uma restrição são consideradas em
conjunto. Se, neste caso das moedas, a restrição fosse que não
poderiam ter a mesma face voltada para cima, só poderíamos cortar
Figura 2.4
ramos da árvore de pesquisa referentes à enumeração da segunda
Grafo representando o problema
das 3 moedas em posições diferentes. Cada arco representa uma
restrição, e cada elipse representa
uma moeda, com os dois valores
possíveis à partida.
moeda, e dependendo do valor da primeira. A Figura 2.3 ilustra os
dois tipos de restrições e consistência.
É importante não confundir, quando as restrições unem variáveis
35
duas a duas, a noção de consistência de arco (em que duas variáveis são consideradas) com consistência global. Vamos supor que temos três moedas, e queremos colocá-las de forma a que não haja duas
moedas com a mesma face voltada para cima. Tal problema é obviamente impossível. No entanto a
consistência de arco não permite chegar imediatamente a este resultado; só após enumerar a primeira
moeda, é que a consistência de arco permite remover essa orientação dos domínios das outras duas
moedas, e concluir a inconsistência (pois as duas restantes moedas teriam que ter a mesma orientação).
Nesse caso faltaria ainda escolher o outro valor possível para a primeira moeda, o que daria eventualmente o mesmo resultado. Só então é que o se poderia concluir que o problema não tem solução. A
Figura 2.4 representa o grafo deste problema.
Esta conclusão seria imediata se considerássemos as três moedas em simultâneo. Desta forma seria
logo evidente que três moedas com dois estados cada uma não podem estar todas em estados diferentes. Como este exemplo demonstra, mesmo um sistema em que as restrições se referem apenas a pares
de variáveis pode ser necessário considerar mais que duas variáveis em simultâneo para garantir uma
consistência completa. Isto é importante para o método que aqui proponho, no qual como veremos
adiante as restrições são modeladas como distâncias entre pares de átomos.
Se três variáveis são consideradas em simultâneo trata-se de consistência de caminho. Esta progressão
no número de variáveis consideradas simultaneamente quando se impõe consistência pode se estender
para qualquer valor. Por exemplo, se quisermos colocar sete dados de seis faces todos com uma face
diferente para cima, a consistência de caminho não garante consistência global, exigindo uma longa
pesquisa pela arvore. Para concluir que o problema é impossível seria necessário considerar as sete
variáveis em simultâneo. Podemos assim falar de consistência-k, em que k é o número de variáveis
consideradas quando a consistência é imposta. A consistência de nó será assim k=1, consistência de
arco k=2, e a consistência de caminho para k=3.
A manutenção de consistência k é tão mais exigente em termos computacionais quanto maior for k. A
complexidade temporal da consistência de nó é linear com a cardinalidade dos domínios (a) e o número de variáveis (n), ou seja O(an). No caso da consistência de arco, a complexidade temporal máxima é
de O(a3e) para o algoritmo AC-3 (26), em que e representa o número de restrições binárias no sistema.
Outros algoritmos para manter a consistência de arco têm desempenhos melhores; O(a2e) para o AC-4
(29) e AC-5 (20). O algoritmo AC-6 (9), se bem que com uma complexidade temporal idêntica no pior
dos casos, têm em média um desempenho melhor. Quanto à consistência de caminho, os algoritmos
PC-1 e PC-2 (26) tem complexidades no pior dos casos de respectivamente O(n5a5) e O(n3a5) em que n
representa o número de variáveis. O algoritmo PC-3 tem uma complexidade temporal O(n3a3) (29),
mas a sua complexidade espacial é também O(n3a3), o que para casos com um número significativo de
variáveis e valores pode ser proibitivo.
Geralmente não é garantida uma consistência completa, mas sim apenas consistência parcial, o que
torna necessária uma enumeração de muitas alternativas e o retrocesso na pesquisa sempre que são
36
descobertas enumerações inconsistentes. A manutenção de consistência permite reduzir a complexidade da pesquisa, que como vimos seria de O(an), para O(a’n nk), em que a’ é a cardinalidade dos domínios após redução por imposição de consistência. Como a’ é menor que a, consegue-se uma redução
no tempo de pesquisa, mas a um preço nk, em que n é o número de variáveis e k o nível de consistência. Por isso a consistência de arco é a mais usada na prática; os custos de manter uma consistência de
ordem maior, em geral, não são compensados pela redução na pesquisa.
Neste trabalho foi usada uma versão modificada do algoritmo AC-3 (26), mostrado na Figura 2.5 em
pseudo código. Este algoritmo é menos eficiente que as alternativas mais recentes. No entanto, trata-se
de um algoritmo geral, aplicável a qualquer domínio, ao passo que os algoritmos posteriores de
consistência de arco ganham eficiência especializando-se em problemas de domínios finitos. Recentemente foi criado um paradigma que sistematiza vários algoritmos de propagação de restrições (1). O
AC-3 foi o mais evoluído dos algoritmos de consistência de arco que foi possível incluir neste paradigma, precisamente pelo seu carácter geral. Como se discute adiante, foi escolhida uma modelação
por domínios contínuos, pelo que não foi possível tomar partido das técnicas dos algoritmos mais recentes.
procedimento REVER(Vi,Vj)
REMOVE <- falso;
para cada X em Di
se não existe Y in Dj tal que (X,Y) é consistente,
então
remover X de Di;
REMOVE <- verdadeiro;
fimse;
fimpara;
devolve REMOVE;
fim REVER
procedimento AC-3
Q <- {(Vi,Vj) em arcos(G),i≠j};
enquanto não Q vazio
selecciona e remove qualquer arco (Vk,Vm) de Q;
se REVER(Vk,Vm) então
Q <- Q união {(Vi,Vk) tal que (Vi,Vk) em arcos(G),i≠k,i≠m}
fimse
fimenquanto
fim AC-3
Figura 2.5
Representação em pseudo código do algoritmo AC-3
Este algoritmo é composto por um procedimento REVER, que elimina os valores do domínio de uma
variável Vi que não têm suporte na variável Vj. Este procedimento é chamado para todos os pares de
variáveis relacionadas por uma restrição (i.e. unidas por um arco pertencente ao grafo G). Quando o
procedimento REVER é chamado, o arco correspondente ao par seleccionado é removido da lista de
arcos a processar. Se o domínio de uma variável é alterado pelo procedimento REVER, todos os arcos
pertencentes a G e que tocam essa variável são adicionados à lista de arcos a processar. O procedimento termina quando esta lista estiver vazia.
37
Recapitulando, podemos reduzir a enumeração de soluções forçando durante a pesquisa alguma consistência com as restrições impostas. No entanto não é prático manter uma consistência completa, e
por isso muitas das escolhas feitas durante a enumeração podem resultar em inconsistência, exigindo
que se retroceda e altere uma escolha feita anteriormente. Assim torna-se também importante ter uma
boa heurística de enumeração, ou seja, um conjunto de regras de preferência que aumente a probabilidade de escolher o caminho certo quando existem várias hipóteses.
Para ilustrar isto, consideremos o problema de colocar três berlindes em três orifícios, como ilustrado
na Figura 2.6. As restrições impostas são que apenas um berlinde tem pode ocupar cada orifício, e que
o berlinde tem que caber no orifício. Consideremos que apenas é mantida consistência de arco da para
a primeira restrição (i.e. entre pares de berlindes, que têm que ocupar posições diferentes), e não se
mantém a consistência de nó para a segunda restrição (i.e. o berlinde tem que caber no orifício).
Figura 2.6
Enumeração para o problema de colocar 3 berlindes em três orifícios. O berlinde amarelo é colocado no primeiro
orifício. Por consistência de arco, este orifício não está disponível para o berlinde rosa, que é colocado no segundo orifício. Por fim o berlinde verde só pode ser colocado num orifício no qual não cabe.
Como se pode ver na Figura 2.6, o primeiro berlinde é colocado no primeiro orifício. Impondo consistência de arco à primeira restrição (posições diferentes), o segundo berlinde só poderá ser colocado em
um dos dois orifícios restantes, sendo colocado no segundo. Finalmente, o terceiro berlinde pode apenas ser colocado no terceiro orifício, mas ao completar a enumeração desta hipótese é verificada a violação da segunda restrição (o berlinde tem que caber no orifício), cuja consistência não foi mantida.
Assim torna-se necessário retroceder para explorar hipóteses alternativas. Mas retroceder um passo,
até à colocação do segundo berlinde, não é suficiente. De facto o erro foi feito logo na primeira opção,
quando o berlinde mais pequeno foi colocado no orifício maior.
38
Em situações reais pode ser muito grande o número de retrocessos e tentativas falhadas até que o erro
seja resolvido, pois este pode ter sido feito muito antes da inconsistência ser detectada. Por isso é muito importante ter uma heurística de escolha que minimize a probabilidade de erro e que cometa os
erros tanto quanto possível próximo da detecção das inconsistências. Para este exemplo, a heurística
de colocar cada berlinde no menor orifício em que este caiba resolveria este problema. É de salientar
que este exemplo simples não é realista, pois não haveria razão para não impor a consistência da
segunda restrição. A ideia importante é que, se não é garantida a consistência completa, é vantajoso
ordenar as enumerações de forma a encontrar o menor número de falhas.
Existem dois tipos de escolha durante a enumeração; qual a variável a enumerar, e qual o valor a atribuir-lhe. A ordenação das variáveis e dos valores pode ser estática, se for determinada no início da
execução, ou dinâmica, se depender do estado da pesquisa durante a execução (7). A heurística de falha primeiro é a mais comum para ordenação das variáveis. Baseia-se no principio que se detectará
uma falha mais cedo enumerando as variáveis com menores domínios. Parece contraditório procurar
uma falha, mas se uma solução parcial é incorrecta, é preferível detectá-lo antecipadamente, evitando
uma busca infrutífera nesse ramo da árvore. Outras heurísticas também têm o mesmo objectivo, como
escolher a variável que participa no maior número de restrições, ou que tem mais restrições com variáveis já enumeradas. Em todas estas heurísticas a ideia base é de tentar resolver primeiro os casos mais
difíceis, o que resulta numa redução média da profundidade dos ramos da árvore de pesquisa.
Quanto à ordenação dos valores, o efeito é ordenar os ramos explorados. Evidentemente nos casos em
que não existem soluções ou nos casos em que se quer enumerar todas as soluções a ordenação de valores é irrelevante. Mas de outra forma, uma ordenação ideal de valores pode produzir uma solução
sem necessidade de retrocesso. Neste caso a ideia base é a do sucede primeiro, ou seja, queremos
escolher o valor com maior probabilidade de ser o correcto. Isto pode ser conseguido, como no caso
do algoritmo AC-4, contando o suporte que cada valor tem e escolhendo o valor mais suportado. Em
alternativa, pode-se escolher o valor que simplificará ao máximo o problema a resolver.
No trabalho aqui apresentado, como veremos adiante (3.3 Heurística de Enumeração, página 55), foi
usada uma ordenação de variáveis por falha primeiro e uma ordenação de valores por sucede primeiro.
Todos os exemplos apresentados até agora referem-se a problemas em que as variáveis podem tomar
valores dentro de um domínio finito. Nestes casos manter a consistência consiste em retirar do domínio de uma variável aqueles valores que levariam necessariamente a uma violação das restrições. No
exemplo da Figura 2.6, ao colocar o primeiro berlinde, os domínios do segundo e do terceiro deixam
de conter o orifício ocupado. No entanto o problema que pretendo resolver não é necessariamente um
problema de domínios finitos. O objectivo é determinar a posição de cada átomo, e esta pode tomar
qualquer valor real, tendo assim um número infinito de valores possíveis.
39
Este problema poderia ter sido resolvido de duas formas. Uma opção seria considerar que cada átomo
ocuparia uma posição numa grelha tridimensional, resolvendo assim o problema com técnicas de domínios finitos. No entanto, mesmo usando uma grelha relativamente grosseira de por exemplo 0.5Å
para converter as posições em domínios finitos, teria cerca de 100 valores possíveis para cada coordenada. É fácil ver que com um número tão elevado de restrições e variáveis (na ordem dos milhares), o
problema seria na prática impossível de resolver. Mesmo com algoritmos de consistência como o AC6 ou o PC-3 a complexidade é respectivamente quadrática e cúbica com a cardinalidade dos domínios.
Optei por isso pela forma alternativa; considerar os domínios como contínuos, e neste caso não é viável remover do domínio das variáveis valores pontuais pois o domínio não é enumerável. O ponto de
partida para a representação dos domínios é a consistência de limite (bound consistency, 19).
Para exemplificar esta representação, consideremos o problema (Figura 2.7) de encontrar os valores
para duas variáveis reais X e Y de forma a que se respeite as duas restrições; X é metade de Y e Y é
igual a X. Supondo que se sabe à partida que a solução em ambos os casos se encontra no intervalo [10; 10], podemos restringir X ao intervalo [-5; 5], pois os valores de X não podem ultrapassar metade
dos de Y. Podemos então restringir Y ao mesmo intervalo, pois Y tem que ser igual a X. Segundo este
conceito, para efeitos de consistência são apenas testados os limites do intervalo de valores que forma
o domínio de uma variável. No entanto, para o problema específico que aqui pretendo resolver, é possível estender esta representação de forma a poder remover valores dentro do domínio. Essa represenrepresentação, baseada na consistência de limite mas
-10
X
0
-10
mais poderosa, será descrita na próxima secção.
Y
Este exemplo, além de ilustrar o conceito de consistên-
X = Y/2
Y=X
cia de limite, mostra também uma dificuldade em satisfazer restrições em domínios contínuos. O processo de
X = Y/2
Y=X
redução de domínios será repetido num ciclo infinito,
pois se bem estes reduzidos para metade a cada passo,
Figura 2.7
Redução progressiva dos domínios de X e
Y por imposição de consistência de limite.
nunca se chegará ao valor exacto que é solução do problema (ambas as variáveis iguais a zero). Em geral é
impossível obter em tempo finito valores exactos para
exactos para problemas em domínios reais. É por isso necessário fixar inicialmente um limite para a
precisão da solução obtida, para que o algoritmo pare em tempo finito quando este limite for atingido.
Outro problema desta opção é não poder recorrer aos algoritmos mais avançados de consistência PC-3
e AC-4, 5 e 6, pois estes baseiam-se na tabulação e contagem de valores suportados pelas restrições, e
no caso de domínios contínuos esta técnica não é aplicável. Foi necessário optar entre uma consistência de arco como o AC-3 e consistência de caminho como o algoritmo PC-2. O algoritmo AC-3 tem
uma complexidade temporal O(a3e), que é linear com o número de restrições, o que é vantajoso devido
40
vantajoso devido ao elevado número de restrições nos problemas que pretendo resolver. A
complexidade cúbica com a cardinalidade dos domínios não à partida um problema grave, pois a
cardinalidade efectiva, na prática, dependerá da precisão desejada, e por isso poderá ser controlada.
Uma consistência mais completa, como a consistência de caminho do algoritmo PC-2, não foi tentada
pois a sua complexidade de O(n3a5), sendo cúbica com o número de variáveis, é uma grande
desvantagem para estes problemas.
A concepção do método foi determinada por todas estas considerações. Em suma, sendo inviável
manter consistência completa, torna-se necessária uma pesquisa pelas possibilidades que a consistência parcial não elimina à partida. Esta pesquisa terá que ser guiada por uma heurística apropriada que
reduza o impacto das escolhas erradas na enumeração. Considerando os domínios como contínuos, o
processo de satisfação das restrições terá que ser interrompido quando todas as variáveis estiverem
restritas a intervalos aceitáveis, visto que não se podem obter valores exactos em tempo finito. Por último, o elevado número de variáveis e restrições nestes problemas limita o critério de consistência
usado a uma consistência de arco. A consistência de nó neste caso não tem qualquer utilidade devido à
natureza do problema, e critérios de consistência mais completos, se bem que possivelmente
vantajosos em subconjuntos de variáveis, dificilmente poderão ser aplicados em geral.
2.3 Adaptação do Modelo
Esta secção descreve os vários problemas de modelação e as soluções implementadas. Nomeadamente,
a escolha das variáveis, a modelação das restrições e domínios, e os métodos de propagação das restrições.
2.3.1 As variáveis usadas
Para resolver a estrutura é necessário determinar as coordenadas de cada átomo. Apesar da posição de
cada átomo estar definida por três variáveis (x, y e z), a modelação destas como variáveis separadas é
problemática, pois a restrição Fora é uma disjunção de três restrições sobre estas três variáveis
(Equação 2.2). Garantindo apenas consistência de arco não é possível propagar estas restrições, pois
em geral é possível encontrar suporte para todos os valores do domínio de cada variável. A Figura 2.8
ilustra melhor este problema num espaço bidimensional, em que um átomo cujo domínio abrange a
região a azul tem que ser excluído da proximidade do átomo na posição (x1, y1). Nenhum valor pode
ser removido dos domínios das variáveis x2 e y2.
41
y2
x1 , y1
a
b
c
x2
Figura 2.8
O átomo 1 no ponto (x1, y1) excluí, por uma restrição Fora, o átomo 2 da região marcada a rosa. Os domínios
das variáveis x2 e y2 abrangem a zona marcada a azul. Podemos ver que para qualquer valor (a, b ou c) de x2
existem valores possíveis para y2, sendo impossível reduzir o domínio de x2 impondo consistência de arco.
Como o recíproco também se verifica, também não é possível reduzir o domínio de y2. No entanto é evidente que
a zona marcada a branco devia ser removida do domínio do átomo 2.
Para resolver este problema as variáveis consideradas não são cada uma das três coordenadas de um
átomo, mas o ponto P(x, y, z) que representa a posição no espaço do centro geométrico do átomo.
2.3.2 Restrições e Domínios das Variáveis
Um outro problema é a propagação de restrições que definem volumes esféricos. O domínio de um
átomo sujeito a duas ou mais restrições Dentro será a intersecção das esferas definidas por estas restrições. No entanto, o cálculo e a representação destas intersecções, usando as restrições tal como definidas anteriormente (Equação 2.1 e Equação 2.2), é computacionalmente muito exigente. Por isso a
noção de distância foi simplificada, substituindo a distância Euclidiana, e definindo as restrições
como:
Dentro
max(| x1 − x2 | + | y1 − y2 | + | z1 − z2 |) ≤ k
Equação 2.3
Fora
| x1 − x2 |≥ αk ∨ | y1 − y2 |≥ αk ∨ | z1 − z2 |≥ αk
α= 1
3
Equação 2.4
A restrição Dentro será assim o cubo que contém a esfera de raio k e centro (x1, y1, z1), a restrição
Fora será o cubo contido nesta esfera. É necessário o parâmetro α para garantir que a restrição Fora
simplificada não excluí valores possíveis.
42
A Figura 2.9 ilustra esta simplificação para o caso a duas dimensões (note-se que a duas dimensões o
parâmetro α é igual a 1/√2).
Restrição
Dentro
Restrição
Fora
Distância
Euclidiana
Figura 2.9
Esta figura mostra, em duas dimensões, a diferença entre a definição Euclidiana de distância e a definição mais
simples usada. Note-se que a restrição Dentro contém o círculo definido pela distância Euclidiana e a restrição
Fora tem está contida neste.
Devido a esta simplificação, os domínios não são intersecções de esferas mas sim de paralelepípedos.
Como uma intersecção de paralelepípedos é também um paralelepípedo, evita-se o aumento na complexidade da representação e do cálculo dos domínios.
Como vimos atrás a noção de consistência de limite não permite remover valores no interior do domínio. Por isso é necessário estender a representação do domínio.
43
Região
Excluída
Região
Permitida
Figura 2.10
O domínio da posição de um átomo é representado por um conjunto de paralelepípedos definindo duas regiões.
A região Permitida, representada por um paralelepípedo, e a região Excluída, representada por zero ou mais paralelepípedos.
Assim, o domínio de uma variável de posição de um átomo será representado por um conjunto de um
ou mais paralelepípedos. Um paralelepípedo define a região onde o centro geométrico do átomo se
pode encontrar de forma a verificar todas as restrições Dentro que lhe foram impostas, e será
designado
z
região
Permitida.
Os
restantes
paralelepípedos definem a região onde o centro
Vértice
Maior
geométrico do átomo não pode estar por ter sido
y
excluído devido a restrições Fora. Esta região será
designada região Excluída, e é composta por zero ou
mais paralelepípedos, sem sobreposições e contidos na
0
região Permitida. Desta forma é possível remover
regiões internas ao domínio, o que não seria possível
x
Vértice
Menor
Figura 2.11
Representação de um paralelepípedo pelos
vértices Maior e Menor. Também estão
representados os três semi-eixos positivos
das coordenadas x, y e z.
apenas por consistência de limite.
Cada paralelepípedo é definido por dois pontos, correspondendo a dois vértices opostos do paralelepípedo. O
vértice Menor é o vértice com o menor valor nas três
coordenadas. O vértice Maior é o vértice oposto, com o
maior valor em cada uma das coordenadas. Esta repre-
coordenadas. Esta representação simplifica significativamente as operações de intersecção de
paralelepípedos, como se descreve adiante. A Figura 2.11 ilustra esta representação.
2.3.3 Propagação das Restrições
44
Cada tipo de restrição (Fora e Dentro) é propagado de forma diferente. As restrições do tipo Dentro
são propagadas por operações de intersecção entre paralelepípedos. A região Permitida de um átomo
A será a intersecção da sua região Permitida com a vizinhança da região Permitida do átomo B. A
vizinhança de B é o paralelepípedo que define a região Permitida de B, aumentado em todas as direcções de uma distância igual á distância que define a restrição (k na Equação 2.3). A vizinhança de B
define assim a região onde o átomo A pode estar sem violar a restrição Dentro que o relaciona com B,
como ilustra a Figura 2.12.
Após esta intersecção, todos os paralelepípedos que definem a região Excluída do átomo A são
intersectados com a nova região Permitida deste. Esta operação simplifica a região Excluída,
removendo quaisquer paralelepípedos desnecessários.
A intersecção de paralelepípedos é simples de calcular. O paralelepípedo resultante da intersecção terá
no vértice Menor (ver Figura 2.11) o valor máximo de cada coordenada dos vértices Menores dos
paralelepípedos a intersectar. O vértice Maior terá como coordenadas os valores mínimos das
coordenadas dos vértices Maiores. Se paralelepípedo resultante tiver no vértice Menor uma
coordenada com valor superior á correspondente no
vértice Menor, então a intersecção é vazia. Esta
Máximo dos
vértices Menores
operação está ilustrada na Figura 2.13 para o caso
semelhante a duas dimensões.
Mínimo dos
vértices Maiores
Uma restrição do tipo Fora é propagada acrescentando
ao conjunto de paralelepípedos que define a região ExIntersecção
cluída de um átomo A a zona de exclusão do átomo B.
A zona de exclusão de B é um paralelepípedo calculado
calculado a partir da
zona Permitida de B,
Região
Permitida
subtraindo
k
ao
Figura 2.13
Intersecção de dois rectângulos. O caso
tridimensional com paralelepípedos é
idêntico.
cada
coordenada do vértice Maior e somando a cada coordenada do
vértice Menor o valor de distância correspondente à restrição (αk na
Vizinhança
Figura 2.12
Cálculo da vizinhança de um
domínio
à
distância
k
(representação bidimensional).
Equação 2.4), gerando respectivamente os vértices Menor e Maior
da zona de exclusão. Mais uma vez, se o vértice Menor desta tiver
uma ou mais coordenadas com um valor superior à coordenada
respectiva no vértice Maior, a zona de exclusão é nula. A Figura
2.14 ilustra esta operação.
45
Uma vez adicionada a zona de exclusão de B à região
Zona de
Exclusão
Excluída de A, esta última é processada para garantir que
os paralelepípedos que a definem não se intersectam.
Região
Permitida
Esta é a operação mais complexa na propagação das restrições, mas facilita a determinação da falha na pesquisa
αk
da solução quando o volume da região Excluída iguala
ou ultrapassa o volume da região Permitida, e simplifica
a representação da zona Excluída reduzindo o número de
αk
paralelepípedos necessários para a representar. Isto é
conseguido com um processo iterativo em que primeiro
Figura 2.14
um bloco da zona excluída é expandido em todas as di-
Cálculo da zona de exclusão
de um domínio à distância αk
(representação bidimensional).
recções até ter a dimensão máxima possível enquanto
completamente contido na zona Excluída. Em seguida
este novo paralelepípedo é subtraído à zona Excluída. O
subtraído à zona Excluída. O processo é repetido até a zona Excluída estar vazia. A zona Excluída
simplificada é o conjunto destes paralelepípedos expandidos. A Figura 2.15 resume a propagação das
restrições Dentro e Fora.
Restrição Dentro
Domínio Original
de A
Novo
Domínio
de A
Restrição Fora
Região Permitida
de A
Região
Excluída
de A
Vizinhança de B
Adição à
Região
Excluída
de A
Zona de
Exclusão
de B
Figura 2.15
Propagação dos dois tipos de restrição. Para a restrição Dentro o domínio do átomo A é reduzido intersectando a
região Permitida deste com a vizinhança de B. No caso da restrição Fora a zona de exclusão de B intersectada
com a região Permitida de A é adicionada à região Excluída de A. Note-se são desprezadas as regiões onde a
região de exclusão de B intersecta com os paralelepípedos da região Excluída de A.
A propagação das restrições é feita de forma a garantir a consistência de arco. Isto é conseguido propagando as restrições de cada variável sempre que o domínio dessa variável é alterado. A Figura 2.16
mostra em pseudo código o algoritmo usado. Este é uma adaptação do AC-3, em que foi alterado o
procedimento REVER e a inicialização da lista de arcos Q.
46
procedimento REVER(Vi,Vj)
REMOVE <- falso;
propagar restrição(j,i);
se mudou Di então REMOVE <- verdadeiro;
devolve REMOVE;
fim REVER
procedimento AC-3
Q <- {(Vi,Vj) em arcos(G),i≠j, Dj alterado};
enquanto não Q vazio
selecciona e remove qualquer arco (Vk,Vm) de Q;
se REVER(Vk,Vm) então
Q <- Q união {(Vi,Vk) tal que (Vi,Vk) em arcos(G),i≠k,i≠m}
fimse
fimenquanto
fim AC-3
Figura 2.16
Representação em pseudo código do algoritmo utilizado para manter consistência. Este algoritmo é baseado no
AC-3 (26), mostrado na Figura 2.5.
No procedimento REVER já não são testados e removidos individualmente os valores do domínio que
não são suportados. Em substituição, é propagada a restrição de Vj em Vi da forma descrita acima,
conforme a restrição é Dentro ou Fora. Se o domínio Di sofre alteração devido a esta propagação, todos os arcos de restrições que partem de Vi são adicionados à lista Q.
A inicialização da lista Q incluí apenas os arcos de variáveis cujo domínio foi alterado, quer por enumeração quer na fase de inicialização do cálculo, como se descreve na secção seguinte.
A consistência de arco é mantida para todas as restrições colocadas explicitamente no grafo. Existe,
num entanto, um restrição que não é tratada explicitamente; a impossibilidade de colocar dois átomos
na mesma posição. O modelo que proponho usa exclusivamente restrições binárias, e a forma de processar esta restrição no modelo é convertê-la numa rede de restrições Fora unindo todos os pares de
átomos. O problema é que isto gera um número demasiado grande de restrições (da ordem do quadrado das variáveis) pelo que não é viável tratá-las explicitamente. Por isso estas restrições são propagadas apenas na enumeração de cada variável, não sendo mantida a consistência de arco para este caso.
2.4 Enumeração
Visto não ser mantida uma consistência completa, é necessário explorar as possibilidades de colocação
dos átomos. Esta exploração pode ser vista como uma pesquisa por uma árvore, em que cada nó corresponde à enumeração de uma variável (ver 2.2 Técnicas de Consistência). Como o domínio das
posições dos átomos não é discreto, não será dado um valor exacto à variável enumerada como no
exemplo da Figura 2.2. Se assim fosse, cada nó teria um número infinito de nós descendentes, o que
tornaria a pesquisa impossível. A enumeração consiste por isso em reduzir o domínio das variáveis até
se atingir a precisão desejada.
47
Em geral, quanto maior for a redução do domínio da variável em cada passo da enumeração, maior o
número de nós descendentes. Por outro lado, quanto menor for a redução do domínio, maior a profundidade da árvore de pesquisa para um dado valor de precisão final (ver Figura 2.17). Se não recorresse
à propagação das restrições, seria preferível reduzir a profundidade da árvore, o que reduziria o número de nós visitados. Mas como em cada nó são propagadas as consequências da respectiva redução do
domínio, quanto maior a profundidade da árvore maior é a capacidade de corte desta propagação.
Assim, optei por dividir o domínio de cada variável em duas partes iguais em cada passo de enumeração.
Figura 2.17
Para atingir a mesma precisão final, dividir o domínio em quatro partes (árvore da esquerda) gera mais descendentes por nó do que dividindo em duas partes (árvore da direita), mas produz uma árvore menos profunda.
O ciclo de enumeração consiste em:
1. Selecção de um átomo de acordo com a heurística de falha primeiro
2. Redução do domínio a metade. A metade é seleccionada de acordo com o princípio de
sucede primeiro.
3. Propagação das consequências da redução de domínio
Da selecção e redução de domínio excluem-se todos os átomos cuja posição esteja definida com a precisão desejada. Também se exclui provisoriamente qualquer átomo que tenha sido seleccionado para
enumeração num ciclo anterior, até que todos os átomos sejam seleccionados. Desta forma a selecção
para enumeração é feita em regime de rotatividade.
Assim o primeiro passo na enumeração consiste em seleccionar o átomo cujo domínio tenha o menor
volume, pois este corresponde á variável mais problemática. Isto corresponde á heurística de falha
primeiro, em que se tenta ordenar as variáveis de forma a detectar a falha o mais cedo possível.
O domínio é então dividido ao meio por um plano de corte perpendicular ao maior comprimento do
paralelepípedo que define a região Permitida. O novo domínio será uma a metade com menor sobreposição com domínios de outros átomos. Este é o princípio de sucede primeiro, pois este novo domínio terá menor probabilidade de causar violações de restrições.
Após esta redução do domínio de um átomo, as restrições são propagadas como descrito na secção
anterior até atingir um novo ponto fixo.
48
A razão para seguir um regime de rotatividade na enumeração é discutida adiante (3.3 Heurística de
Enumeração, página 55), mas a ideia fundamental é que ao seleccionar o átomo com menor domínio e
em seguida reduzir o domínio para metade, é quase certo que esse seja o átomo seleccionado em seguida. Isto equivale na prática a atribuir ao átomo imediatamente um domínio com a dimensão final
desejada, que foi uma opção rejeitada por reduzir os efeitos da propagação de restrições. Assim todos
os domínios são reduzidos uma vez antes que qualquer domínio seja seleccionado pela segunda vez.
A enumeração é aplicada apenas aos átomos cujo domínio não esteja suficientemente reduzido. Qualquer átomo cujo domínio se possa incluir num paralelepípedo de dimensões predefinidas (tipicamente
de 2.5Å, ver 3.6 Dimensão Final dos Domínios, página 64) considera-se completamente enumerado e
é por isso excluído deste processo.
A escolha do novo domínio também é discutida em mais detalhe adiante (3.3 Heurística de
Enumeração, página 55). A heurística implementada consiste em somar os volumes da intersecção da
região Permitida do átomo a enumerar com as regiões Permitidas dos outros átomos. É escolhida a
metade candidata cujo volume total seja inferior, reduzindo desta forma a probabilidade de dois
átomos serem colocados no mesmo volume.
Como descrito na secção anterior, uma vez seleccionado o novo domínio é propagada uma restrição
Fora a todos os átomos com os quais não exista já uma restrição Fora explícita. Trata-se aqui de uma
situação de compromisso; é importante propagar para todos os átomos a informação que um átomo já
está a ocupar um determinado volume. No entanto é demasiado dispendioso garantir consistência de
arco neste caso, e por isso estas restrições só são propagadas no passo de enumeração de cada átomo.
Finalmente, o átomo enumerado é marcado como alterado, e a lista de arcos Q no algoritmo de
consistência (Figura 2.16) é inicializada com todas as restrições em que este esteja envolvido.
2.5 Retrocesso
Como a consistência de arco não garante a consistência completa do sistema, a enumeração é falível.
Uma falha é descoberta sempre que o domínio de um átomo fica vazio, indicando que é impossível
colocar esse átomo respeitando as restrições e os domínios dos outros átomos. Assumindo que o sistema tem uma solução, isto indica que foi feita uma escolha errada durante a enumeração. É necessário
retroceder (Backtracking) na enumeração para corrigir esta decisão.
O retrocesso é feito repondo todos os valores dos domínios na altura da última enumeração. A última
enumeração é então repetida escolhendo a metade alternativa do domínio, que foi rejeitada da primeira
vez (como exposto em 2.4 Enumeração, a enumeração consiste em dividir o domínio em duas partes e
escolher uma para o novo domínio). Se um novo retrocesso é necessário e ambas as metades do domínio nesta enumeração foram testadas, então o retrocesso prossegue até uma enumeração anterior em
que ainda haja uma região alternativa para testar.
49
Se este retrocesso prossegue para além da primeira enumeração feita, o sistema é considerado impossível, pois nenhuma escolha permite a colocação de todos os átomos.
Se a qualquer momento não houver átomos para enumerar (por terem todos domínios de dimensões
inferiores ao mínimo predeterminado) o processo de enumeração é considerado completo e bem sucedido.
2.6 Minimização
Mesmo após terminada a enumeração, a posição de cada átomo ainda não está complemente determinada, sendo definida pelo domínio da respectiva variável de posição. Para obter uma estrutura definida, cada átomo é colocado no ponto central do seu domínio, e em seguida as posições de todos os
átomos são alteradas para minimizar a diferença entre a distância entre todos os pares de átomos unidos por restrições e a distância esperada para esses átomos. Esta distância esperada é o valor médio do
intervalo de distância definido por cada par de restrições Fora e Dentro.
Para isto foi usado o algoritmo de minimização multidimensional de Powell (como descrito em 30).
Este algoritmo consiste em minimizar cada variável (cada coordenada de cada átomo) independentemente das outras, percorrendo todas as variáveis. Este ciclo é repetido até que a diferença entre duas
estruturas consecutivas seja suficientemente pequena. A Figura 2.18 mostra em pseudo código o algoritmo de minimização.
procedimento MINIMIZA
repete
SOMA <- 0
para todos atomos Ai
para todas coordenadas Cj
C <- MINIMO(Cj, j)
SOMA <- SOMA + (C-Cj)^2
Cj <- C
fimpara
fimpara
ate SOMA < PRECISAO
fim MINIMIZA
Figura 2.18
Representação em pseudo código do algoritmo de minimização
A função MINIMO devolve o valor da coordenada Cj, ao longo da direcção j do vector de coordenadas, que minimiza as diferenças entre as distâncias ideais e as medidas para todas as restrições. Esta
função MINIMO é uma minimização linear pelo método da bissecção pela razão de ouro (30, Golden
Section Search in One Dimension, página 397).
50
2.7 Verificação da Quiralidade
A distância entre dois pontos numa estrutura é igual à distância entre as imagens desses pontos num
espelho. Assim, existem no mínimo duas soluções para um sistema possível de restrições de distância,
em que uma solução é a imagem espelhada da outra. Como já foi mencionado (ver 1.7 Quiralidade,
Página 25) apenas uma destas é desejável no caso de estruturas de proteínas.
Nesta fase de desenvolvimento e avaliação do método, a selecção entre as duas soluções foi sempre
feita por comparação com a estrutura alvo. A partir da solução produzida, a solução alternativa foi
criada invertendo o sinal de uma das coordenadas para cada átomo, e a solução mais semelhante à
solução alvo foi guardada. Este processo tem o mérito de ser extremamente simples de implementar, e
não distorce os resultados porque se uma estrutura for muito semelhante à estrutura alvo (o que aconteceu na maioria dos casos) a outra é forçosamente muito diferente, não havendo por isso o perigo de
estar artificialmente a melhorar os relutados obtidos com uma escolha tendenciosa.
Para uma futura aplicação a um caso real, este processo não poderá ser utilizado (não se conhece a
estrutura alvo). A solução neste caso será a análise da quiralidade dos centros quirais dos aminoácidos
ou de estruturas secundárias como as Hélices-α (ver 1.3 Estrutura Secundária., Página 20), que só
existem em sistemas biológicos numa das duas formas possíveis.
2.8 Discussão do Método
Nesta secção irei expor algumas das limitações e características inovadoras do método. Uma limitação
importante é o critério de consistência usado (2.2 Técnicas de Consistência), especialmente para o
caso particular da restrição que os átomos não se podem sobrepor. A modelação desta restrição como
uma rede de restrições Fora gera um número demasiado grande de restrições, pelo que nem é viável
manter a consistência de arco para este caso. No entanto é potencialmente viável garantir uma consistência mais completa. Este tipo de situação é conhecido como "todos diferentes" (all different). Uma
restrição que imponha que todas as variáveis sejam diferentes têm propriedades que podem ser exploradas de forma a melhorar a eficiência. O predicado Diffn (8) é exemplo de um algoritmo para garantir
que um conjunto de blocos tridimensionais pode ser acomodado num espaço limitado. O problema
para a implementação de um sistema semelhante neste trabalho é que estes algoritmos operam invariavelmente em domínios finitos, e tornam-se impraticáveis em domínios com cardinalidade muito elevada ou em problemas com muitas variáveis. A determinação de estruturas de proteínas é um problema precisamente com estas características e por isso, até à preparação deste documento, ainda não foi
explorada a implementação desta restrição global.
Outra limitação da presente implementação é o algoritmo de minimização. O problema principal é que
este algoritmo minimiza todas as restrições da mesma forma. No entanto as restrições associadas a
51
ligações covalentes são extremamente rígidas, e deviam ser tratadas como tal. O resultado é que este
algoritmo produz soluções com alguma distorção nas ligações químicas.
Por fim, uma potencial fraqueza do método é a heurística de ordenação de valores, descrita em 2.4
Enumeração, que dá prioridade, na divisão dos domínios, à metade que mais se afasta dos outros átomos. O maior defeito desta heurística é assumir que todos os átomos que ficarão próximos na estrutura
final têm no modelo uma restrição Dentro. Se assim for, ao maximizar a distância entre eles dentro
dos limites das restrições impostas, não se incorre em qualquer erro, pois estas restrições não permitem que os átomos se afastem demasiado. Mas em casos reais um grande número destas restrições
pode não estar incluída no modelo, o que em teoria é problemático. No entanto os testes feitos ao
método até ao momento indicam que na prática esta heurística é apropriada nos casos reais (ver 3.5
Dependência das Restrições, página 61, e 3.7 Outras Estruturas Testadas, página 70).
Este método tem duas características inovadoras. Em primeiro lugar, a sua natureza mista, que combina um algoritmo construtivo, utilizando técnicas de processamento de restrições, com um algoritmo
reparativo, a minimização final. Isto permite colmatar duas dificuldades complementares nestas técnicas; tipicamente, a maior dificuldade dos algoritmos construtivos em domínios contínuos será obter
soluções com grande precisão, enquanto que o problema nos algoritmos reparativos é essencialmente a
pesquisa pelo espaço de possibilidades. O método que proponho consiste numa redução inicial do
espaço de procura, seguida por uma minimização que aproveita esta informação como ponto de partida. Como descrevo no próximo capítulo (3.7 Comparação com DYANA, página 67), esta combinação
melhora consideravelmente o desempenho.
A outra inovação é a representação dos domínios, como descrito em 2.3 Adaptação do Modelo. Está
descrita na literatura uma representação alternativa para problemas em domínios contínuos (31). Nesta, um domínio é representado por uma árvore em que cada nó corresponde a um cubo (no caso tridimensional), e pode ter até oito descendentes, correspondendo cada um destes a um octante deste cubo.
Por isto esta forma de representar um domínio designa-se por Octree (Quadtree para o caso bidimensional). Como cada um dos descendentes corresponde por sua vez também a um cubo, esta representação permite, em teoria, uma precisão arbitrária, dependendo apenas da profundidade da árvore (as
regiões pertencentes ao domínio são aquelas representadas pelos nós folha).
A vantagem desta representação é a sua flexibilidade, pois permite representar qualquer forma no
espaço. No entanto, o seu carácter genérico não permite tomar partido de certas características do
domínio. No caso deste trabalho, devido às simplificações feitas às restrições de distância (ver 2.3
Adaptação do Modelo) o domínio pode ser representado exclusivamente por paralelepípedos. Desta
forma a representação é muito mais simples que pelo método das Octrees. Este assunto é discutido em
mais detalhe na secção 3.2 Representação dos Domínios (página 54).
52
3. Resultados
"Resultados! Homem, tenho imensos resultados. Já sei de milhares
de coisas que não funcionam."
Thomas A. Edison
A fase inicial deste trabalho foi essencialmente uma exploração de hipóteses alternativas, a grande
maioria das quais foi rejeitada antes mesmo do método estar delineado. Uma análise exaustiva desses
"rascunhos" não seria útil. Mas durante a fase intermédia em que o algoritmo implementado já conseguia resolver algumas estruturas, foi necessário optar entre várias alternativas como heurísticas de
enumeração ou valores de parâmetros. Este capítulo mostrará algumas das alternativas exploradas,
justificando as escolhas feitas com os resultados obtidos, e uma análise do desempenho do método
como descrito no capítulo anterior.
3.1 Estrutura de Teste
Para a maioria dos testes apresentados neste capítulo, a estrutura escolhida foi a cadeia de aminoácidos
de um monómero da Dessulforedoxina. Esta proteína bacteriana (Dessulfovibrio gigas) reunia três
vantagens. A estrutura é conhecida, determinada quer por cristalografia Raios-X (2) quer por
Ressonância Magnética Nuclear (16). É uma proteína pequena, o que facilitou a execução de múltiplos
testes, e é uma estrutura com a qual estou familiarizado, o que permitiu em muitas situações uma
rápida avaliação qualitativa dos resultados.
Cada monómero contem um grupo prostético (ver 1.6 Outros Elementos Estruturais, Página 24), que é
neste caso um átomo de Ferro. A presente implementação não modela ainda qualquer grupo prostético,
e por isso este átomo foi ignorado, considerando assim no modelo apenas a cadeia de aminoácidos de
um monómero.
Também foram ignorados os átomos de Hidrogénio, como descrito em 2.1 Modelação do Problema
(Página 30). A estrutura usada para teste consiste assim numa cadeia de 36 aminoácidos, com 261
átomos. A Figura 3.1 ilustra a estrutura da Dessulforedoxina e o monómero usado para teste.
As restrições usadas foram no total 4950 (2475 restrições Fora e 2475 restrições Dentro), sendo:
2404 restrições obtidas da estrutura conhecida de cada aminoácido.
1273 restrições Dentro entre todos os pares de átomos na estrutura que na proteína estão ligados a
átomos de Hidrogénio e que se encontram a uma distância inferior a 6Å. Este processo simula as restrições fornecidas por RMN num caso ideal, em que a interacção dos átomos de Hidrogénio permitia
detectar a proximidade destes. Num caso real a distância obtida entre átomos de Hidrogénio seria fa-
53
seria facilmente convertida numa distância máxima entre os átomos a que estes estão ligados, pois
cada átomo de Hidrogénio pode ligar-se apenas a um átomo. O valor de distância para cada uma destas
restrições é de 120% da distância medida na estrutura de Raios-X, previamente conhecida. Esta
margem adicional de 20% simula a incerteza na conversão da intensidade do pico cruzado em
distância.
1273 restrições Fora associadas às restrições Dentro obtidas por simulação dos dados de RMN. Devido à incerteza nos valores de distância obtidos na prática por RMN, seria em princípio arriscado impor
restrições de distância mínima com base nos dados experimentais. Por isso na presente implementação
estas restrições são consideradas como uma imposição explicita da restrição que os átomos não se
podem sobrepor, e não se considera assim que derivem directamente dos dados experimentais. A
justificação para impor explicitamente estas restrições é que os átomos com restrições Dentro terão,
em princípio, mais propensão para se sobrepor, pois estas restrições vão obrigar o algoritmo a manter
estes átomos em proximidade. No entanto, é importante salientar que os resultados com esta estrutura
de teste não suportam esta hipótese (ver 3.4 Sobreposição de Átomos). É possível que a heurística de
enumeração seja suficiente para resolver este potencial problema, pelo que a incorporação destas restrições será algo a estudar em mais detalhe no futuro. Para além disto, é teoricamente possível usar a
informação experimental para obter valores mínimos de distância e não apenas valores máximos. Se
na prática isto for viável, estas restrições virão também directamente dos dados experimentais.
Figura 3.1
À esquerda a estrutura da Dessulforedoxina. Os dois monómeros, na realidade idênticos, estão representados a
verde e azul. Cada monómero contém um átomo de Ferro, representado a vermelho. À direita a estrutura de teste, que consiste num monómero sem os átomos de Hidrogénio e sem o Ferro prostético. Esta estrutura contêm
261 átomos. A escala indicada é em Ångstrom.
54
Salvo especificação em contrário, todos os resultados apresentados foram calculados num processador
Pentium a 133MHz.
3.2 Representação dos Domínios
Como já foi mencionado (2.8 Discussão do Método, página 50), foi considerada uma forma alternativa
de representar os domínios das variáveis, utilizando as técnicas de Octrees (31) em vez da representação escolhida, por conjuntos de paralelepípedos. A diferença de desempenho entre estas alternativas
depende principalmente da complexidade das representações dos domínios das variáveis. Quanto mais
complexos estes forem, mais demoradas as operações de propagação de restrições.
Antes de apresentar as razões que me levaram a optar pela representação usada, descreverei primeiro
esta técnica de representação de domínios em árvore para o caso a duas dimensões (Quadtrees). Cada
nó da árvore representa uma quadrado no plano, e cada nó pode ter até quatro nós descendentes, correspondendo aos quatro quadrantes do quadrado. Å Figura 3.2 mostra a representação por este método
de uma região elíptica. Como se pode ver, é possível aproximar a uma precisão arbitrária qualquer região aumentando a árvore.
Figura 3.2
Três representações em árvore do domínio representado a laranja. O nó raiz corresponde ao quadrado maior. Os
nós a cinzento representam o domínio. Da esquerda para a direita aumenta a precisão da representação.
Esta capacidade de representar qualquer domínio com precisão arbitrária é por vezes muito importante, mas acarreta um custo na complexidade da representação. Como podemos ver na figura, para representar a região rectangular que contêm a elipse (árvore da direita) é necessária uma árvore com três
níveis e seis nós. Mesmo para representar uma região rectangular o problema poderia ser idêntico no
caso (muito provável) que a fronteira da região não coincidisse exactamente com as fronteiras entre as
regiões correspondentes aos nós.
Uma estimativa da complexidade da árvore necessária para representar os domínios das posições dos
átomos foi feita medindo as variações de volume destes domínios. Usando a estrutura de teste foi
55
gerado o histograma mostrado na Figura 3.3. Cada classe representa uma gama de volumes, e este gráfico mostra o número variações de volume dos domínios das variáveis para cada classe. Os valores
numéricos das classes são o logaritmo de base 8 dos volumes correspondentes, criando assim uma
divisão logarítmica de classes. Isto parece uma representação estranha, mas justifica-se se considerarmos que cada nó numa Octree tem um volume oito vezes menor que o nó anterior. Assim cada classe
no gráfico da Figura 3.3 representa um nível numa Octree, assumindo para simplificar que as divisões
de volumes seriam todas cúbicas, caso ideal para uma Octree. Esta premissa não é realista, mas dá nos
uma medida para a complexidade mínima da árvore que seria necessária para manter a mesma precisão que o método aqui implementado (2.3 Adaptação do Modelo, página 40).
A unidade usada foi a resolução da representação por paralelepípedos, por isso a classe 0 corresponde
a um volume de 10-6Å3, e cada classe seguinte a um volume 8 vezes maior que a classe anterior. No
entanto este valor é irrelevante, apenas determinando a posição do gráfico no eixo das abcissas.
Numero de ocorrências
10000
1000
100
10
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
Variação de Volume (Log 8)
Figura 3.3
Histograma da variação no volume dos domínios pela propagação de restrições. A escala das abcissas é logarítmica de base 8. Quadro A.1, Página 84
O que é relevante é a gama de valores que a variação de volume pode tomar, abrangendo 11 classes,
ou seja, 11 níveis de uma hipotética Octree com capacidade de representar esta gama de variações. Se
cada nó desta Octree tivesse apenas 2 nós filhos (de um máximo de 8), a representação teria 2048 nós.
É certo que nem todas as árvores usadas necessitariam de 11 níveis, mas a representação que proponho
para este método necessita em média de apenas 2 paralelepípedos por domínio, e é extremamente provável que o recurso a Octrees gerasse representações mais complexas. Por isso estes resultados dão
bastante confiança que, para este problema, a representação por paralelepípedos é uma escolha
apropriada.
56
3.3 Heurística de Enumeração
Como já foi descrito (ver 2.4 Enumeração, Página 46), para enumeração é seleccionado primeiro o
átomo com o domínio mais reduzido. Em seguida o domínio deste é dividido em duas partes semelhantes, e uma é seleccionada para ser o novo domínio. Nesta secção descreverei alguns dos resultados
que ajudaram a implementar as duas heurísticas; sucede primeiro para a ordenação de valores e falha
primeiro para a ordenação das variáveis.
3.3.1 Ordenação dos Valores
Se bem que a conceito de sucede primeiro seja de aplicação geral, a implementação da heurística de
escolha entre as duas partes do domínio seria forçosamente específica deste problema de determinação
de estruturas moleculares. Duas alternativas foram consideradas; ou escolher apenas pela ordem pela
qual as duas partes eram geradas, ou escolher em primeiro lugar a parte do domínio que menos ocupada por domínios de outros átomos.
A primeira alternativa consistia simplesmente em separar o domínio em dois domínios e escolher o
primeiro destes. Se eventualmente isto resultasse num sistema impossível, quando o programa voltasse
a esta escolha por retrocesso (ver 2.5 Retrocesso, Página 48) o segundo seria então escolhido. A ordem
de escolha, nesta alternativa, é irrelevante. Esta seria uma heurística por defeito caso nenhuma outra
heurística melhorasse consistentemente o desempenho.
Na segunda alternativa são somados os volumes das regiões Permitidas (ver 2.3 Adaptação do
Modelo, página 40) dos domínios de outras variáveis que intersectam cada uma das duas partes do
domínio da variável seleccionada, e é escolhida a parte cujo volume total das intersecções seja menor.
Isto tende a afastar os domínios dos átomos, colmatando de certa forma a deficiente propagação da
restrição implícita que proíbe as sobreposições. Tal como no caso alternativo, se a execução voltar por
retrocesso a esta escolha, a outra parte do domínio será então escolhida. Esta é uma implementação
específica para este problema da heurística de sucede primeiro, pois a região com menor probabilidade
de causar violações é a menos ocupada. Isto deve-se à propagação tardia das restrições Fora, que só
podem ser propagadas quando o domínio está suficientemente reduzido para gerar zonas de exclusão.
Ao manter os átomos afastados evita-se que, mais tarde, surjam conflitos que forcem o retrocesso.
A Figura 3.4 mostra o tempo medido para estruturas de tamanho variável entre 2 e 32 aminoácidos.
Estas estruturas foram geradas usando a parte inicial (terminal amina) da estrutura de teste (ver 3.1
Estrutura de Teste). Dois efeitos contribuem para a diferença de desempenho entre as duas heurísticas.
Para estruturas maiores, neste caso acima dos 32 aminoácidos, a heurística de escolha pela ordem de
geração resulta facilmente em enumerações inconsistentes, e o número excessivo de retrocessos impede, na prática, a resolução.
57
Para estruturas menores isto não é um problema, pois existem menos átomos e menos restrições; para
os casos com menos de 32 aminoácidos não houve diferença significativa entre o número de retrocessos. Neste caso o que reduz o desempenho da heurística de escolha por ordem de geração é o aumento
no número de paralelepípedos necessários para descrever os domínios. Evidentemente, a heurística de
escolher as regiões mais afastadas de outros domínios reduz substancialmente a propagação das restri-
Tempo (s)
ções Fora, o que por sua vez resulta em domínios formados por um número menor de paralelepípedos,
200
180
160
140
120
100
80
60
40
20
0
Escolha por ordem de geração
Escolha por sobreposição
de domínios
2
7
12
17
22
27
32
Numero de Aminoácidos
Figura 3.4
Este gráfico mostra o tempo de cálculo em função do número de aminoácidos para cada heurística. A diferença
no desempenho acentua-se com o aumento no tamanho da estrutura.
Quadro A.2, Página 84
A Figura 3.5 mostra como a heurística por ordem de geração produz invariavelmente um número maior de paralelepípedos por domínio.
Numero de Paralelepípedos
18
16
Escolha por ordem de geração
14
12
10
8
6
Escolha por sobreposição
de domínios
4
2
0
2
7
12
17
22
Numero de Aminoácidos
27
32
58
Figura 3.5
Este gráfico mostra o número médio de paralelepípedos nos domínios em função do tamanho da estrutura para as
duas heurísticas de enumeração. Quadro A.3, Página 85
A razão para esta diferença é os átomos ficarem em média mais afastados, tanto quanto as restrições
Dentro o permitem, no caso da escolha por sobreposição de domínios. Desta forma a propagação de
restrições Fora é menos frequente, o que reduz em média a dimensão das regiões Excluídas dos domínios. O tempo de cálculo é reduzido não só porque as restrições Fora tem que ser propagadas menos
vezes, mas também porque quanto mais simples forem os domínios mais rápida é a propagação das
restrições.
3.3.2 Ordenação das Variáveis
A escolha da variável mais restrita (first fail) é uma heurística clássica bem documentada na literatura
(32, 19), aplicável na generalidade dos problemas. Por isso as variáveis são escolhidas de acordo com
esta heurística. A implementação desta heurística consiste em seleccionar para enumeração a variável
com o menor domínio. No entanto esta enumeração é feita em regime de rotatividade, em que todos as
variáveis são enumeradas uma vez antes que qualquer variável seja enumerada segunda vez (ver 2.4
Enumeração, Página 46). As duas opções seriam assim a enumeração sequencial por falha primeiro,
em que seria permitido enumerar o mesmo átomo várias vezes consecutivas, ou uma enumeração por
rotatividade, em que um átomo enumerado ficaria excluído da enumeração até que todos os outros fossem enumerados uma vez. A Figura 3.6 mostra a comparação do desempenho das duas heurísticas
alternativas, em ambos os casos escolhendo na enumeração a parte do domínio menos ocupada por
domínios de outros átomos. O teste foi feito apenas para estruturas até 14 aminoácidos porque para
200
180
160
140
120
100
80
60
40
20
0
Enumeração
sequencial
Enumeração por
rotatividade
2
10
18
Numero de Aminoácidos
26
Numero de Paralelepípedos
Tempo (s)
tamanhos superiores uma enumeração sequencial demorava demasiado tempo.
45
40
35
30
25
20
15
10
Enumeração
sequencial
Enumeração por
rotatividade
5
0
2
10
18
26
Numero de Aminoácidos
Figura 3.6
Gráficos do tempo e número médio de paralelepípedos nos domínios em função do tamanho da estrutura para as
duas heurísticas de selecção de átomos para enumeração. Quadro A.4, Página 85
59
O tempo de cálculo para a enumeração sequencial é maior devido ao grande aumento na complexidade
dos domínios. Quando um átomo é enumerado o seu domínio diminui para metade, tornando muito
provável que esse átomo seja seleccionado diversas vezes consecutivas. Desta forma o domínio de um
átomo é drasticamente reduzido enquanto os domínios de outros átomos, na sua maioria, praticamente
constantes. As restrições Fora no átomo a ser enumerado são então propagadas a muitos outros átomos, aumentando o número de paralelepípedos que define a zona Excluída destes.
Na enumeração por rotatividade todos os domínios já estão significativamente reduzidos quando as
restrições Fora começam a ser propagadas. Assim muitos domínios já não intersectam com a zona de
exclusão do átomo enumerado, o que limita muito o aumento na complexidade dos domínios.
3.4 Sobreposição de Átomos
Numa estrutura molecular os átomos não se podem sobrepor. A heurística de escolha de domínios na
enumeração tem aqui um papel importante, tendendo a afastar os átomos o máximo permitido pelas
restrições como vimos em 3.3 Heurística de Enumeração. Também importante é o conjunto de restrições Fora que se incluem no modelo. Grande parte destas surge da informação estrutural dos vários
aminoácidos, disponível a priori, que permite que todos os átomos pertencentes ao mesmo aminoácido
estejam relacionados por restrições Fora e Dentro. Os valores de distância para estas restrições são
função da estrutura dos diferentes aminoácidos.
As restantes restrições Fora são impostas explicitamente associadas às restrições Dentro obtidas por
RMN (neste caso a partir de estruturas conhecidas, simulando os dados que poderiam ser obtidos por
RMN, como descrito em 3.1 Estrutura de Teste) ou de uma forma não explícita entre todos os átomos
que não estejam relacionados por qualquer restrição. Estas restrições têm a função exclusiva de impedir a sobreposição dos átomos que nem estão ligados covalentemente nem pertencem ao mesmo aminoácido, e os valores de distância para estas restrições são um parâmetro que tem que ser ajustado.
Nesta secção mostrarei os resultados que levaram à escolha de um valor de 1.5Å para a distância (αk
na Equação 2.4, Pág. 41) para este conjunto de restrições Fora. Os valores de distância para as
restantes restrições Fora foram obtidos directamente das estruturas dos aminoácidos e não foram
ajustados.
60
700
600
Tempo (s)
500
400
300
200
100
0
0
0.5
1
1.5
2
Distância (Angstrom)
2.5
3
Figura 3.7
Gráfico do tempo de cálculo para diferentes valores de distância para as restrições Fora impostas. Quadro A.5,
Página 86.
No modelo foi assumido o mesmo valor de distância para todas estas restrições Fora impostas para
impedir a sobreposição de átomos. Usando a estrutura de teste descrita atrás (3.1 Estrutura de Teste)
foi resolvido o sistema de restrições com diferentes valores de distância. A Figura 3.7 mostra o tempo
de cálculo em função do valor de distância.
Como se pode ver, o tempo de cálculo aumenta lentamente aproximadamente até um valor de cerca de
2Å, a partir do qual o aumento é mais acentuado.
Também foram avaliadas as soluções obtidas, comparando-as com a estrutura alvo. A diferença entre
estruturas de macro-moléculas é normalmente medida pela raíz quadrada da média dos quadrados das
distâncias (RMQD, em Inglês RMSD Root Mean Square Deviation) entre átomos equivalentes quando
as estruturas são sobrepostas. Se as estruturas forem exactamente iguais, as distâncias entre átomos
equivalentes serão todas nulas, e por isso o valor da RMQD será também nulo. Regra geral para
proteínas duas estruturas são consideradas bastante semelhantes se o valor de RMQD obtido para os
átomos Carbono e Azoto da cadeia principal da proteína (ver 1.2 Estrutura Primária, Página 16). A
Figura 3.8 mostra a qualidade das soluções obtidas em função do valor de distância para as restrições
em causa.
61
3.5
RMQD (Angstrom)
3.0
2.5
2.0
1.5
1.0
0.5
0.0
0
0.5
1
1.5
2
Distância (Angstrom)
2.5
3
Figura 3.8
Gráfico da Raíz da Média do Quadrado da Distância (RMQD) entre a cadeia principal da estrutura alvo e a solução calculada em função da distância para as restrições Fora impostas. Quadro A.5, Página 86.
A qualidade das soluções é óptima para valores até 1.5Å, e significativamente pior para valores superiores (se bem que com uma dependência algo errática). Para valores superiores a 1.5Å o modelo começa afastar-se da realidade química. Impor uma restrição de distância mínima entre os núcleos dos
átomos com um valor muito elevado vai inevitavelmente distorcer o modelo, pelo que é fácil compreender esta perda de qualidade para estes valores.
Mais complexo é o que se passa a valores inferiores. Os resultados apresentados na Figura 3.8 parecem indicar que este parâmetro é irrelevante para valores abaixo de 1.5Å. No entanto a qualidade das
soluções nesta gama de valores deve-se à abundância de restrições. Nestas condições a heurística de
redução de domínio usada na enumeração (ver 2.4 Enumeração, Página 46) e a minimização após a
resolução das restrições bastam para evitar sobreposições entre átomos. No entanto trata-se de uma
situação ideal que infelizmente não é representativa da realidade. É quase certo que numa aplicação
prática deste método o conjunto de restrições não contenha todas as restrições potencialmente detectáveis por RMN. Por isso o valor escolhido para parametrizar estas restrições foi de 1.5Å, por ser o valor
que torna o modelo menos dependente da abundância de restrições e por estar de acordo com a
realidade química.
Como descrito atrás (3.1 Estrutura de Teste), algumas destas restrições são impostas explicitamente
associadas a restrições Dentro obtidas por RMN (ou, neste caso, por simulação). Intuitivamente, átomos unidos por restrições Dentro terão maior probabilidade de sobreposição, e desta forma a restrição
Fora de 1.5Å é imposta explicitamente para contrariar esta tendência. No entanto, nesta estrutura de
teste, nenhuma diferença prática foi detectada entre impor ou não explicitamente estas restrições. É
possível que a heurística de enumeração e a optimização consigam resolver este problema sem que
isto seja necessário, mas no presente método decidi manter esta imposição explícita porque o reduzido
62
reduzido custo associado (cerca de 3% do tempo total, sendo menos de metade do número total de
restrições Fora. Ver adiante 3.6 Desempenho) é, a meu ver, compensado pela possibilidade deste
procedimento ser vantajoso em geral. Afinal, o efeito deste procedimento foi até ao momento testado
em apenas uma estrutura, o que não permite concluir com confiança que será inútil também em outros
casos.
3.5 Dependência das Restrições
A simulação de restrições experimentais (3.1 Estrutura de Teste) é útil para a parametrização do método, mas é essencial que o método seja capaz de lidar com sistemas em que o número de restrições entre átomos não ligados seja mais reduzido, pois são essas as condições que se observam na prática.
A Figura 3.9 mostra a qualidade das soluções obtidas quando algumas restrições foram removidas aleatoriamente. Cada restrição foi removida com uma probabilidade variável entre 10% e 80%, em múltiplos de 10%. O cálculo da estrutura foi repetido dez vezes para cada valor de probabilidade (para um
total de 80 pontos no gráfico), pois de cada vez diferentes restrições eram rejeitadas, e o número de
restrições rejeitadas também variava ligeiramente.
RMQD (Angstrom)
8
7
6
5
4
3
2
1
0
0%
20%
40%
60%
80%
100%
Restrições Removidas
Figura 3.9
Gráfico da Raíz da Média do Quadrado da Distância (RMQD) entre a cadeia principal da estrutura alvo e a solução calculada em função da fracção de restrições removidas. Quadro A.6, Página 86.
Como o gráfico mostra, a qualidade das soluções obtidas é muito sensível à remoção de algumas restrições críticas (pois mesmo removendo apenas 10% das restrições muitas soluções têm uma qualidade
inaceitável, com valores de RMQD significativamente superiores a 1Å), mas pouco sensível à remoção de alguns conjuntos grandes de restrições (mesmo para valores de 70% de restrições removidas,
algumas soluções tinham valores de RMQD próximos de 1Å).
63
Este resultado é compreensível, pois é natural que alguns conjuntos de restrições tenham um papel
crucial para definir a estrutura. Se for retirada alguma destas restrições a qualidade do resultado é inferior. À primeira vista é um resultado desanimador, pois sabemos que na prática não são conhecidas
todas as restrições que a RMN potencialmente fornece. Numa aplicação real uma fracção considerável
seria excluída à partida por limitações experimentais. Se esta exclusão for aleatória o resultado pode
ser desastroso. Mas esta condição não é inteiramente realista, pois a intensidade dos picos cruzados
(ver 1.8 Ressonância Magnética Nuclear, Página 25) é dependente da distância, sendo maior quanto
menor for a distância entre os átomos. Regra geral, podemos assumir que uma restrição terá mais
probabilidade de ser detectada experimentalmente quanto mais intenso for o pico cruzado obtido no
espectro de RMN, ou seja, quanto menor for a distância.
Isto significa que a exclusão de restrições que se espera na prática não é completamente aleatória. Se
bem que parcialmente aleatória, o factor mais importante para determinar se a restrição é detectada
será a distância entre os átomos. Para testar esta hipótese as restrições obtidas experimentalmente para
o dímero da Dessulforedoxina (16, dados cedidos por Brian Goodfellow) foram comparadas com as
restrições simuladas como descrito atrás (3.1 Estrutura de Teste). Chamo a atenção para o facto desta
estrutura ser diferente da estrutura de teste (trata-se do dímero, com as duas cadeias de aminoácidos), e
o número total de restrições ser maior.
Número de Restrições
1800
1600
Simulação
1400
Experimental
1200
1000
800
600
400
200
0
<3
3a4
4a5
5a6
Distâncias das restrições (Angstrom)
Figura 3.10
Histograma com o número de restrições obtidas por simulação e experimentalmente para quatro gamas de distância. Quadro A.7, Página 87.
A Figura 3.10 mostra esta comparação. Foram consideradas apenas restrições com distâncias até 6Å
de acordo com o método de simulação descrito em 3.1 Estrutura de Teste.
64
RMQD (Angstrom)
6
5
4
3
2
1
0
0%
20%
40%
60%
80%
100%
Restrições Removidas
Figura 3.11
Variação da qualidade da solução obtida em função da fracção de restrições removidas. Quadro A.8, Página 87.
Este resultado confirma a hipótese que as restrições de menor distância são na sua maioria detectáveis
experimentalmente. É por isso mais adequado simular uma situação real removendo restrições em função dos seus valores de distância do que duma forma aleatória. A Figura 3.11 mostra a variação na
qualidade da solução obtida em função da fracção de restrições removidas. Neste caso para cada ponto
foram removidas as restrições com distância superior a um valor de corte, aumentando-se a fracção
removida reduzindo o valor de corte.
Uma simulação mais realista consiste em retirar as restrições aleatoriamente, mas com uma probabilidade dependente da distância da restrição, reproduzindo a proporção verificada experimentalmente
RMDQ(A)
como se mostra na Figura 3.10.
10
9
8
7
6
5
4
3
2
1
0
Esperado experimentalmente
+ Desvio Padrão
Média
- Desvio Padrão
0%
20%
40%
60%
Restrições removidas
80%
100%
65
Figura 3.12
Qualidade da solução obtida em função da fracção de restrições usadas. Indica-se a média e a média a mais e a
menos um desvio padrão para os dez valores calculados a cada ponto. Quadro A.9, Página 87.
No gráfico mostra-se também a proporção de restrições disponíveis experimentalmente (16% das obtidas por simulação). Este pequeno número de restrições, quando seleccionadas aleatoriamente, gera
soluções de fraca qualidade. No entanto é de salientar que as restrições produzidas experimentalmente
não são aleatórias, pois a atribuição dos picos é revista até ser possível gerar uma estrutura suficientemente restrita. Além disso, apenas foram consideradas no modelo restrições entre átomos a menos de
6Å de distância (ver 3.1 Estrutura de Teste). Isto é uma aproximação apropriada para a maioria das
restrições, pois como mostra a Figura 3.11 as restrições entre átomos mais distantes são apenas uma
pequena fracção. Mas mesmo um número pequeno de restrições entre átomos a mais de 6Å de distância pode ser importante para restringir a estrutura. Por estas razões (por não ser aleatória a selecção e
por não se restringirem a restrições com menos de 6Å), as restrições de origem experimental podem
definir adequadamente a estrutura, como se mostra adiante (3.7 Outras Estruturas Testadas).
3.6 Dimensão Final dos Domínios
Como foi descrito anteriormente (ver 2.4 Enumeração, Página 46) a fase de processamento de restrições é terminada quando todos os domínios dos átomos têm uma dimensão suficientemente pequena,
sendo em seguida o resultado optimizado por minimização. O valor deste parâmetro (dimensão final
do domínio) determina o tempo de cálculo tanto para a fase de processamento de restrições, pois quanto menor for este valor mais prolongada será esta fase, como a fase de optimização, pois quanto maior
o valor mais longe de um mínimo local estará a estrutura a minimizar.
A parametrização deste valor será assim um compromisso entre os tempos de cálculo nas duas fases
(processamento de restrições e optimização), de forma a que o tempo total seja minimizado.
Um outro factor a considerar é a qualidade das soluções obtidas. Se a fase de propagação de restrições
for terminada prematuramente, ou seja, se este parâmetro de dimensão final tiver um valor muito elevado, a solução fornecida para optimização pode estar demasiado longe da estrutura correcta para que
o algoritmo de optimização consiga gerar uma estrutura aceitável. A Figura 3.13 mostra a variação do
tempo de cálculo e da qualidade da estrutura obtida em função deste parâmetro.
66
120
4.5
4.0
3.5
Tempo (s)
80
3.0
2.5
60
2.0
40
1.5
RMDQ (A)
RMDQ (A)
Tempo (s)
100
1.0
20
0.5
0
0.0
5.0
4.5
4.0
3.5
3.0
2.5
2.0
1.5
1.0
Diâmetro Final (A)
Figura 3.13
Variação da qualidade da solução obtida e do tempo total de cálculo em função da dimensão final dos domínios na fase de processamento de restrições. O gráfico mostra os resultados para três valores de distância para
as restrições Fora impostas para evitar sobreposição atómica. Quadro A.10, página 88.
O tempo de cálculo diminui, em geral, sempre que a dimensão final dos domínios é aumentada, mas a
partir de um valor de aproximadamente 3Å a qualidade da solução obtida é variável. O valor óptimo
para este parâmetro seria ligeiramente superior a 3Å, valor para o tempo de cálculo é menor para a
zona em que as soluções são de qualidade aceitável.
Esta análise foi feita apenas com uma estrutura, e é por isso arriscado generalizar estes resultados. Assim o valor escolhido foi 2.5Å. Isto aumenta a confiança nos resultados para o caso geral, apenas com
um custo acrescido de cerca de 15% do tempo de cálculo em relação ao valor de 3Å.
Uma parametrização mais rigorosa exigiria naturalmente a repetição desta análise para várias estruturas. No entanto a prioridade é aperfeiçoar o algoritmo de optimização, e só depois se justifica uma
determinação mais cuidada deste valor, pois este está dependente do algoritmo de minimização.
3.6 Desempenho
O tempo despendido nas várias operações durante o cálculo da estrutura teste foi determinado interrompendo a execução a cada 100ms e registando a fase corrente do programa. Como a periodicidade
desta interrupção e o tempo de execução em cada operação são ligeiramente variáveis (devido à execução concorrente de rotinas do sistema operativo), foi calculada a média para quatro execuções do
programa. A Figura 3.14 mostra esquematicamente a proporção do tempo de cálculo das fases principais em relação ao tempo total.
67
Escolha de
Domínio
Propagação Fora
não explícita
Partição do
Domínio
Optimização
Retrocesso
Propagação
Dentro
Propagação Fora
Tempo Total, incluindo representação gráfica da dimensão dos domínios e do progresso do cálculo,
gestão de memória e acesso a ficheiros.
Figura 3.14
Proporção do tempo de cálculo para várias fases em relação ao tempo total de 69.3 segundos. Para maior detalhe
ver Quadro A.11, página 88.
A característica mais saliente é a proporção total das várias fases de cálculo ser relativamente pequena
(cerca de metade do tempo total). Isto deve-se em parte aos processos como representação gráfica do
progresso, registo de estatísticas como as mostradas neste capítulo e as próprias rotinas de interrupção
e contagem do tempo despendido. Todos estes processos são supérfluos para o cálculo de estruturas,
estando apenas presentes nesta fase para auxiliar a avaliação do programa.
Pode-se ver também que o tempo despendido na optimização é muito reduzido (2.5%), o que indica
que este algoritmo pode ainda ser substancialmente melhorado sem perigo de aumentar significativamente o tempo total de cálculo.
A propagação das restrições Fora que não estão explicitamente incluídas no sistema de restrições (ver
3.4 Sobreposição de Átomos), é feita apenas na fase de enumeração, e ainda assim requer uma fracção
significativa do tempo de cálculo. Estas restrições foram propagadas em média, para esta estrutura (ver
3.1 Estrutura de Teste), 237 vezes para cada enumeração, um número próximo do total de 261 átomos
na estrutura. As restrições Fora explicitamente impostas no problema foram propagadas aproximadamente 9 vezes para cada átomo (total de 2475 restrições fora explícitas para 261 átomos). Assim, se
estas restrições não explícitas fossem propagadas da mesma forma que as restrições Fora explícitas, o
tempo de cálculo destas restrições seria cerca de 25 vezes maior que o presente tempo de cálculo para
as restrições Fora explícitas (são 237 propagações por átomo em vez de apenas 9) o que iria triplicar o
tempo total de cálculo. Além disso o tempo de propagação destas restrições não explícitas aumenta
numa progressão quadrática com o número de átomos, pois o número destas restrições por átomo é
aproximadamente igual ao número total de átomos. Assim estas restrições não são impostas explicitamente, mas sim propagadas apenas na enumeração de cada átomo.
Por último, é aparente que a fase de enumeração é responsável por uma fracção significativa, semelhante ao tempo total de propagação de restrições. Isto deve-se em parte à propagação das restrições
Fora não explícitas durante a enumeração e à escolha do novo domínio, mas cerca de metade do tempo de enumeração e oucupado a guardar o estado corrente de todos os átomos caso seja necessário re-
68
necessário repetir esta enumeração devido a um eventual retrocesso. Guardar simplesmente os
domínios de todos os átomos implicaria um uso excessivo de memória, pois tipicamente serão
guardados centenas de pontos de escolha (313 para o caso da estrutura de teste). Nesta implementação
o presente ponto de escolha é comparado com o anterior, e o ponto de escolha anterior é modificado
de forma a guardar apenas as diferenças entre o anterior e o presente, pois essa informação é suficiente
para reconstruir o estado do sistema a cada ponto de escolha. Desta forma o uso de memória é
reduzido para aproximadamente 5%, (1.1Mb para o cálculo da estrutura de teste usando este
processo), com um custo aceitável em tempo de execução (cerca de 5 segundos, 7% do tempo total,
para a estrutura de teste).
3.7 Comparação com DYANA
O método aqui proposto foi comparado com DYANA (17), a aplicação comercial usada de momento
no Departamento de Química da Faculdade de Ciências e Tecnologia para o cálculo de estruturas de
proteínas a partir de restrições de RMN. O método base desta aplicação é minimizar as violações às
restrições impostas. Uma estrutura inicial gerada aleatoriamente é minimizada por simulated
annealing, alterando iterativamente os ângulos de torção (ver 1.1 Ligação Covalente, Página 15) das
ligações químicas com liberdade de rotação. Estas são fundamentalmente as ligações C-C e C-N dos
átomos de cada aminoácido que formam a cadeia principal da proteína (a ligação peptídica entre
aminoácidos é considerada rígida. Ver 1.2 Estrutura Primária, Página 16), e algumas ligações nas
cadeias laterais de certos aminoácidos. Todos os outros ângulos de torção, todos os ângulos de flexão e
todos os comprimentos de ligação são considerados fixos, tendo cada aminoácido em média cerca de
três graus de liberdade.
Este método tem alguma tendência de convergir para mínimos locais distantes da estrutura que minimiza globalmente as violações às restrições impostas. Por isso numa aplicação típica 500 estruturas
são calculadas, sendo guardadas as 15 melhores (com valores menores para a violação das restrições).
Para comparar o desempenho do método aqui proposto com DYANA foi fornecida a este último a lista
de restrições (1273 restrições) obtidas simulando os dados ideais de RMN para a estrutura de teste (ver
3.1 Estrutura de Teste). Foram calculadas 500 estruturas com o programa DYANA, sendo guardadas
as 15 melhores.
Para produzir 15 estruturas com o método aqui proposto foi feito um retrocesso abrangendo entre 30%
e 70% dos pontos de escolha após o cálculo de cada estrutura, prosseguindo a enumeração e optimização do ponto de escolha resultante. O número exacto de pontos de escolha recuados durante este retrocesso foi escolhido aleatoriamente. Desta forma conseguiu-se uma amostragem do espaço de soluções
possíveis.
69
A Figura 3.15 mostra a comparação dos resultados obtidos. As estruturas calculadas com o programa
DYANA têm uma qualidade ligeiramente superior e abrangem um maior espaço de possibilidades
para as restrições impostas.
A diferença na qualidade das estruturas não é muito acentuada, como mostra o Quadro 3.1. Quando
comparadas com a estrutura alvo, as soluções mais parecidas têm valores muito semelhantes de
RMQD, e em ambos os casos inferiores a 1Å. Esta pequena diferença deve-se ao algoritmo de optimização usado no método aqui proposto. Este algoritmo é muito menos sofisticado que o DYANA, pois
não faz qualquer distinção entre restrições associadas a ligações químicas rígidas e restrições de distância entre átomos não ligados.
É mais acentuada a diferença na amostragem de soluções compatíveis com as restrições impostas. No
Quadro 3.1 pode se ver também que em média as soluções geradas pelo DYANA diferem entre si quase duas vezes mais que as soluções geradas pelo método aqui proposto. A principal causa desta deficiência é o algoritmo de minimização. Por um lado, tratando-se de uma minimização ‘gananciosa’, o
algoritmo converge para o mínimo local mais próximo, sem explorar outras alternativas.. Por outro
lado, a optimização é feita no sentidos de que todos os valores de distância estejam o mais próximo
possível dos valores médios para cada par de átomos unidos por uma restrição, o que vai forçar a convergência para um conjunto muito restrito de soluções.
Raiz da Média do Quadrado da Distância (RMQD) em Å
Melhor
DYANA
P.R.
Para a Estrutura Alvo
Média
Desvio Padrão
Dentro do Conjunto de Soluções
Média
Desvio Padrão
0.8
1.04
0.16
0.86
0.30
0.9
1.20
0.19
0.52
0.26
Quadro 3.1
Comparação dos resultados obtidos pelo programa DYANA com os obtidos pelo método de Programação por
Restrições (P.R.) aqui proposto. Os valores referem-se aos átomos da cadeia principal proteico.
Outro factor importante pode ser a forma implementada para gerar várias soluções, ou seja, retroceder
um número aleatório de pontos de escolha. É possível que esta não permita gerar soluções suficientemente diversas para explorar o espaço de estruturas consistentes com as restrições.
70
Estrutura Alvo
Estruturas obtidas com o método
proposto
Estruturas obtidas com DYANA
Figura 3.15
Comparação dos resultados obtidos pelo programa DYANA com os obtidos pelo método aqui proposto. No topo
é mostrada a estrutura alvo, de onde foram retiradas as restrições usadas. Nas figuras inferiores as estruturas calculadas são mostradas a azul, sobrepostas à estrutura alvo em cinzento.
A qualidade das soluções obtidas pelos dois métodos é também muito semelhante no que respeita à
violação das restrições impostas. Nas estruturas finais algumas restrições são violadas, se bem que a
magnitude das violações é desprezável. A Figura 3.16 mostra o número e a magnitude das violações às
restrições para os conjuntos de 15 soluções geradas. Como se pode ver todas as violações são significativamente inferiores a 1Å, que corresponde ao diâmetro de um átomo de Hidrogénio e a cerca de
metade do diâmetro de um átomo de Carbono, e por isso tratam-se de violações insignificantes à escala das estruturas proteicas .
Estes resultados reforçam a hipótese que a menor qualidade das soluções em relação ao DYANA
deve-se a uma deficiência do algoritmo de optimização implementado, pois aparentemente a componente de processamento de restrições é capaz de gerar estruturas adequadas.
A vantagem do método de Programação por Restrições é a grande eficiência com que soluções aproximadas podem ser geradas. As soluções obtidas pelo método aqui proposto, incluindo optimização,
fora calculadas em 8 minutos num PC com um processador Pentium a 133 MHz, enquanto que o cálculo no DYANA demorou mais de 6 horas num computador O2 com um processador R5000. Considerando a diferença de desempenho entre os computadores usados, o método aqui proposto representa
um aumento de cerca de cem vezes na velocidade de cálculo.
71
10000
P.R. - 8%
DYANA - 17%
1000
100
10
1
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Violação em Angstrom
Figura 3.16
Número de restrições violadas nas 15 soluções geradas em cada método em função da magnitude da violação
para os dois métodos (Programação por Restrições e DYANA). Note-se a escala logarítmica nas ordenadas. Indica-se também para cada método a percentagem total de restrições violadas.
3.7 Outras Estruturas Testadas
O método proposto neste trabalho foi também testado em três outras estruturas, com conjuntos de restrições obtidos em cada caso simulando as restrições potencialmente obtidas por RMN (ver 3.1
Estrutura de Teste). Além disso também foi feito um teste calculando a estrutura dimérica da
Dessulforedoxina a partir de restrições obtidas experimentalmente por RMN (16).
A Figura 3.17 mostra o resultado obtido para o cálculo da estrutura do Citocromo C de cavalo. As
restrições usadas foram obtidas a partir da estrutura conhecida da proteína (10), do modo descrito
anteriormente (ver 3.1 Estrutura de Teste). Nesta figura encontram-se representadas as 15 estruturas
geradas, a estrutura alvo e o grupo prostético desta proteína (ver 1.6 Outros Elementos Estruturais,
página 24). É de salientar que os grupos prostéticos não estão modelados na presente versão do
método, e por isso foi apenas considerada a cadeia de aminoácidos da proteína. Esta falha no modelo
degradou certamente a qualidade das estruturas obtidas, dado o papel estrutural importante que este
grupo tem na proteína.
72
Figura 3.17
Estruturas obtidas para o Citocromo C de cavalo (a azul) comparadas com a estrutura alvo (a cinzento). O grupo
prostético (hemo) está representado a vermelho. Qualidade média 6.8Å RMQD.
A Figura 3.18 mostra as 15 soluções obtidas para a estrutura de um inibidor proteico da Tripsina,
comparadas com a estrutura alvo conhecida (28). As restrições usadas foram obtidas a partir desta última.
Figura 3.18
Estruturas obtidas para o inibidor da Tripsina (a azul) comparadas com a estrutura alvo (a cinzento). Qualidade
média de 2.8Å RMQD.
73
Figura 3.19
Estruturas obtidas para o inibidor da Tripsina Pancreática (a azul) comparadas com a estrutura alvo (a cinzento).
Qualidade média de 3.9Å RMQD.
A Figura 3.19 mostra os resultados obtidos para outro inibidor proteico da Tripsina (Inibidor da Tripsina Pancreática Humana, 18) comparados com a estrutura alvo conhecida. De salientar neste caso a
região terminal da estrutura, à direita na figura, onde naturalmente as restrições são insuficientes para
que a estrutura seja correctamente determinada.
Figura 3.20
Estruturas obtidas para o dímero da Desulforedoxina (a azul) comparadas com a estrutura alvo (a cinzento). Qualidade média de 3.6 Å RMQD.
74
A Figura 3.20 mostra os resultados obtidos para o dímero da Desulforedoxina, comparados com a estrutura alvo conhecida (2). As restrições usadas para este teste foram obtidas experimentalmente por
RMN (16, dados cedidos pelo autor).
Para este teste foi necessário ignorar algumas restrições porque, na prática, alguns grupos de átomos
não são distinguíveis. Isto exige que o modelo inclua pseudo átomos imaginários no centro geométrico
destes grupos (solução adoptada no DYANA) ou que as restrições seja aplicadas, com modificação, a
todos os átomos do grupo. O presente modelo ainda não inclui estas características, o que certamente
afectou o resultado.
Nestes resultados é evidente que a qualidade das soluções obtidas é inferior ao caso da estrutura de
teste. Isto deve-se à incapacidade do algoritmo de optimização para minimizar satisfatoriamente
estruturas de maiores dimensões.
Como já foi descrito (ver 2.6 Minimização, página 49) este algoritmo simples minimiza todas as restrições indiscriminadamente. Desta forma a importante informação estrutural dada pela rigidez da
maioria das ligações químicas não é utilizada, não só aumentando muito o tempo de cálculo pelo
excessivo número de graus de liberdade, mas também gerando estruturas distorcidas por permitir
distorções irrealistas.
Citocromo C
Inibidor Tripsina
Número de Átomos
Número de Restrições
Tempo Total
Tempo de Processamento de Restrições
Inibidor Tripsina (Pancreático)
Tempo de Optimização
Desulforedoxina
Figura 3.21
Comparação entre as várias estruturas testadas. O número de restrições, o número de átomos e o tempo encontram-se a escalas diferentes, mas a mesma escala é usada para todos os tempos e entre os vários casos. Quadro
A.12, página 88.
É de notar que a proporção da fase de optimização nestes casos é sempre superior ao caso do cálculo
de uma única estrutura, como visto na Figura 3.14. O cálculo de múltiplas estruturas é feito por um
75
retrocesso parcial (entre 30% e 70% dos pontos de escolha), o que faz com que o tempo de processamento de restrições seja menor para as estruturas a partir da primeira.
Apesar de não ser satisfatória a qualidade das soluções geradas pelo método como presentemente implementado, estes resultados mostram que a programação por restrições permite gerar rapidamente
soluções aproximadas. Isto permite reduzir o espaço de pesquisa para o algoritmo de optimização, tornando desnecessária a geração de centenas de estruturas como no caso de um método que recorra apenas à optimização como o DYANA.
76
77
4. Conclusão
"A previsão é difícil, especialmente do futuro."
Niels Bohr
Penso que este trabalho cumpriu o objectivo, mostrando que a aplicação de técnicas de programação
por restrições pode aumentar significativamente o desempenho no cálculo de estruturas a partir de restrições de distância. No que respeita ao caso particular da determinação de estruturas proteicas por
RMN, será necessário um estudo mais aprofundado para poder garantir que o método aqui apresentado
é de facto superior aos métodos correntemente usados. Os resultados obtidos são promissores, indicando um aumento de cerca de cem vezes na velocidade de cálculo, mas dois pontos importantes ficaram em aberto.
Em primeiro lugar, as estruturas obtidas pelo método como implementado até ao momento são de qualidade inferior. O presente algoritmo de minimização não distingue as restrições provenientes da RMN
das restrições associadas às ligações covalentes. Sendo estas últimas muito mais rígidas que as primeiras, a minimização indiscriminada gera estruturas com distorções inaceitáveis. No entanto este problema será quase certamente de resolução trivial, requerendo apenas uma minimização que modele
estas características estruturais do problema.
Em segundo lugar há a salientar a falta de testes com sistemas impossíveis. Este é um ponto importante porque na prática a atribuição das restrições obtidas por NMR é um processo iterativo de tentativa e
erro, o que implica que o sistema de cálculo das estruturas seja capaz de gerar uma solução mesmo
que as restrições sejam incompatíveis. Esta solução será necessariamente errada, contendo violações
às restrições impostas, mas é indispensável para avaliar e rever as atribuições. Apesar de não ter testado esta situação, penso que o método que aqui proponho é suficientemente robusto para resolver estes
casos. Um método exclusivamente construtivo como os métodos de programação por restrições não
poderia dar qualquer solução neste caso, exigindo que o problema das atribuições erradas fosse resolvido de outra forma. No entanto o método aqui proposto é misto, e os algoritmos reparativos, como a
minimização na fase final, não têm dificuldade em gerar soluções parcialmente incorrectas. Por isso
estou proponho que este será também um problema de resolução fácil, exigindo apenas que a fase
construtiva de processamento das restrições seja interrompida se uma solução consistente não for
gerada dentro de um período pré estabelecido. Visto que o número de retrocessos (2.5 Retrocesso, página 48) foi sempre inferior a dez nos casos testados, penso que a imposição de um limite de cem ou
mil retrocessos pode distinguir com confiança os casos em que existem atribuições incompatíveis, e
este número de retrocessos não é suficiente para causar um impacto significativo no tempo de cálculo.
No que respeita ao uso de técnicas de processamento de restrições, existem ainda opções por explorar.
Como mencionei anteriormente (2.2 Técnicas de Consistência, página 32), nestes problemas não deve
78
ser vantajoso, em geral, aplicar critérios de consistência de ordem superior à consistência em arco.
Mas possivelmente haverá vantagem em aplicá-los de uma forma localizada. Por exemplo, o ângulo
entre duas ligações será uma restrição envolvendo três átomos. Esta restrição terciária é modelada
como uma rede de restrições binárias, e parte da informação não é usada se for mantida apenas a consistência de arco. Uma solução possível seria aplicar um critério de consistência mais completo a esse
grupo de átomos. O mesmo conceito pode ser estendido a ângulos diedros (quatro átomos), a centros
quirais ou elementos de estrutura secundária (que podem conter um número variável de átomos).
A implementação de técnicas de propagação de restrições globais também poderá ser útil para impedir
a sobreposição de átomos. No presente método, a restrição que átomos não se podem sobrepor é
propagada de uma forma muito incompleta (2.3 Adaptação do Modelo, página 40) porque a rede de
restrições binárias que a modelam é demasiado extensa para manter sequer consistência de arco. Mas
esta é um exemplo clássico de uma restrição global, e possivelmente pode ser propagada de uma
forma mais eficiente.
Penso que o método aqui apresentado é uma boa base para o cálculo e previsão de estruturas moleculares. Uma aplicação quase imediata será ao processamento de dados experimentais de RMN estrutural
de proteínas. Num âmbito mais geral, penso que terá também uma aplicação em previsão e determinação de estruturas de macro-moléculas. A flexibilidade do método base permite uma adaptação a outros
dados de análise estrutural, e permite o aproveitamento de informação mais teórica, como modelação
por homologia ou previsão de estruturas locais. A simplicidade com que o método permite integrar
informação experimental e previsão teórica poderá resultar numa contribuição significativa para a análise estrutural de macro-moléculas. Será este o sentido em que este trabalho irá continuar; após o aperfeiçoamento para o caso da resolução de estruturas proteicas por RMN, o objectivo será alargar a base
de informação usada e o âmbito da aplicação do método.
Se bem que a previsão, especialmente do futuro, seja difícil, penso que é promissora a aplicação de
técnicas de programação por restrições ao problema da análise estrutural de macro-moléculas.
79
Glossário
Cadeia Principal: Sequência de átomos formada pelos grupos Carboxilo e Amina de cada aminoácido, unidos pelo Carbono-α, e unidos entre si pela ligação peptídica.
Consistência de limite: Noção de consistência em que apenas são testados os limites do intervalo de
valores possíveis.
Consistência-k: Critério de consistência que elimina os valores dos domínios das variáveis que não
são suportados quando são consideradas k variáveis em simultâneo.
Domínio: Conjunto de valores que uma variável pode tomar.
Efeito de Overhauser: Influência de um núcleo em ressonância na absorção de outro núcleo vizinho.
Enumeração: Processo de escolha do valor para as variáveis. No caso de problemas em domínios
contínuos consiste geralmente em reduzir o domínio das variáveis.
Falha primeiro: Heurística de escolha da variável a enumerar. Segundo esta heurística é escolhida a
variável com o menor domínio, o que tende a antecipar a detecção de falhas.
Não determinista: Algoritmo em que as decisões são tomadas de forma imprevisível ou aleatória.
PC: Personal Computer. Computador pessoal.
Picos cruzados: Designação dos picos nos espectros de RMN a duas dimensões, obtidos para um par
de frequências.
Ponto de escolha: Instante da execução em que o domínio de uma variável é restrito rejeitando valores que são suportados pelo critério de consistência. No caso de falha a execução terá que voltar ao
ponto de escolha para optar pelos valores rejeitados.
Ressonância: Oscilação do vector de momento magnético de um núcleo em fase com a frequência da
radiação incidente.
RMN: Ressonância Magnética Nuclear. Técnica de espectroscopia baseada na detecção de transições
de um núcleo atómico com momento magnético não nulo imerso num campo magnético.
RMQD: Raiz Média do Quadrado da Distância entre os átomos correspondentes de duas estruturas
moleculares. O valor mínimo, obtido sobrepondo o melhor possível as duas estruturas, é usado como
medida da diferença entre as estruturas.
Sucede primeiro: Heurística de ordenação de valores a atribuir a uma variável. Consiste em seleccionar primeiro os valores com menor probabilidade de falha.
80
81
Bibliografia
1. Apt, K, The Rough Guide to Constraint Propagation, 1999, Lecture Notes in Computer Science,
1713, 1-23.
2. Archer M, Huber R, Tavares P, Moura I, Moura JJ, Carrondo MA, Sieker LC, LeGall J, Romao
MJ (1995). Crystal structure of desulforedoxin from Desulfovibrio gigas determined at 1.8 A resolution: a novel non-heme iron protein structure. J Mol Biol 1995 Sep 1;251(5):690-702
3. Asimov, I (1987)., Asimov’s new guide to science, Penguin Books.
4. Atkins, P. (1990), Physical Chemistry, 4ª ed., Oxford
5. Backofen, R, Constraint Techniques for Solving the Protein Structure Prediction Problem, CP98,
Lecture Notes in Computer Science 1520, Springer-Verlag, 72-86
6. Barták, R., Constraint Programming: In Pursuit of the Holy Grail, Proceedings of WDS99 (invited lecture), Prague, June 1999
7. Barták, R., On-Line Guide to Constraint Programming, 1998,
http://kti.ms.mff.cuni.cz/~bartak/constraints/index.html
8. Beldiceanu, N., Contejean, E., Introducing Global Constraints in CHIP. Mathl. Comp. Modelling,
Vol 20, No. 12, 97-123, 1994
9. Bessiére, C., Arc-consistency and arc consistency again. Artificial Intelligence, 65 (1994) 179-190
10. Bushnell, G. W., Louie, G. V., Brayer, G. D.High-Resolution Three-Dimensional Structure of
Horse Heart Cytochrome C. J.Mol.Biol. 214 pp. 585, 1990
11. Cheng, B., Choi, K., Lee, J., Wu, J., Increasing Constraint Propagation by Redundant Modeling:
an Experience Report. Constraints, V. 4, 167, 1999
12. Fermi, G., Perutz, M.F.,Shaanan, B.,Fourme, R., (1984) The Crystal Structure of Human Deoxyhaemoglobin at 1.74 Angströms Resolution, J.Mol.Biol., V. 175, 159
13. Gallaire, H., Logic Programming: Further Developments IEEE Symposium on Logic Programming, Boston, 1985
14. Gil, V., Geraldes, C., (1987) Ressonância Magnética Nuclear, Fundamentos, Métodos e Aplicações, Fundação Calouste Gulbenkian.
15. Gonçalves Ferreira, F.A., Nutrição Humana, 2ªEd., Fundação Calouste Gulbenkian, 1994
82
16. Goodfellow B:J, Rusnak F., Moura I., Domke T., Moura J.J.G., NMR determination of the global
structure of the 113Cd derivative of Desulforedoxin: Investigation of the Hydrogen bonding pattern at the metal center, Protein Sc.7, 928-937 (1998)
17. Güntert, P., Mumenthaler, C. & Wüthrich, K. (1997). Torsion angle dynamics for NMR structure
calculation with the new program DYANA. J. Mol. Biol. 273, 283-298.
18. Hecht, Szardenings, Collins, Shomburg, Three-dimensional structure of the complexes between
bovine chymotrypsinogen *A and two recombinant variants of human pancreatic secretory trypsin
inhibitor (*Kazal-Type), J. Mol. Biol., V.220, 711, 1991
19. Hentenryck, P., Constraint Satisfaction in Logic Programming, MIT Press, 1989
20. Hentenryck, P., Deville, Y., Teng, C. A generic arc-consistency algorithm and it specializations,
Artificial Intelligence 57 (1992) 291-321
21. Homer, S., Selman, A., Complexity Theory, ftp://ftp.cs.buffalo.edu/pub/tech-reports/91-04.ps.Z
22. Jaffar, J. & Lassez, J. Constraint Logic Programming ACM Symposium on Principles of Programming Languages, 1987
23. Leishman, S., Gray, PMD and Fothergill, JE, ASSASSIN: A Constraint Based Assignment System
for Protein 2D Nuclear Magnetic Resonance, Applications and Innovations in Expert Systems II,
(Proceedings of Expert Systems 94, Cambridge), ed. R.Milne and A.Montgomery, 263-280, December 1994
24. Lewin, B., Genes V, Oxford, 1994
25. Lopez-Ortiz, A., Cmputational Theory FAQ, University of New Brunswick, Canada.
http://www.cs.unb.ca/~alopez-o/comp-faq/faq.html
26. Mackworth, A., Freuder, E., The Complexity of Some Polynomial Network Constraint Satisfaction
Problems, Artificial Intelligence 25 (1985) 65-74
27. Marquart M.,Walter J.,Deisenhofer, J, Bode W.,Huber R.(1983) The Geometry of the Reactive Site
and of the Peptide Groups in Trypsin, Trypsinogen and its Complexes with Inhibitors, Acta Crystallogr., Sect. B, V. 39, 480
28. Marquart, Walter, Deisenhofer, Bode, Huber, The geometry of the reactive site and of the peptide
groups in trypsin, trypsinogen and its complexes with inhibitors, Acta Crystallogr., Sect. B, V.39,
480, 1983
83
29. Mohr, R., Henderson, T., Arc and Path Consistency Revisited, Artificial Intelligence 28 (1986)
225-233
30. Press, Vetterling, Teukolsky, Flannery, Numerical Recipes in C 2nd ed, Cambrige Univ. Press
1994
31. Sam-Haroud, D., Faltings, B., Consistency Techniques for Continuous Constraints, Constraints, V.
1, 85, 1996
32. SICStus Prolog User's Manual Swedish Institute of Computer Science, November 1997
33. Stryer. L, Biochemistry, 3ªEd., International Student Edition,. 1988
34. Tong, L.,Pav, S., Pargellis, C., DO, F., D.Lamarre, Aderson, P.C., (1993), Crystal Structure of
Human Immunodeficiency Virus (HIV) Type 2 Protease in Complex with a Reduced Amide Inhibitor and Comparison with HIV-1 Protease Structures, Proc. Nat. Acad. Sci. USA, V. 90, 8387
35. Tsang, E., Foundations of Constraint Satisfacition, Academic Press, 1993
36. Zimmerman, D.E., Kulikowski C.A., Montelione G.T., A constraint reasoning system for automating sequence-specific resonance assignments from multidimensional protein NMR spectra. Ismb
1993;1:447-55
84
85
Apêndice A: Quadros
Classe
0
1
2
3
4
5
6
7
8
9
10
11
12
13
Número
0
0
6
33
164
710
1192
1589
2976
4274
5616
1740
68
0
Quadro A.1
Dados para o gráfico da Figura 3.3, Página 55
Aminoácidos
2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
32
34
36
Tempo (Segundos) para cada heurística
Ordem de Geração
Sobreposição de Domínios
0.8
0.5
2.6
1.7
6.9
3.8
16.0
7.5
19.3
10.4
29.5
13.6
43.3
17.7
49.5
19.6
56.7
24.9
68.6
33.6
89.8
36.9
109.6
38.6
134.4
38.2
199.5
42.2
265.6
43.8
268.7
54.8
64.6
912.6
70.4
256.9
Quadro A.2
Dados para o gráfico da Figura 3.4, Página 57. Valores a negrito indicam execuções interrompidas.
86
Média de paralelepípedos por domínio para a heurística:
Aminoácidos
2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
32
34
36
Ordem de Geração
1.9
2.6
5.5
7.2
6.0
7.5
9.7
9.2
7.9
7.3
8.5
10.5
12.5
15.8
17.2
17.4
19.4
8.2
Sobreposição de Domínios
1.5
1.9
1.7
2.3
2.0
1.9
2.4
2.0
1.9
2.1
2.2
2.1
2.1
1.8
1.8
2.8
2.0
2.0
Quadro A.3
Dados para o gráfico da Figura 3.5 , Página 57. Valores a negrito indicam
execuções interrompidas.
Aminoácidos
2
4
6
8
10
12
14
16
18
20
22
24
26
28
Por rotatividade
Tempo(s) Nº Paral.
0.5
1.5
1.7
1.9
3.8
1.7
7.5
2.3
10.4
2.0
13.6
1.9
17.7
2.4
19.6
2.0
24.9
1.9
33.6
2.1
36.9
2.2
38.6
2.1
38.2
2.1
42.2
1.8
Em Série
Tempo (s) Nº Paral.
0.5
2.0
2.5
4.4
4.9
5.5
18.0
10.9
23.9
13.1
38.1
15.0
90.1
20.3
121.2
20.4
201.1
26.9
593.9
40.6
399.4
31.0
274.6
21.4
332.1
25.3
602.4
32.1
Quadro A.4
Dados para o gráfico da Figura 3.6, Página 58.
87
Distância (Å)
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
1.6
1.8
2.0
2.2
2.4
2.6
2.8
Tempo(s)
50
52
52
52
52
56
62
67
72
76
95
117
255
246
658
RMQD (Å)
0.9
0.9
0.9
0.9
0.9
0.9
0.9
0.9
0.9
1.1
1.1
1.9
0.9
2.3
2.9
Quadro A.5
Dados para o gráfico da Figura 3.7, Página 59 e para o
gráfico da Figura 3.8, Página 60
Probabilidade de remoção
10%
20%
30%
40%
RMQD (Å)
Removidas
RMQD (Å)
Removidas
RMQD (Å)
Removidas
RMQD (Å)
Removidas
1.05
1.49
1.68
2.13
2.15
2.43
3.66
4.29
4.43
4.94
9%
10%
10%
9%
10%
11%
10%
11%
9%
10%
0.82
1.15
1.18
2.22
2.36
2.66
2.83
3.28
4.61
7.59
21%
21%
19%
19%
21%
20%
19%
20%
21%
21%
1.36
1.73
1.77
1.91
2.01
2.16
2.38
2.40
3.47
4.34
30%
28%
30%
30%
29%
32%
30%
28%
29%
30%
1.54
1.62
1.76
2.07
2.65
3.05
3.63
3.67
3.83
5.13
40%
43%
40%
43%
39%
40%
42%
39%
39%
39%
Probabilidade de remoção
50%
60%
70%
80%
RMQD (Å)
Removidas
RMQD (Å)
Removidas
RMQD (Å)
Removidas
RMQD (Å)
Removidas
1.51
1.77
1.85
2.08
2.24
2.29
3.01
3.34
3.71
4.39
50%
50%
52%
50%
50%
49%
50%
52%
50%
50%
1.74
1.92
2.01
2.73
2.88
3.12
3.33
3.56
3.65
4.44
62%
60%
59%
60%
59%
59%
60%
60%
60%
60%
1.67
1.81
2.94
2.94
3.09
3.22
3.86
4.35
5.20
5.35
71%
71%
71%
73%
71%
71%
70%
68%
71%
69%
3.03
3.07
3.12
3.77
3.79
3.84
3.87
4.88
4.95
5.04
78%
81%
80%
79%
79%
79%
79%
83%
80%
79%
Quadro A.6
Dados para o gráfico da Figura 3.9, Página 62
88
Distância (A)
Simulação
<3
3a4
4a5
5a6
Experimental
90
326
1030
1642
86
185
149
96
Quadro A.7
Dados para o gráfico da Figura 3.10, Página 63.
Restrições
Removidas
RMQD
0%
11%
20%
29%
37%
45%
51%
60%
68%
74%
79%
83%
85%
87%
90%
0.9
2.1
1.5
1.5
2.6
1.6
1.9
3.5
3.8
3.4
3.2
3.2
5.1
5.2
7.3
Quadro A.8
Valores da RMQD (em Ångstrom) para o gráfico da Figura
3.11, Página 63.
Restrições
Removidas
0%
5%
10%
15%
20%
25%
30%
35%
40%
45%
50%
Média
RMQD (Å)
Desvio Padrão
1.2
2.0
3.2
2.9
2.7
3.1
2.5
3.0
3.6
3.7
3.3
0.0
0.7
1.7
1.4
1.1
0.9
1.0
1.0
1.4
1.2
1.0
Restrições
Removidas
Média
55%
60%
65%
70%
75%
80%
85%
90%
95%
100%
4.2
3.8
3.9
3.8
4.6
4.2
4.4
6.1
12.7
38.0
RMQD (Å)
Desvio Padrão
Quadro A.9
Valores da RMQD (em Ångstrom) para o gráfico da Figura
3.12, Página64.
0.8
0.9
1.2
1.2
0.8
0.8
0.8
1.4
4.9
0.0
89
Dimensão Final (Å)
5.0
4.9
4.8
4.7
4.6
4.5
4.4
4.3
4.2
4.1
4.0
3.9
3.8
3.7
3.6
3.5
3.4
3.3
RMQD (Å)
1.49
1.50
1.50
1.48
1.52
1.52
0.71
3.48
3.57
3.59
4.04
4.13
3.90
4.01
4.26
3.78
3.90
3.91
Tempo (s) Dimensão Final (Å)
41.7
3.2
43.0
3.1
43.3
3.0
43.0
2.9
44.0
2.8
42.8
2.7
43.2
2.6
43.9
2.5
49.0
2.4
44.1
2.3
44.6
2.2
48.1
2.1
48.1
2.0
49.2
1.9
45.9
1.8
46.1
1.7
49.9
1.6
46.9
1.5
RMQD (Å) Tempo (s)
0.93
46.7
1.03
47.8
0.93
48.9
0.99
65.2
1.02
66.1
0.98
66.8
0.96
68.4
0.92
69.3
0.98
72.1
0.92
75.6
0.97
76.0
0.94
80.4
1.00
79.4
0.98
83.6
0.94
87.0
0.94
90.5
0.93
92.2
0.94
96.8
Quadro A.10
Valores de RMQD (em Ångstrom) e tempo (em segundos) para o gráfico da Figura 3.13, página
65.
Partição
Tempo (s)
Fracção
Tempo (s)
Fracção
10.3
14.9%
Simplificação
de Dominio
0.1
0.2%
Propagação
não explícita
3.6
5.2%
Retrocesso
Escolha de
Domínio
1.6
2.3%
Minimização
Propagação Fora
8.6
12.4%
Outros
Propagação
Dentro
9.9
14.3%
Total
0.1
0.1%
1.8
2.5%
33.4
48.1%
69.3
Quadro A.11
Proporções e tempos (em segundos) para as várias fases de cálculo apresentadas na Figura
3.14, página 66.
Tempo (Segundos) para 15 soluções
Processamento de
Optimização
Total
Restrições
Citocromo C
2289
413
3187
Inibidor
733
196
1114
Inibidor (Pancreático)
782
185
1154
Desulforedoxina
958
171
1305
Átomos
826
443
457
522
Restrições
18238
9098
9904
6440
Quadro A.12
Tempos de cálculo (em segundos), número de átomos e de restrições para os casos apresentados
na Figura 3.21, página73.