ads:
Laborat´orio Nacional de Computa¸c˜ao Cient´ıfica
Programa de P´os Gradua¸c˜ao em Modelagem Computacional
Resolu¸c˜ao de Estruturas de Prote´ınas Utilizando-se
Dados de RMN a partir de um Algoritmo Gen´etico de
M´ultiplos M´ınimos
Por
Marx Gomes Van der Linden
PETR
´
OPOLIS, RJ - BRASIL
JUNHO DE 2009
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
RESOLU ¸C
˜
AO DE ESTRUTURAS DE PROTE
´
INAS
UTILIZANDO-SE DADOS DE RMN A PARTIR DE UM
ALGORITMO GEN
´
ETICO DE M
´
ULTIPLOS M
´
INIMOS
Marx Gomes Van der Linden
DISSERTA¸C
˜
AO SUBMETIDA AO CORPO DOCENTE DO LABORAT
´
ORIO
NACIONAL DE COMPUTA¸C
˜
AO CIENT
´
IFICA COMO PARTE DOS REQUI-
SITOS NECESS
´
ARIOS PARA A OBTEN ¸C
˜
AO DO GRAU DE MESTRE EM
MODELAGEM COMPUTACIONAL
Aprovada por:
Prof. Laurent Emmanuel Dardenne, D.Sc
(Presidente)
Prof. Helio Jos´e Correa Barbosa, D.Sc.
Prof. Fabio Ceneviva Lacerda Almeida, D.Sc.
Prof. Paulo Mascarello Bisch, Ph.D
Prof. Ernesto Ra´ul Caffarena, D.Sc.
PETR
´
OPOLIS, RJ - BRASIL
JUNHO DE 2009
ads:
Linden, Marx Gomes Van der
L744r Resolu¸c˜ao de estruturas de prote´ınas utilizando-se dados de rmn a partir
de um algoritmo gen´etico de m´ultiplos m´ınimos / Marx Gomes Van der Linden.
Petrop´olis, RJ. : Laborat´orio Nacional de Computa¸c˜ao Cient´ıfica, 2009.
xxi, 124 p. : il.; 29 cm
Orientadore(s): Laurent Emmanuel Dardenne e Helio Jos´e Correa Barbosa
Disserta¸c˜ao (M.Sc.) – Laborat´orio Nacional de Computa¸c˜ao Cient´ıfica,
2009.
1. Prote´ınas - Estrutura. 2. Algoritmos gen´eticos. 3. Ressonˆancia
Magn´etica Nuclear I. Emmanuel Dardenne, Laurent. II. LNCC/MCT. III.
T´ıtulo.
CDD 572.633
A frase mais empolgante de se ouvir nas
ciˆencias, aquela que anuncia as novas
descobertas, n˜ao ´e “Eureka! ” (Encontrei!),
mas “Que estranho...”
Isaac Asimov (1920 - 1992)
iv
Dedicat´oria
A Tatiana e `a minha fam´ılia.
v
Agradecimentos
A Tatiana, pelo amor que supera o tempo e a distˆancia.
A meus pais, pela dedica¸c˜ao e carinho recebidos durante toda a minha vida
e pelo apoio a meus estudos e projetos.
Ao prof. Laurent, meu orientador, pela confian¸ca e pelo suporte e aux´ılio
dispensados desde o in´ıcio de minha jornada pela Modelagem Computacional; ao
prof. H´elio, co-orientador, pela valiosa experiˆencia em Algoritmos Gen´eticos com-
partilhada por meio de aulas e conversas pessoais.
Ao F´abio, pelas tardes de conversa sobre a vida, o universo e tudo o mais, e
pela inestim´avel ajuda nas quest˜oes mais dif´ıceis da implementa¸c˜ao do projeto.
Aos amigos que compartilharam comigo os dois anos mais at´ıpicos de minha
vida: Arthur, Daniel, Leonardo, Pablo, Priscila, Tha´ıs, Vin´ıcius e muitos outros
que me ajudaram a torn´a-los mais agrad´aveis.
Ao Programa de P´os-Gradu¸c˜ao em Modelagem Computacional (LNCC) e
aos seus funcion´arios.
`
A CAPES pelo financiamento.
vi
Resumo da Disserta¸c˜ao apresentada ao LNCC/MCT como parte dos requisitos
necess´arios para a obten¸c˜ao do grau de Mestre em Ciˆencias (M.Sc.)
RESOLU ¸C
˜
AO DE ESTRUTURAS DE PROTE
´
INAS
UTILIZANDO-SE DADOS DE RMN A PARTIR DE UM
ALGORITMO GEN
´
ETICO DE M
´
ULTIPLOS M
´
INIMOS
Marx Gomes Van der Linden
Junho , 2009
Orientador: Laurent Emmanuel Dardenne, D.Sc
Co-orientador: Helio Jos´e Correa Barbosa, D.Sc.
Prote´ınas s˜ao macromol´eculas biol´ogicas formadas por pol´ımeros de amino´a-
cidos, as quais est˜ao envolvidas em todos os processos vitais dos organismos, com-
preendendo um amplo leque de fun¸c˜oes. A espectropia por Ressonˆancia Magn´etica
Nuclear (rmn) ´e, ao lado da difra¸c˜ao de raios-X em cristais, uma das duas prin-
cipais t´ecnicas experimentais capazes de permitir a elucida¸c˜ao da estrutura de
prote´ınas em resolu¸c˜ao atˆomica. A predi¸c˜ao de estruturas prot´eicas utilizando
informa¸c˜oes experimentais de rmn ´e um problema de otimiza¸c˜ao global com re-
stri¸c˜oes.
O gapf ´e um programa que utiliza um Algoritmo Gen´etico (ag) desenvolvido
para predi¸c˜ao ab initio – isto ´e, para determina¸c˜ao da estrutura de uma prote´ına
apenas a partir do conhecimento de sua seq
¨
uˆencia de amino´acidos – utilizando
uma abordagem de m´ultiplos m´ınimos, baseada em uma fun¸c˜ao aptid˜ao derivada
de um campo de for¸ca molecular cl´assico. Neste trabalho, ´e descrito o gapf-
nmr, uma vers˜ao derivada do gapf, que utiliza restri¸c˜oes experimentais de rmn
para auxiliar na busca pelas melhores estruturas prot´eicas correspondentes a uma
seq
¨
uˆencia dada. Cinco vers˜oes diferentes do algoritmo foram desenvolvidas, com
diferentes varia¸c˜oes na maneira como a fun¸c˜ao de energia ´e calculada ao longo da
vii
execu¸c˜ao.
O programa desenvolvido foi aplicado a um conjunto-teste de 7 prote´ınas de
estrutura j´a conhecida e, para todas elas, foi capaz de chegar a uma estrutura com
o enovelamento correto ou aproximado. Foi observado que as vers˜oes do algoritmo
que aumentam progressivamente a regi˜ao da prote´ına usada no c´alculo de energia
tiveram desempenho superior `as demais, e que a abordagem de m´ultiplos m´ınimos
foi importante para a obten¸c˜ao de bons resultados. Os resultados foram compara-
dos aos descritos para o genfold – que ´e, at´e o momento, a ´unica implementa¸c˜ao
alternativa conhecida de um ag para o problema de predi¸c˜ao de estruturas a partir
de dados de rmn – e a vers˜ao atual do gapf-nmr se mostrou superior ao genfold
na determina¸c˜ao de duas das trˆes prote´ınas do conjunto-teste deste.
viii
Abstract of Dissertation presented to LNCC/MCT as a partial fulfillment of the
requirements for the degree of Master of Sciences (M.Sc.)
RESOLUTION OF PROTEIN STRUCTURES USING NMR DATA
BY MEANS OF A GENETIC ALGORITHM OF MULTIPLE
MINIMA
Marx Gomes Van der Linden
June, 2009
Advisor: Laurent Emmanuel Dardenne, D.Sc
Co-advisor: Helio Jos´e Correa Barbosa, D.Sc.
Proteins are biological macromolecules comprised of amino acid polymers
that play a wide range of biological roles involved in every process of living or-
ganisms. Together with X-ray diffraction, Nuclear Resonance Spectroscopy (nmr)
is one of the two main experimental techniques that are capable of delivering
atomic-level resolution of protein structures. Prediction of proteic structures using
experimental information from nmr experiments is a global optimization problem
with restraints.
gapf (Cust´odio, 2008) is a computer program that uses a Genetic Algorithm
(ga) developed for ab initio prediction – the determination of the structure of a
protein from its amino acid sequence only – using a multiple minima approach and
a fitness function derived from a classic molecular force field. The work presented
here describes gapf-nmr, an alternate version of gapf that uses experimental
restraints from nmr to support the search for the best protein structures that
correspond to a given sequence. Five different versions of the algorithm have been
developed, each with a variation on how the energy function is calculated during
the course of the program run.
gapf was tested on a test set comprised of 7 proteins with known structure
ix
and it was capable of achieving a correct or approximate fold for every one of
these proteins. It was noted that the versions of the algorithm that progressively
increase the area of the protein used in the energy function have performed better
than the other versions, and that the multiple minima approach was important
to the achievement of good results. Results were compared to those obtained by
genfold – to the moment, the only known alternate implementation of a ga
to the problem of protein structure prediction using nmr data – and the current
version of gapf was shown to be superior to genfold for two of the three proteins
that compose its test set.
x
Sum´ario
1 Introdu¸c˜ao 1
1.1 Amino´acidos e prote´ınas . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 α-h´elices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Folhas β . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.3 Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.4 Gr´afico de Ramachandran . . . . . . . . . . . . . . . . . . . 5
1.1.5 Coordenadas internas . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Campos de For¸ca e Dinˆamica Molecular . . . . . . . . . . . . . . . 7
1.3 Ressonˆancia Magn´etica Nuclear (RMN) em Prote´ınas . . . . . . . . 11
1.3.1 Restri¸c˜oes de efeitos Overhauser nucleares (NOEs) . . . . . . 14
1.3.2 Restri¸c˜oes de acoplamento escalar . . . . . . . . . . . . . . . 14
1.3.3 Informa¸c˜oes estruturais . . . . . . . . . . . . . . . . . . . . . 15
1.4 M´etodos Computacionais para Resolu¸c˜ao de Estruturas de Prote´ınas
a partir de Dados de RMN . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.1 Geometria de Distˆancia . . . . . . . . . . . . . . . . . . . . . 16
1.4.2 O m´etodo da fun¸c˜ao de alvo vari´avel . . . . . . . . . . . . . 17
1.4.3 Resolu¸c˜ao de Prote´ınas por RMN como um Problema de
Otimiza¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.4 DYANA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4.5 X-PLOR/CNS/XPLOR-NIH . . . . . . . . . . . . . . . . . 21
1.5 Predi¸c˜ao de Estruturas de Prote´ınas . . . . . . . . . . . . . . . . . . 24
xi
1.5.1 Modelagem por homologia, ou modelagem comparativa . . . 25
1.5.2 Predi¸c˜ao ab initio . . . . . . . . . . . . . . . . . . . . . . . 27
2 Objetivos 29
2.1 Objetivos Espec´ıficos . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Algoritmos Gen´eticos 31
3.1 Sele¸c˜ao Natural e Evolu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . 31
3.1.1 A Origem das Esp´ecies . . . . . . . . . . . . . . . . . . . . . 31
3.1.2 A Nova S´ıntese . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Algoritmos Gen´eticos . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.1 Popula¸c˜ao inicial . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.2 Sele¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.3 Operadores . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.4 Substitui¸c˜ao Parental . . . . . . . . . . . . . . . . . . . . . . 40
3.2.5 Nichos e Preserva¸c˜ao da Diversidade . . . . . . . . . . . . . 40
3.3 Algoritmos Gen´eticos com Restri¸c˜oes . . . . . . . . . . . . . . . . . 42
3.3.1 T´ecnicas diretas . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3.2 T´ecnicas indiretas . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.3 GENFOLD . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4 Metodologia 55
4.1 GAPF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.1.1 O Cromossomo do GAPF . . . . . . . . . . . . . . . . . . . 57
4.1.2 Fun¸c˜ao Aptid˜ao . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.1.3 Suaviza¸c˜ao do Potencial de Lennard-Jones . . . . . . . . . . 60
4.1.4 Popula¸c˜ao inicial . . . . . . . . . . . . . . . . . . . . . . . . 61
4.1.5 Operadores . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.1.6 Substitui¸c˜ao Parental . . . . . . . . . . . . . . . . . . . . . . 65
4.2 GAPF-NMR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2.1 Arquivos de entrada . . . . . . . . . . . . . . . . . . . . . . 67
xii
4.2.2 Resolu¸c˜ao de distˆancias com pseudo-´atomos . . . . . . . . . 68
4.2.3 Adapta¸c˜ao das topologias do GROMOS96 . . . . . . . . . . 70
4.2.4 Incorpora¸c˜ao das restri¸c˜oes ao GAPF . . . . . . . . . . . . . 71
4.2.5 Operadores . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.2.6 Vers˜oes do Algoritmo . . . . . . . . . . . . . . . . . . . . . . 73
4.2.7 Substitui¸c˜ao Parental . . . . . . . . . . . . . . . . . . . . . . 77
5 Resultados e Discuss˜ao 78
5.1 1GB4; Dom´ınio modificado β1 da prote´ına G . . . . . . . . . . . . . 82
5.2 1BBL; Dom´ınio de liga¸c˜ao a E3 da cadeia E2o do complexo 2-OGDH
de E. coli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.3 1FYJ; Motivo EPRS-R1 da prote´ına Glutamil-Prolil-tRNA sintetase
(EPRS-R1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.4 1PIT; Prote´ına Inibidora da Tripsina Pancre´atica (BPTI) . . . . . . 97
5.5 1OCP; Dom´ınio POU
H
da prote´ına OCT3 . . . . . . . . . . . . . . 101
5.6 1AFI; Prote´ına Bacterial Peripl´asmica MerP . . . . . . . . . . . . . 105
5.7 1KUL; Dom´ınio de liga¸c˜ao ao amido granular (SBD) da Glicoamilase108
6 Conclus˜oes e Perspectivas 111
6.1 Perspectivas Futuras . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Referˆencias Bibliogr´aficas 115
xiii
Lista de Figuras
Figura
1.1 Estrutura de um amino´acido. . . . . . . . . . . . . . . . . . . . . . 2
1.2 Liga¸c˜ao pept´ıdica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3
ˆ
Angulos φ, ψ e ω. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Gr´afico de Ramachandran. . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Representa¸c˜ao esquem´aticas dos termos envolvidos nos campos de
for¸ca. (a) extens˜ao da liga¸c˜ao covalente; (b) ˆangulo formado entre
duas liga¸c˜oes covalentes; (c) rota¸c˜ao (tor¸c˜ao) da liga¸c˜ao covalente;
(d) intera¸c˜oes de van der Waals e colis˜oes est´ericas; (e) intera¸c˜oes
eletrost´aticas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Alinhamento dos spins em torno do eixo z. Adaptado de (J. B.
Lambert e E. P. Mazzola, 2003). . . . . . . . . . . . . . . . . . . . . 12
1.7
ˆ
Angulos φ e χ
1
em uma cadeia polipept´ıdica. . . . . . . . . . . . . . 15
3.1 Descri¸c˜ao geral de um algoritmo gen´etico. . . . . . . . . . . . . . . 36
3.2 Fun¸c˜ao f5 de Jong (1975) (fox-hole) . . . . . . . . . . . . . . . . . 42
4.1 O cromossomo utilizado no gapf representa uma prote´ına como
uma cadeia de res´ıduos de amino´acidos. Cada res´ıduo, por sua vez,
´e modelado como um conjunto de ˆangulos φ, ψ e, opcionalmente,
χ
1
, ..., χ
n
, sendo 1 ≥ n ≥ 4, de acordo com a quantidade de ˆangulos
χ definida para o amino´acido correspondente. . . . . . . . . . . . . 57
4.2 Formato de entrada das restri¸c˜oes do gapf-nmr. . . . . . . . . . . 69
4.3 Restri¸c˜oes de distˆancia no arquivo de entrada. . . . . . . . . . . . . 69
xiv
4.4 Restri¸c˜oes de ˆangulos diedrais no arquivo de entrada. . . . . . . . . 69
4.5 Esquematiza¸c˜ao da vers˜ao Walk. . . . . . . . . . . . . . . . . . . . . 74
4.6 Esquematiza¸c˜ao da vers˜ao Grow. . . . . . . . . . . . . . . . . . . . 75
5.1 Correla¸c˜ao entre a viola¸c˜ao m´edia das restri¸c˜oes de distˆancia em
indiv´ıduos da popula¸c˜ao final e seus rmsds em rela¸c˜ao a uma estru-
tura de referˆencia. Os dados se referem a uma execu¸c˜ao do algoritmo
para dom´ınio β1 modificado da prote´ına G (Se¸c˜ao 5.1), na vers˜ao
MemWalk, com uso do termo de Coulomb. . . . . . . . . . . . . . . 81
5.2 Estrutura prim´aria e estrutura secund´aria do dom´ınio β1 da pro-
te´ına G de Streptococcus c´odigo pdb: 1GB4). (Malakauskas e Mayo,
1998). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.3 Varia¸c˜ao dos termos da fun¸c˜ao de aptid˜ao ao longo de uma execu¸c˜ao
da vers˜ao MemWalk do gapf-nmr, com termo de Coulomb, para o
dom´ınio modificado β1 da prote´ına G (c´odigo pdb: 1GB4). A cada
100.000 execu¸c˜oes, o algoritmo passa a operar em um novo fragmento. 87
5.4 Esquematiza¸c˜ao das viola¸c˜oes de distˆancia mais violadas em (a) uma
das estruturas finais geradas pelo gapf-nmr para o Dom´ınio mod-
ificado β1 da prote´ına G, usando a vers˜ao MemWalk do algoritmo,
sem o termo de Coulomb (b) uma estrutura de referˆencia (c´odigo
pdb: 1GB4). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.5 Mapa de viola¸c˜ao de restri¸c˜oes do dom´ınio modificado β1 da pro-
te´ına G (ver texto).
(a) Estrutura gerada. (b) Estrutura de referˆencia experimental. . . 88
5.6 Estrutura prim´aria e estrutura secund´aria do dom´ınio de liga¸c˜ao a
e3 da cadeia E2o do complexo 2-OGDH de E. coli (c´odigo pdb:
1BBL). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.7 Varia¸c˜ao dos termos de energia ao longo da execu¸c˜ao do algoritmo,
para o dom´ınio de liga¸c˜ao a e3 da cadeia E2o do complexo 2-OGDH
de E. coli. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
xv
5.8 (a) Estrutura final calculada por uma das execu¸c˜oes do gapf NMR
para o dom´ınio de liga¸c˜ao a e3 da cadeia E2o do complexo 2-OGDH
de E. coli. As liga¸c˜oes em vermelho indicam as restri¸c˜oes de distˆan-
cia mais violadas. (b) Estrutura de referˆencia (c´odigo pdb: 1BBL). 91
5.9 Mapa de viola¸c˜ao de restri¸c˜oes do dom´ınio de liga¸c˜ao a e3 da cadeia
E2o do complexo 2-OGDH de E. coli. (a) Estrutura gerada. (b)
Estrutura de referˆencia experimental. . . . . . . . . . . . . . . . . . 92
5.10 Estrutura prim´aria e estrutura secund´aria do motivo eprs-r1 da
prote´ına Glutamil-Prolil-tRNA sintetase (c´odigo pdb: 1FYJ). . . . 93
5.11 Varia¸c˜ao dos termos de energia ao longo da execu¸c˜ao do algoritmo,
para a prote´ına eprs-r1. . . . . . . . . . . . . . . . . . . . . . . . . 95
5.12 (a) Estrutura final calculada por uma das execu¸c˜oes do gapf-nmr
para a prote´ına eprs-r1. As liga¸c˜oes em vermelho indicam as
restri¸c˜oes de distˆancia mais violadas. (b) Estrutura de referˆencia
(c´odigo pdb: 1FYJ). . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.13 Mapa de viola¸c˜ao de restri¸c˜oes da prote´ına eprs-r1. (a) Estrutura
gerada. (b) Estrutura de referˆencia experimental. . . . . . . . . . . 96
5.14 Estrutura prim´aria e estrutura secund´aria da prote´ına Prote´ına In-
ibidora da Tripsina Pancre´atica (c´odigo pdb: 1PIT). . . . . . . . . 97
5.15 (a) Estrutura final calculada por uma das execu¸c˜oes do gapf-nmr
para a prote´ına bpti. (b) Estrutura de referˆencia (c´odigo pdb:
1PIT). Em ambas as figuras, est˜ao indicados os res´ıduos de ciste´ına. 99
5.16 Varia¸c˜ao dos termos de energia ao longo da execu¸c˜ao do algoritmo,
para a prote´ına bpti. . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.17 Mapa de viola¸c˜ao de restri¸c˜oes da prote´ına bpti. (a) Estrutura
gerada. (b) Estrutura de referˆencia experimental. . . . . . . . . . . 100
5.18 Estrutura prim´aria e estrutura secund´aria do dom´ınio pou
H
da pro-
te´ına oct3 (c´odigo pdb: 1OCP). . . . . . . . . . . . . . . . . . . . 101
xvi
5.19 Varia¸c˜ao dos termos de energia ao longo da execu¸c˜ao do algoritmo,
para o dom´ınio pou
H
da prote´ına oct3. . . . . . . . . . . . . . . . 103
5.20 (a) Estrutura final calculada por uma das execu¸c˜oes do gapf NMR
para o dom´ınio pou
H
da prote´ına oct3. As liga¸c˜oes em vermelho
indicam as restri¸c˜oes de distˆancia mais violadas. (b) Estrutura de
referˆencia (c´odigo pdb: 1OCP). . . . . . . . . . . . . . . . . . . . . 103
5.21 Mapa de viola¸c˜ao de restri¸c˜oes do dom´ınio pou
H
da prote´ına oct3..
(a) Estrutura gerada. (b) Estrutura de referˆencia experimental. . . 104
5.22 Estrutura prim´aria e estrutura secund´aria da prote´ına MerP (c´odigo
pdb: 1AFI). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.23 (a) Estrutura final calculada por uma das execu¸c˜oes do gapf NMR
para a prote´ına MerP. As liga¸c˜oes em vermelho indicam as restri¸c˜oes
de distˆancia mais violadas. (b) Estrutura de referˆencia (c´odigo pdb:
1AFI). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.24 Varia¸c˜ao dos termos de energia ao longo da execu¸c˜ao do algoritmo,
para a prote´ına MerP. . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.25 Estrutura prim´aria e estrutura secund´aria do dom´ınio sbd da gli-
coamilase 1 (c´odigo pdb: 1KUL). . . . . . . . . . . . . . . . . . . . 108
5.26 Varia¸c˜ao dos termos de energia ao longo da execu¸c˜ao do algoritmo,
para o dom´ınio sbd da glicoamilase 1. . . . . . . . . . . . . . . . . 110
5.27 (a) Estrutura final calculada por uma das execu¸c˜oes do gapf-nmr
para o dom´ınio sbd da glicoamilase 1. As liga¸c˜oes em vermelho
indicam as restri¸c˜oes de distˆancia mais violadas. (b) Estrutura de
referˆencia (c´odigo pdb: 1KUL). Em ambas as figuras, est˜ao indica-
dos os res´ıduos de ciste´ına. . . . . . . . . . . . . . . . . . . . . . . . 110
xvii
Lista de Tabelas
Tabela
4.1 Valores de φ e ψ em graus. . . . . . . . . . . . . . . . . . . . . . . . 62
4.2 Classifica¸c˜ao dos amino´acidos como hidrof´obicos e n˜ao-hidrof´obicos
(Callebaut et al., 1997). . . . . . . . . . . . . . . . . . . . . . . . . 66
5.1 Conjunto-teste de prote´ınas utilizado neste estudo. . . . . . . . . . 79
5.2 Resultados obtidos pelo gapf-nmr para o Dom´ınio modificado β1
da prote´ına G, em rela¸c˜ao `a estrutura de referˆencia depositada sob
o c´odigo 1GB4 no pdb. . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.3 Tempo m´edio de execu¸c˜ao do gapf em diferentes configura¸c˜oes para
o Dom´ınio modificado β1 da prote´ına G, em rela¸c˜ao `a estrutura de
referˆencia depositada sob o c´odigo 1GB4 no pdb em uma m´aquina
Intel Core 2 Duo e6550 (2.33GHz), com 2GB de mem´oria ram. 84
5.4 Resultados obtidos pelo gapf-nmr para o Dom´ınio modificado β1
da prote´ına G, em rela¸c˜ao `a estrutura de referˆencia depositada sob
o c´odigo 1GB4 no pdb, sem o mecanismo de crowing (M´ultiplos
M´ınimos). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.5 Resultados obtidos pelo gapf-nmr para o dom´ınio de liga¸c˜ao a
e3 da cadeia E2o do complexo 2-OGDH de E. coli, em rela¸c˜ao `a
estrutura de referˆencia depositada sob o c´odigo 1BBL no pdb. . . . 90
5.6 Resultados obtidos pelo gapf-nmr para a prote´ına eprs-r1, em
rela¸c˜ao `as estruturas de referˆencia depositadas sob o c´odigo 1FYJ
no pdb. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
xviii
5.7 Resultados obtidos pelo gapf-nmr para a prote´ına bpti, em rela¸c˜ao
`as estruturas de referˆencia depositadas sob o c´odigo 1PIT no pdb.
Na ´ultima linha, para efeito de compara¸c˜ao, ´e exibido o resultado
obtido pelo genfold. . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.8 Resultados obtidos pelo gapf-nmr para o dom´ınio pou
H
da pro-
te´ına oct3, em rela¸c˜ao `as estruturas de referˆencia depositadas sob
o c´odigo 1OCP no pdb. . . . . . . . . . . . . . . . . . . . . . . . . 102
5.9 Resultados obtidos pelo gapf-nmr para a prote´ına MerP, em re-
la¸c˜ao `as estruturas de referˆencia depositadas sob o c´odigo 1AFI no
pdb. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.10 Resultados obtidos pelo gapf-nmr para o dom´ınio sbd da glicoami-
lase 1, em rela¸c˜ao `as estruturas de referˆencia depositadas sob o
c´odigo 1KUL no pdb. . . . . . . . . . . . . . . . . . . . . . . . . . . 109
xix
Lista de Siglas e Abreviaturas
˚
A: Angstroms
1AFI: Prote´ına Bacterial Peripl´asmica MerP
1BBL: Dom´ınio de liga¸c˜ao a E3 da cadeia E2o do complexo 2-OGDH de E. coli
1FYJ: Motivo EPRS-R1 da prote´ına Glutamil-Prolil-tRNA sintetase (EPRS-R1)
1GB4: Dom´ınio modificado β1 da prote´ına G
1KUL: Dom´ınio de liga¸c˜ao ao amido granular (SBD) da Glicoamilase
1OCP: Dom´ınio POU
H
da prote´ına OCT3
1PIT: Prote´ına Inibidora da Tripsina Pancre´atica (BPTI)
2X: Operador Crossover de 2 pontos
3D: Tridimensional
AG: Algoritmo Gen´etico
ALA: Alanina
ARG: Arginina
ASN: Asparagina
ASP:
´
Acido asp´artico
C
α
: Carbono-α
CASP: Critical Assessment of Techniques for Protein Structure Prediction
CE: Computa¸c˜ao Evolucion´aria
CHARMM: Chemistry at HARvard Macromolecular Mechanics
CMUT: Muta¸c˜ao Compensat´oria
CYS: Ciste´ına
DM: Dinˆamica Molecular
xx
DNA (ou ADN):
´
Acido Desoxirribonucl´eico
GLN: Glutamina
GLU:
´
Acido glutˆamico
GLY: Glicina
HIS: Histidina
ILE: Isoleucina
IMUT: Muta¸c˜ao Incremental
LEU: Leucina
LYS: Lisina
MET: Metionina
MPX: Operador Crossover de M´ultiplos Pontos
MUTACAUCHY: Muta¸c˜ao de Cauchy
MUTANU: Muta¸c˜ao n˜ao Uniforme
NOE: Nuclear Overhauser Effect
NOESY: Nuclear Overhauser Effect Spectroscopy
PDB: Protein Data Bank
PHE: Fenilalanina
PRO: Prolina
RMN: Ressonˆancia Magn´etica Nuclear
RMSD: Desvio M´edio Quadr´atico
SER: Serina
SMUT: Muta¸c˜ao de Segmentos
TC: Troca Cont´ıgua
THR: Treonina
TRP: Triptofano
TYR: Tirosina
VAL: Valina
xxi
Cap´ıtulo 1
Introdu¸c˜ao
Este trabalho descreve o desenvolvimento e a implementa¸c˜ao de um Algo-
ritmo Gen´etico de m´ultiplos m´ınimos que tem como objetivo determinar estruturas
tridimensionais de prote´ınas a partir de dados emp´ıricos oriundos de experimentos
de Espectropia de Ressonˆancia Magn´etica Nuclear. O resultado da implementa¸c˜ao
deste algoritmo ´e o programa gapf-nmr, que ´e uma vers˜ao modificada e adap-
tada do gapf, software desenvolvido por Cust´odio (2008) para realizar predi¸c˜oes
ab initio de estruturas de prote´ınas.
No Cap´ıtulo 2, ser˜ao apresentados os objetivos do trabalho. No Cap´ıtulo
3, ser´a desenvolvida uma revis˜ao bibliogr´afica a respeito de Algoritmos Gen´eticos,
com ˆenfase nos principais conceitos que ser˜ao aplicados ao algoritmo descrito neste
trabalho, em particular as t´ecnicas existentes para se lidarem com problemas que
envolvem restri¸c˜oes. No Cap´ıtulo 4, ser´a descrita a metodologia aplicada no de-
senvolvimento do gapf-nmr, assim como no software que lhe serve como base, o
gapf. O Cap´ıtulo 5 apresenta e discute os resultados obtidos a partir da execu¸c˜ao
do gapf-nmr em um conjunto-teste composto por 7 seq
¨
uˆencias pept´ıdicas.
1.1 Amino´acidos e prote´ınas
Amino´acidos s˜ao mol´eculas orgˆanicas que se caracterizam por um ´atomo de
carbono (Cα) ligado a um grupamento amina prim´aria (NH
2
), um grupamento
carboxila (COOH), um ´atomo de hidrogˆenio e uma cadeia lateral vari´avel (Figura
1
Figura 1.1: Estrutura de um amino´acido.
1.1).
A liga¸c˜ao covalente formada entre o carbono do grupo carboxila de um
amino´acido e o nitrogˆenio do grupo amina de outro amino´acido ´e chamada lig-
a¸c˜ao pept´ıdica. Pept´ıdios ou cadeias polipept´ıdicas s˜ao formados por seq
¨
uˆencias
de res´ıduos de amino´acidos unidos atrav´es de liga¸c˜oes pept´ıdicas. Uma prote´ına
´e uma macromol´ecula com fun¸c˜ao biol´ogica formada por uma ou mais cadeias
polipept´ıdicas. Durante o processo de s´ıntese prot´eica, liga¸c˜oes pept´ıdicas s˜ao for-
madas seq
¨
uencialmente: a extremidade carboxila do pept´ıdeo em forma¸c˜ao se liga
`a extremidade amino do novo amino´acido a ser acrescentado, com a elimina¸c˜ao
de uma mol´ecula de ´agua no processo. Cada amino´acido, ao ser incorporado `a
prote´ına, passa a ser chamado res´ıduo de amino´acido (Figura 1.2).
A estrutura de uma prote´ına ´e caracterizada pela organiza¸c˜ao dos res´ıduos
de amino´acido em padr˜oes regulares (estruturas secund´arias) e pela conforma¸c˜ao
completa destes no espa¸co tridimensional (estrutura terci´aria). Os ´atomos de car-
bono e nitrogˆenio que participam da liga¸c˜ao pept´ıdica formam um plano r´ıgido
no espa¸co (Figura 1.3), o qual inclui os ´atomos de oxigˆenio e hidrogˆenio ligados
respectivamente `aqueles. O ˆangulo da liga¸c˜ao pept´ıdica (conhecido como ˆangulo
ω) pode assumir, portanto, apenas dois valores: 0 ou 180.
Os outros ˆangulos formados na cadeia principal s˜ao o ˆangulo φ, entre o Cα
Figura 1.2: Liga¸c˜ao pept´ıdica.
2
Figura 1.3:
ˆ
Angulos φ, ψ e ω.
e o N, e o ˆangulo ψ, entre o Cα e o carbono do terminal carboxila. Estes podem
assumir uma gama de valores bem mais ampla, dentro de limites impostos por
restri¸c˜oes estereoqu´ımicas. A estrutura tridimensional de uma prote´ına pode ser
quase completamente caracterizada a partir da defini¸c˜ao de todos os seus ˆangulos
φ e ψ.
Adicionalmente, para cada res´ıduo de amino´acido, tamb´em s˜ao definidos os
ˆangulos χ
n
, formados entre o n-´esimo carbono da cadeia lateral e seu ´atomo de
carbono precedente (que, no caso de n = 1, ´e o Cα).
1.1.1 α-h´elices
Quando uma seq
¨
uˆencia de res´ıduos de amino´acidos consecutivos em uma
seq
¨
uˆencia prot´eica forma entre si ˆangulos φ e ψ correspondentes a aproximadamente
−60
◦
e −50
◦
, ´e formado um padr˜ao regular helicoidal conhecido como α-h´elice, um
dos elementos mais importantes na estabiliza¸c˜ao de estruturas prot´eicas.
Uma α-h´elice tem aproximadamente 3,6 res´ıduos por volta e ´e estabilizada
internamente por pontes de hidrogˆenio entre o oxigˆenio (aceptor) do grupamento
C=O de cada res´ıduo e o nitrogˆenio (doador) do grupamento NH localizado 4
posi¸c˜oes adiante. As varia¸c˜oes em que as pontes s˜ao formadas entre grupamen-
tos C=O e NH posicionados em res´ıduos 3 ou 5 posi¸c˜oes adiante s˜ao conhecidas
como 3
10
-h´elice e π-h´elice, respectivamente. Estas s˜ao energeticamente menos fa-
vor´aveis, por isso, relativamente incomuns, costumando aparecer apenas no final de
α-h´elices, ou realizando apenas uma volta (Branden e Tooze, 1998). Quase todas
as α-h´elices encontradas em prote´ınas s˜ao direcionadas `a direita, pois a forma¸c˜ao
3
de α-h´elices orientadas `a esquerda com amino´acidos lev´ogiros ´e desfavorecida es-
tereoquimicamente.
As cadeias laterais dos amino´acidos se projetam para fora das α-h´elices,
portanto interferem pouco em sua estrutura, com exce¸c˜ao do amino´acido Prolina,
cuja estrutura r´ıgida c´ıclica tende a romper o padr˜ao da helicoidal. Os efeitos
provocados por cadeias laterais de seq
¨
uˆencias compostas por muitos amino´acidos
carregados podem, entretanto, ser incompat´ıveis com a estrutura de α-h´elice, e
´e conhecido que alguns amino´acidos tendem a ser encontrados em α-h´elices com
mais freq
¨
uˆencia que outros.
Todas as pontes de hidrogˆenio formadas ao longo da estrutura helicoidal
est˜ao alinhadas sobre o mesmo eixo, e cada uma delas tem um momento dipolo.
Como conseq
¨
uˆencia, toda a cadeia que forma a α-h´elice tem, em conjunto, um
momento dipolo significativo, com uma carga parcial positiva no terminal amina,
e uma carga parcial negativa no terminal carboxila.
α-h´elices podem se estabilizar melhor em solu¸c˜ao unindo-se em pares super-
helicoidais que se estabilizam mutuamente atrav´es de pontes de hidrogˆenio. Essa
estrutura ´e chamada coiled coil e forma a base de muitas prote´ınas fibrosas (Bran-
den e Tooze, 1998).
1.1.2 Folhas β
O outro arranjo estrutural predominante encontrado em prote´ınas s˜ao as
folhas β, formadas por grupos de seq
¨
uˆencias (fitas β) de regi˜oes diferentes da cadeia
pept´ıdica. Essas fitas se organizam em conforma¸c˜ao estendida e se estabilizam
atrav´es da forma¸c˜ao de pontes de hidrogˆenio entre os grupos C=O de cada fita
com os grupos NH de fitas adjacentes. A forma¸c˜ao de folhas β, portanto, n˜ao
depende apenas de intera¸c˜oes locais, como ocorre com as α-h´elices.
Quando as fitas β se alinham na mesma dire¸c˜ao, diz-se que formam uma
estrutura folha β paralela. Do contr´ario, formam uma folha β antiparalela. As
cadeias laterais ficam projetadas, para ambos os lados alternadamente, no plano
4
perpendicular `aquele formado pelas pontes de hidrogˆenio entre os res´ıduos.
1.1.3 Loops
Loops s˜ao elementos que conectam estruturas secund´arias, para compor a
conforma¸c˜ao terci´aria da prote´ına. Os grupos C=O e NH dos loops geralmente
n˜ao formam pontes de hidrogˆenio entre si, ficando expostos ao solvente e podendo
formar pontes de hidrogˆenio com mol´eculas de ´agua. Essas regi˜oes tendem a ser ri-
cas em res´ıduos polares e carregados e freq
¨
uentemente participam de intera¸c˜oes com
ligantes. Regi˜oes de loop que conectam duas folhas β antiparalelas s˜ao chamadas
hairpin loops (Branden e Tooze, 1998).
1.1.4 Gr´afico de Ramachandran
Figura 1.4: Gr´afico de Ramachandran.
Em 1962, o f´ısico indiano G. N. I. Ramachandran analisou, entre todas as
combina¸c˜oes dos ˆangulos φ e ψ, quais s˜ao estereoquimicamente poss´ıveis entre
res´ıduos de amino´acidos, e em que estruturas resultaria cada combina¸c˜ao. O re-
sultado deste trabalho ´e conhecido como gr´afico de Ramachandran. O gr´afico de
Ramachandran ´e bidimensional. O eixo x mostra os ˆangulos φ; o eixo y, os ˆangulos
ψ. No exemplo mostrado na Figura 1.4, as regi˜oes em que as combina¸c˜oes destes
5
ˆangulos s˜ao favor´aveis est˜ao desenhadas em cor progressivamente mais escura. O
gr´afico de Ramachandran identifica 3 ´areas favor´aveis `a conforma¸c˜ao pept´ıdica,
correspondentes `as forma¸c˜oes de diferentes estruturas secund´arias: folhas β, α-
h´elices e α-h´elices no sentido esquerdo (representado por L).
1.1.5 Coordenadas internas
A estrutura completa de uma prote´ına pode ser representada de duas maneiras
principais: a mais direta consiste no uso de coordenadas cartesianas, em que cada
´atomo ´e representado como um ponto no espa¸co tridimensional. Essa ´e a repre-
senta¸c˜ao utilizada nos arquivos do Protein Data Bank, ou pdb
1
, o banco de dados
on-line em que s˜ao depositadas, para acesso livre, estruturas de prote´ınas determi-
nadas experimentalmente por grupos de pesquisa de todo o mundo (Berman et al.,
2003). Um conjunto de coordenadas cartesianas n˜ao cont´em informa¸c˜oes sobre as
liga¸c˜oes covalentes entre os ´atomos que formam a estrutura da mol´ecula. Essa
informa¸c˜ao pode ser suplementada separadamente (como ocorre comumente nos
arquivos formatados de acordo com o pdb) ou deduzida posteriormente a partir
dos tipos de ´atomos e suas distˆancias.
Uma maneira alternativa de se representar uma estrutura prot´eica ´e atrav´es
do uso de coordenadas internas (A. Leach, 2001), tamb´em conhecidas como coor-
denadas torcionais. No sistema de coordenadas internas, usa-se uma matriz, geral-
mente denominada matriz-Z, em que cada linha, descreve um ´atomo de acordo
com sua posi¸c˜ao no espa¸co relativamente aos ´atomos descritos em linhas anteri-
ores, conforme (1.1):
i el d i
d
θ i
θ
λ i
λ
(1.1)
Em cada linha, i ´e o ´ındice do ´atomo descrito (iniciando em 1), e el indica o
elemento a que o ´atomo pertence. Essas s˜ao as duas ´unicas informa¸c˜oes presentes
na primeira linha da matriz, que indica o primeiro ´atomo. A partir da segunda
linha tamb´em se indicam os pr´oximos dois campos: d ´e a distˆancia entre o ´atomo
1
http://www.rcsb.org/pdb/
6
descrito (i) e o ´atomo de ´ındice i
d
, sendo i
d
< i. A partir da terceira linha, indica-se
tamb´em mais dois campos: θ ´e o ˆangulo formado entre i , i
d
e i
θ
, sendo tamb´em
i
θ
< i. A partir da quarta linha, sendo tamb´em i
λ
< i, λ indica o ˆangulo torcional
formado entre i, i
d
,i
θ
e i
λ
, ou seja, o ˆangulo formado entre o plano que cont´em os
pontos i, i
d
e i
θ
e o plano que cont´em os pontos i
d
, i
θ
e i
λ
.
A representa¸c˜ao em coordenadas internas pode conter informa¸c˜oes sobre a
estrutura completa de liga¸c˜oes covalentes da prote´ına, se se convencionar que a
distˆancia d sempre se refere a dois ´atomos covalentemente ligados.
A principal vantagem da representa¸c˜ao em coordenadas internas ´e a facili-
dade de manipula¸c˜ao da estrutura, preservando-se a geometria covalente da pro-
te´ına.
´
E poss´ıvel, por exemplo, com a altera¸c˜ao de apenas um elemento da ma-
triz, rotacionar uma liga¸c˜ao entre dois ´atomos, a qual afetar´a a posi¸c˜ao absoluta
de um grande n´umero de ´atomos subseq
¨
uentes, sem a necessidade de se realizar
nenhum c´alculo adicional. Por outro lado, n˜ao ´e poss´ıvel calcular diretamente a
distˆancia entre dois ´atomos arbitr´arios, um tipo de informa¸c˜ao que ´e extremamente
importante em praticamente qualquer tipo de c´alculo computacional que envolva
estruturas de prote´ınas.
Uma vez que ambas as representa¸c˜oes s˜ao mutuamente intercambi´aveis, ´e
comum que aplica¸c˜oes utilizem coordenadas internas para realizar opera¸c˜oes que
modificam a estrutura da prote´ına, e coordenadas cartesianas para os c´alculos que
envolvem distˆancias interatˆomicas.
1.2 Campos de For¸ca e Dinˆamica Molecular
A maneira mais precisa de se modelar computacionalmente um sistema atˆomico
´e atrav´es da aplica¸c˜ao de m´etodos que envolvem c´alculos de Mecˆanica Quˆantica.
Macromol´eculas biol´ogicas como as prote´ınas, entretanto, s˜ao suficientemente com-
plexas para tornar proibitivo o custo computacional deste n´ıvel te´orico de trata-
mento. Simula¸c˜oes computacionais de prote´ınas, portanto, costumam utilizar a
abordagem dos campos de for¸ca cl´assicos (utilizando a Mecˆanica Molecular), que
7
Figura 1.5: Representa¸c˜ao esquem´aticas dos termos envolvidos nos campos de
for¸ca. (a) extens˜ao da liga¸c˜ao covalente; (b) ˆangulo formado entre duas liga¸c˜oes
covalentes; (c) rota¸c˜ao (tor¸c˜ao) da liga¸c˜ao covalente; (d) intera¸c˜oes de van der
Waals e colis˜oes est´ericas; (e) intera¸c˜oes eletrost´aticas.
ignorando o tratamento expl´ıcito dos el´etrons, vˆe o sistema molecular como um
arranjo newtoniano de massas pontuais unidas por molas, com todas as constantes
ajustadas empiricamente. O objetivo da Mecˆanica Molecular ´e simular, com o
m´aximo de precis˜ao poss´ıvel, os resultados que seriam obtidos por m´etodos quˆan-
ticos, em apenas uma fra¸c˜ao do tempo computacional que estes consumiriam (A.
Leach, 2001).
Um campo de for¸ca ´e uma forma funcional e um conjunto de parˆametros
que modela a energia de um sistema molecular de acordo com os pressupostos da
Mecˆanica Molecular. A fun¸c˜ao de energia de um campo de for¸ca costuma ter a
seguinte forma geral (A. Leach, 2001):
E =
ligacoes
k
i
2
(l
i
− l
i,0
)
2
+
angulos
m
i
2
(θ
i
− θ
i,0
)
2
+
torsionais
V
n
2
(1 + cos(nω − γ))
+
N
i=1
N
i=i+1
4ε
ij
σ
ij
r
ij
12
−
σ
ij
r
ij
6
+
q
i
q
j
4πε
0
r
ij
(1.2)
Os dois primeiros termos da equa¸c˜ao (1.2) s˜ao potenciais harmˆonicos que
modelam o aumento de energia `a medida que a liga¸c˜ao covalente se afasta de sua
configura¸c˜ao ´otima: o primeiro modela a varia¸c˜ao de energia com a altera¸c˜ao da
8
distˆancia entre os dois ´atomos que participam da liga¸c˜ao covalente (Figura 1.5, a);
o segundo, a varia¸c˜ao de energia com a altera¸c˜ao do ˆangulo formado entre duas
liga¸c˜oes covalentes (Figura 1.5, b). k
i
, m
i
s˜ao as constantes el´asticas relacionadas,
respectivamente, a esses dois termos; l
i
´e a distˆancia da liga¸c˜ao i, l
i,0
´e a distˆancia
de referˆencia da liga¸c˜ao i (isto ´e, o valor que a distˆancia assume quando todos os
outros termos do campo de for¸ca s˜ao iguais a zero); θ
i
´e o valor do i-´esimo ˆangulo
formado entre duas liga¸c˜oes covalentes na mol´ecula, θ
i,0
´e o ˆangulo de referˆencia
dessas liga¸c˜oes.
O terceiro termo modela como a energia varia `a medida que a liga¸c˜ao co-
valente ´e rotacionada (Figura 1.5, c). V
n
, n e γ s˜ao constantes que estabelecem,
respectivamente, a amplitude, a multiplicidade (isto ´e, o n´umero de m´ınimos) e a
fase do potencial que modela essa varia¸c˜ao de energia.
O ´ultimo termo ´e calculado entre todos os pares de ´atomos i e j n˜ao ligados
e ´e composto pelo potencial de Lennard-jones, que modela as varia¸c˜oes de energia
decorrentes de atra¸c˜oes de van der Waals e colis˜oes est´ericas (Figura 1.5, c) e pelo
potencial de Coulomb, que modela a influˆencia de cargas el´etricas (q
i
,q
j
) (Figura
1.5, d). Esse ´e o termo que, devido a sua natureza combinatorial, apresenta o
c´alculo computacional mais intensivo. No potencial de Lennard-Jones, ε
ij
e σ
ij
s˜ao parˆametros que estabelecem, respectivamente, a separa¸c˜ao em que a energia
passa pelo seu valor m´ınimo, e o diˆametro de colis˜ao; no potencial de Coulomb, ε
0
´e a permissividade el´etrica do v´acuo. Em todos os casos, r
ij
´e a distˆancia entre os
´atomos i e j.
Os valores para os v´arios parˆametros da fun¸c˜ao de energia de um campo
de for¸ca variam de acordo com os pares de ´atomos considerados, e, assim como
os detalhes de como os seus c´alculos s˜ao implementados, com o campo de for¸ca
utilizado. Entre os campos de for¸ca mais comumente utilizados, incluem-se o
Gromos (van Gunsteren e Berendsen, 1987), Charmm (Bernard R. Brooks et al.,
1983) e Amber/Opls (Jorgensen e Tirado-Rives, 1988).
Dinˆamica Molecular (dm) ´e a simula¸c˜ao computacional da evolu¸c˜ao de um
9
sistema molecular ao longo de um per´ıodo de tempo. As sucessivas configura¸c˜oes
do sistema s˜ao geradas atrav´es da integra¸c˜ao das equa¸c˜oes da mecˆanica cl´assica,
especialmente da segunda lei de Newton (equa¸c˜oes 1.3 e 1.4), para cada ´atomo i
do sistema:
F
x
i
= m
i
a
x
i
(1.3)
a
x
i
=
d
2
x
i
dt
2
(1.4)
onde m
i
´e a massa da part´ıcula, a
x
i
, a acelera¸c˜ao da part´ıcula ao longo da co-
ordenada x
i
, e F
x
i
, a for¸ca que atua na part´ıcula nessa dire¸c˜ao. O resultado da
simula¸c˜ao ´e uma trajet´oria que especifica como as posi¸c˜oes e velocidades de todas
as part´ıculas envolvidas variam ao longo do tempo (A. Leach, 2001).
Uma vez que ´e imposs´ıvel resolver analiticamente todo o sistema de equa¸c˜oes
associado ao c´alculo da estrutura de uma macromol´ecula, a simula¸c˜ao de Dinˆamica
Molecular procede atrav´es de m´etodos de integra¸c˜ao num´erica, dividindo a tra-
jet´oria em v´arios pequenos est´agios, separados por um intervalo δt. A for¸ca total
atuante em cada part´ıcula a cada instante t ´e calculada como a soma vetorial, nesse
instante, de suas intera¸c˜oes com todas as outras part´ıculas. A partir do c´alculo das
for¸cas que atuam em todas as part´ıculas, e assumindo que estas permanecem con-
stantes durante o intervalo δt, ´e poss´ıvel determinar suas respectivas acelera¸c˜oes
e, com isso, suas posi¸c˜oes e velocidades no instante t + δt. Diversos m´etodos de
integra¸c˜ao num´erica s˜ao comumente usados em Dinˆamica Molecular, e a escolha
do m´etodo pode ser um fator importante no desempenho do algoritmo (A. Leach,
2001).
Pode ser desej´avel, por diversos motivos, controlar a temperatura ou a press˜ao
de um sistema durante uma simula¸c˜ao de dm. Por exemplo, em um procedimento
de annealing, ´e necess´ario reduzir gradualmente a temperatura de um sistema ao
longo da execu¸c˜ao.
A temperatura de um sistema est´a diretamente relacionada a sua energia
10
cin´etica m´edia. Por esse motivo, a maneira mais direta de se alter´a-la ´e atrav´es
de multiplica¸c˜ao por um fator escalar das velocidades de todos os elementos que
comp˜oem o sistema. Um m´etodo alternativo, que permite manter a temperatura do
sistema constante ao longo da execu¸c˜ao, corrigindo desvios de maneira gradual, ´e
a acopla¸c˜ao deste a uma fonte externa de energia termal, chamada banho t´ermico,
que transfere calor ao sistema quando a temperatura deste se encontra abaixo
da desej´avel, e absorve calor, no caso inverso. Neste m´etodo, as velocidades s˜ao
escaladas suavemente, de modo que, a cada passo, a mudan¸ca na temperatura no
sistema, ´e proporcional `a diferen¸ca entre esta e a temperatura do banho t´ermico
(A. Leach, 2001).
De maneira an´aloga, ´e poss´ıvel especificar e controlar a press˜ao em uma
simula¸c˜ao de dm. Deste modo, o comportamento do sistema pode ser estudado
em fun¸c˜ao de sua press˜ao. Os m´etodos usados para controlar a press˜ao de um
sistema s˜ao an´alogos aos usados para a temperatura: neste caso, ´e poss´ıvel alterar
a press˜ao de um sistema atrav´es do escalonamento direto de seu volume. Tamb´em
´e comumente utilizando o mecanismo de banho hidrost´atico, um sistema acoplado
que recebe e fornece press˜ao de maneira gradual ao sistema principal, atrav´es de
altera¸c˜oes de volume, de maneira an´aloga ao comportamento do banho t´ermico (A.
Leach, 2001).
1.3 Ressonˆancia Magn´etica Nuclear (RMN) em Prote´ınas
O problema de resolu¸c˜ao de estruturas prot´eicas por Ressonˆancia Magn´etica
Nuclear (rmn) se refere `a resolu¸c˜ao da estrutura tridimensional de uma prote´ına a
partir de informa¸c˜oes provenientes do conhecimento de sua seq
¨
uˆencia de amino´a-
cidos e de restri¸c˜oes conformacionais obtidas por dados experimentais de rmn. A
espectropia por Ressonˆancia Magn´etica Nuclear ´e, ao lado da t´ecnica de difra¸c˜ao
de raios-X em cristais, uma das duas principais t´ecnicas experimentais capazes de
permitir a elucida¸c˜ao da estrutura de prote´ınas em resolu¸c˜ao atˆomica.
As t´ecnicas de rmn exploram a propriedade fundamental das part´ıculas
11
chamada spin (I). Pr´otons, el´etrons e nˆeutrons possuem I = ±
1
2
. O spin dota
as part´ıculas de propriedades f´ısicas de momento angular, an´alogas `as de uma
part´ıcula em rota¸c˜ao. O spin do n´ucleo atˆomico, por ser positivamente carregado,
gera um campo magn´etico similar ao de uma carga positiva movendo-se em c´ırcu-
los, dotada de um vetor momento magn´etico µ (J. B. Lambert e E. P. Mazzola,
2003). A magnitude do momento magn´etico produzido por um n´ucleo varia de
acordo com:
µ = γI (1.5)
onde ´e a constante de Planck
2
dividida por 2π, e γ ´e a chamada constante
giromagn´etica, caracter´ıstica de cada n´ucleo.
Duas ou mais part´ıculas com spins de sinais contr´arios e igual magnitude
podem se parear. Nesse caso, as manifesta¸c˜oes observ´aveis do spin s˜ao eliminadas.
Em experimentos de rmn, utilizam-se spins nucleares n˜ao pareados, principal-
mente, no caso de experimentos para determina¸c˜ao de estruturas prot´eicas,
1
H e
13
C.
Figura 1.6: Alinhamento dos spins em torno do eixo z. Adaptado de (J. B. Lambert
e E. P. Mazzola, 2003).
Na ausˆencia de um campo magn´etico externo, todos os n´ucleos do mesmo
is´otopo tˆem a mesma energia. Durante o experimento rmn, gera-se um forte campo
magn´etico B
0
em uma dire¸c˜ao designada como o eixo z (Figura 1.6). Nesse caso, os
2
=
h
2π
= 1, 054571628(53) × 10
−34
J s, onde a constante de Planck h = 6, 62606896(33) ×
10
−34
J s.
12
vetores µ tendem a rotacionar em torno desse eixo. O componente z de µ pode se
alinhar na mesma dire¸c˜ao que B
0
(I
z
= +
1
2
), ou na dire¸c˜ao oposta (I
z
= −
1
2
), sendo
que a primeira orienta¸c˜ao configura um estado de energia ligeiramente menor que
a segunda.
´
E gerada, portanto, em toda a amostra, uma desigualdade nos n´umeros
de n´ucleos em ambos os estados (J. B. Lambert e E. P. Mazzola, 2003), em uma
propor¸c˜ao dada por:
n
+
1
2
n
−
1
2
= exp
∆E
kT
(1.6)
onde n ´e a popula¸c˜ao de cada estado de spin, k ´e a constante de Boltzmann, T
´e a temperatura absoluta em Kelvin e ∆E ´e a diferen¸ca de energia entre os dois
estados.
O movimento precessional de µ em torno de z ocorre na freq
¨
uˆencia de Larmor,
que pode ser expressa como υ
0
ou como a freq
¨
uˆencia angular ω
0
, sendo que ω
0
=
2πυ
0
= γB
0
. A diferen¸ca de energia entre os dois estados de spin pode ser expressa
pela rela¸c˜ao ∆E = ω
0
, de modo que:
∆E = γB
0
(1.7)
Isto ´e, a energia necess´aria para que um pr´oton passe de um estado de spin
a outro ´e diretamente proporcional `a sua constante giromagn´etica (γ) e ao campo
el´etrico externo aplicado (B
0
). Em um experimento rmn, essa passagem de es-
tados ´e induzida por um segundo campo magn´etico, B
1
. Quando a freq
¨
uˆencia de
B
1
´e igual `a freq
¨
uˆencia de Larmor (ω
0
), o sistema absorve energia e passa ao es-
tado de equil´ıbrio, em que n
+
1
2
´e aproximadamente igual a n
−
1
2
, portanto os
componentes z de todos os vetores µ se anulam (J. B. Lambert e E. P. Mazzola,
2003).
Os diversos experimentos de rmn envolvem a aplica¸c˜ao de diferentes seq
¨
uˆen-
cias de pulso B
1
a diferentes intervalos de tempo. Cada tipo de experimento pode
obter informa¸c˜oes sobre a natureza e posi¸c˜ao dos n´ucleos, as quais s˜ao convertidas
em restri¸c˜oes de ˆangulos diedrais e distˆancias interatˆomicas.
13
1.3.1 Restri¸c˜oes de efeitos Overhauser nucleares (NOEs)
O experimento noesy (Nuclear Overhauser Effect Spectroscopy) mede a
transferˆencia de magnetiza¸c˜ao entre n´ucleos espacialmente pr´oximos, mas n˜ao nec-
essariamente diretamente ligados por poucas liga¸c˜oes covalentes. As restri¸c˜oes de
distˆancia obtidas atrav´es dos sinais (noes) desse tipo de experimento conectam
pares de pr´otons possivelmente distantes na seq
¨
uˆencia, mas pr´oximos no espa¸co
at´e uma distˆancia de 5
˚
A (P. G
¨
untert, 1998).
Essas restri¸c˜oes representam a informa¸c˜ao essencial que ser´a usada nas etapas
computacionais para se definir a estrutura secund´aria e terci´aria de uma prote´ına.
Na abordagem tradicional, assume-se que existe uma ´unica estrutura tridi-
mensional compat´ıvel simultaneamente com todas as restri¸c˜oes de noe. Trata-
mentos mais sofisticados podem levar em considera¸c˜ao a id´eia de que os resultados
de um experimento noesy representam uma m´edia no tempo de diversas confor-
ma¸c˜oes prot´eicas intercambi´aveis (A. E. Torda et al., 1989, 1990).
Uma vez que a presen¸ca de movimentos internos e o intercˆambio qu´ımico em
uma mol´ecula podem diminuir a for¸ca dos noes, seus efeitos n˜ao s˜ao geralmente
tratados como distˆancias interatˆomicas precisas, mas como limites superiores para
essas distˆancias. Pelo mesmo motivo, a ausˆencia de um noe n˜ao pode ser in-
terpretada como um limite inferior da distˆancia entre dois ´atomos (P. G
¨
untert,
1998).
1.3.2 Restri¸c˜oes de acoplamento escalar
N´ucleos ligados entre si por trˆes liga¸c˜oes covalentes exercem uma influˆen-
cia rec´ıproca sobre seus respectivos campos magn´eticos. Essa influˆencia pode ser
mensurada em experimentos de rmn, resultando na obten¸c˜ao da constante de
acoplamento
3
J entre esses n´ucleos.
A constante de acoplamento ´e importante para a resolu¸c˜ao de estruturas
porque est´a relacionada ao ˆangulo diedral θ formado pelos quatro ´atomos ligados
14
atrav´es das rela¸c˜oes de Karplus (M. Karplus, 1963):
3
J (θ) = A cos
2
θ + B cos θ + C (1.8)
Os parˆametros A, B e C foram determinados experimentalmente para v´arios
tipos de liga¸c˜oes (P. G
¨
untert, 1998). Em particular, as constantes de acopla-
mento tipicamente detect´aveis em experimentos de rmn para determina¸c˜ao de
estruturas de prote´ınas descrevem os ˆangulos φ (formados, na cadeia principal,
entre o carbono-α de um res´ıduo e o nitrogˆenio do res´ıduo anterior) e χ
1
(forma-
dos entre o carbono-α e o primeiro ´atomo da cadeia lateral, chamado carbono-β)
(Figura 1.7).
Figura 1.7:
ˆ
Angulos φ e χ
1
em uma cadeia polipept´ıdica.
1.3.3 Informa¸c˜oes estruturais
As restri¸c˜oes obtidas por rmn, isoladamente, n˜ao seriam suficientes para se
determinar a posi¸c˜ao de todos os ´atomos em uma prote´ına; ´e necess´ario tamb´em
o conhecimento bioqu´ımico de suas caracter´ısticas estruturais, como comprimento
e ˆangulos das liga¸c˜oes, quiralidades, grupos planares e informa¸c˜oes sobre repuls˜ao
est´erica, assim como sua seq
¨
uˆencia de amino´acidos (P. G
¨
untert, 1998). Todas
essas informa¸c˜oes devem ser de alguma forma incorporadas a um algoritmo que se
proponha a resolver estruturas de prote´ınas a partir de dados de rmn.
15
1.4 M´etodos Computacionais para Resolu¸c˜ao de Estruturas de
Prote´ınas a partir de Dados de RMN
1.4.1 Geometria de Distˆancia
As primeiras abordagens para o c´alculo de uma estrutura prot´eica a partir de
dados de rmn envolviam o uso de geometria de distˆancia (P. G
¨
untert, 1998), um
m´etodo matem´atico que se baseia no teorema de que, dados exatos valores para
todas as distˆancias entre um conjunto de pontos no espa¸co, ´e poss´ıvel determinar
as coordenadas cartesianas exatas para esses pontos de forma ´unica, exceto por
invers˜oes, transla¸c˜oes e rota¸c˜oes globais (L. M. Blumenthal, 1953; G. M. Crippen,
1977; G. M. Crippen e T. F Havel, 1988).
A aplicabilidade desse m´etodo, entretanto, ´e limitada pelo fato de que, em
rmn, disp˜oe-se de um conjunto incompleto de distˆancias que n˜ao s˜ao exatas, mas
descritas atrav´es de limites inferiores e superiores. Para que se possam usar as
restri¸c˜oes de distˆancia obtidas por rmn nos c´alculos de geometria de distˆancia,
geralmente inicializam-se todos os valores desconhecidos de limites superiores para
um valor alto, e todos os valores desconhecidos de limites inferiores para zero.
Ajustam-se, ent˜ao, os limites inferiores e superiores das distˆancias entre os pontos,
repetidamente, at´e que todas as combina¸c˜oes satisfa¸cam o teorema da desigual-
dade triangular
3
. Um conjunto completo de distˆancias ´e formado escolhendo-se
aleatoriamente, para cada distˆancia, um valor entre os limites inferior e superior.
A estrutura resultante da aplica¸c˜ao desse m´etodo geralmente ter´a o enovelamento
tridimensional correto, mas severamente distorcido (P. G
¨
untert, 1998). Alguns
m´etodos podem usar diferentes sele¸c˜oes aleat´orias de distˆancias na ´ultima etapa
da forma¸c˜ao do conjunto de pontos, para obter um grupo de conforma¸c˜oes aprox-
imadas que pode ser usado como ponto de partida para a aplica¸c˜ao de outros
algoritmos mais robustos.
Outras desvantagens da geometria de distˆancia incluem o fato de que esta
3
Teorema que afirma que, em um triˆangulo, o comprimento de cada lado ´e sempre inferior `a
soma do comprimento dos dois outros lados.
16
necessariamente ignora a informa¸c˜ao contida em restri¸c˜oes de ˆangulos diedrais e
n˜ao ´e capaz de diferenciar conforma¸c˜oes quirais distintas da mesma estrutura (P.
G
¨
untert, 1998).
1.4.2 O m´etodo da fun¸c˜ao de alvo vari´avel
O m´etodo da fun¸c˜ao de alvo vari´avel foi proposto por Braun e G¯o (1985)
como uma alternativa mais eficiente que os c´alculos de geometria de distˆancia para
o uso de restri¸c˜oes provenientes de dados experimentais de rmn. A id´eia b´asica do
algoritmo consiste em acomodar uma estrutura inicial aleat´oria em um conjunto
de restri¸c˜oes que, inicialmente, consiste apenas em distˆancias intra-residuais e que,
gradativamente, passa a abranger pares de ´atomos mais distantes na seq
¨
uˆencia, at´e
cobrir toda a prote´ına. Uma das principais vantagens computacionais do m´etodo ´e
o fato de trabalhar no espa¸co das coordenadas internas, ao inv´es das coordenadas
cartesianas.
Na implementa¸c˜ao original, apenas uma baixa porcentagem das conforma¸c˜oes
iniciais aleat´orias conseguia atingir estados finais com poucas viola¸c˜oes de re-
stri¸c˜oes, e era necess´ario repetir a execu¸c˜ao diversas vezes, at´e se atingir um con-
junto aceit´avel de estruturas com poucas viola¸c˜oes. A fun¸c˜ao de alvo vari´avel mais
comumente usada no programa diana (P. G
¨
untert e K. W
¨
uthrich, 1991), ante-
cessor do dyana (P. G
¨
untert et al., 1997), descrito adiante na se¸c˜ao 1.4.4, utiliza
como algoritmo de minimiza¸c˜ao o m´etodo do gradiente conjugado.
1.4.3 Resolu¸c˜ao de Prote´ınas por RMN como um Problema de
Otimiza¸c˜ao
De modo geral, em todos os m´etodos modernos, a resolu¸c˜ao de estruturas por
rmn ´e geralmente descrita como um problema de minimiza¸c˜ao de alguma varia¸c˜ao,
geralmente simplificada, da equa¸c˜ao (1.2), sob a atua¸c˜ao das restri¸c˜oes derivadas
de dados experimentais de rmn.
Entretanto, h´a uma considera¸c˜ao fundamental que diferencia esses proble-
17
mas da abordagem usual de problemas de otimiza¸c˜ao com restri¸c˜oes. Na maioria
dos problemas para os quais foram originalmente desenvolvidas as metodologias
descritas na se¸c˜ao 3.3, a solu¸c˜ao ´otima se encontra no espa¸co de busca restrito. O
objetivo desses algoritmos, portanto, ´e o de encontrar a melhor solu¸c˜ao poss´ıvel
dentro do espa¸co vi´avel, mesmo que esta esteja distante do ´otimo global, que seria
encontrado sem as restri¸c˜oes. Nesses casos, portanto, a solu¸c˜ao encontrada tende
a se localizar na fronteira entre as duas regi˜oes do espa¸co de busca.
Em contraste, as restri¸c˜oes obtidas atrav´es de experimentos rmn, quando
aplicadas ao problema de busca da estrutura prot´eica de menor energia, n˜ao mod-
ificam significativamente a posi¸c˜ao do ´otimo global no espa¸co de busca. Portanto,
ao inv´es de efetivamente limitarem a regi˜ao do espa¸co vi´avel, essas restri¸c˜oes tˆem
o papel de auxiliar o processo de busca do algoritmo em dire¸c˜ao ao ´otimo global.
Em praticamente todos os algoritmos j´a propostos para o problema, as re-
stri¸c˜oes s˜ao implementadas como fun¸c˜oes de penalidades (ver se¸c˜ao 3.3.2.1), que
s˜ao somadas a termos estruturais relevantes derivados de (1.2).
Independentemente do m´etodo computacional utilizado para se resolverem
as restri¸c˜oes experimentais de rmn, o resultado da maioria dos m´etodos modernos
geralmente n˜ao ´e uma ´unica estrutura final, mas um conjunto de estruturas, pr´ox-
imas entre si, que satisfazem as restri¸c˜oes experimentais com aproximadamente a
mesma completude.
A abordagem do problema de resolu¸c˜ao de estruturas por rmn como um
problema de otimiza¸c˜ao foi inicialmente popularizada pelos programas DISMAN
(G. Wagner et al., 1987) e diana (P. G
¨
untert e K. W
¨
uthrich, 1991), que utilizavam
o m´etodo de gradiente conjugado para uma fun¸c˜ao alvo que media a concordˆancia
entre uma dada conforma¸c˜ao e um conjunto de restri¸c˜oes experimentais e estrutu-
rais. Em ambos os programas, a quantidade de restri¸c˜oes utilizadas para se calcu-
lar a fun¸c˜ao a ser minimizada aumentava gradualmente ao longo da execu¸c˜ao. A
efic´acia desse m´etodo, entretanto, ´e limitada a algumas classes de prote´ınas que se
estabilizam principalmente por intera¸c˜oes de curto alcance (P. G
¨
untert, 1998).
18
Os programas dyana (P. G
¨
untert et al., 1997) / cyana (P. G
¨
untert, 2004) e
a fam´ılia de programas x-plor (A. T. Br
¨
unger, 1993) / cns (A.T. et al., 1998) / x-
Plor-NIH (C. D. Schwieters et al., 2003) representam atualmente os mais populares
e eficazes algoritmos de resolu¸c˜ao de estruturas por rmn. Ambos implementam
a minimiza¸c˜ao de uma fun¸c˜ao de energia atrav´es de varia¸c˜oes dos m´etodos de
simula¸c˜ao computacional da Dinˆamica Molecular (dm).
Os m´etodos de dm foram desenvolvidos originalmente com o objetivo de
simular t˜ao realisticamente quanto poss´ıvel o comportamento de um sistema f´ısico
real. Em programas de determina¸c˜ao de estrutura por rmn, entretanto, o objetivo
passa a ser o de simplesmente efetuar, no espa¸co de conforma¸c˜oes estruturais, uma
busca por estruturas fisicamente vi´aveis que atendam a todas as restri¸c˜oes exper-
imentalmente determinadas. Por esse motivo, quando aplicadas ao problema de
rmn, os m´etodos de dm costumam sofrer modifica¸c˜oes que incluem a simplifica¸c˜ao
do campo de for¸ca e o uso da t´ecnica de annealing, isto ´e, a aplica¸c˜ao de uma
alta temperatura no in´ıcio da execu¸c˜ao, seguida por sua progressiva redu¸c˜ao (P.
G
¨
untert, 1998).
1.4.4 DYANA
O programa DYANA (P. G
¨
untert et al., 1997), calcula estruturas tridi-
mensionais de prote´ınas a partir de restri¸c˜oes de distˆancia e ˆangulos de tor¸c˜ao
detectadas por rmn atrav´es de um processo de annealing no espa¸co de ˆangulos de
tor¸c˜ao (coordenadas internas). A fun¸c˜ao alvo ´e dada por:
E = w
0
c=u,l,v
w
c
(α,β)∈I
c
f
c
(d
αβ
, b
αβ
) + w
d
k∈I
d
1 −
1
2
∆
k
Γ
k
2
∆
2
k
(1.9)
onde w
0
= 10 kJ mol
−1
˚
A
−2
´e uma constante; u, l e v se referem `as restri¸c˜oes
que imp˜oem, respectivamente, limites superiores, inferiores e de Van der Waals `as
distˆancias interatˆomicas; w
u
, w
l
, w
v
e w
d
s˜ao fatores de peso ajustados para cada
tipo de restri¸c˜ao; d
αβ
e b
αβ
s˜ao, respectivamente, as distˆancias encontradas e as
19
restri¸c˜oes de distˆancia para dois ´atomos α e β.
A fun¸c˜ao f
c
(d, b) mede a contribui¸c˜ao de uma viola¸c˜ao de distˆancia para a
fun¸c˜ao alvo e pode assumir trˆes formas distintas. A primeira vers˜ao (Equa¸c˜ao 1.10)
´e mantida por compatibilidade com diana (P. G
¨
untert e K. W
¨
uthrich, 1991), o
programa antecessor do dyana:
f
c
(d, b) =
d
2
− b
2
2b
(1.10)
A segunda vers˜ao (Equa¸c˜ao 1.11) ´e usada comumente para o c´alculo de pe-
nalidades para pequenas viola¸c˜oes:
f
c
(d, b) = (d − b)
2
(1.11)
A terceira vers˜ao (Equa¸c˜ao 1.12) ´e uma fun¸c˜ao com uma ass´ımptota linear,
que limita as penalidades associadas a viola¸c˜oes elevadas:
f
c
(d, b) = 2β
2
b
2
1 +
d − b
βb
2
− 1
(1.12)
onde β ´e um parˆametro adimensional que regula o peso dado a altas viola¸c˜oes de
restri¸c˜oes em rela¸c˜ao a baixas viola¸c˜oes.
As restri¸c˜oes de ˆangulos torcionais tˆem a forma de intervalos permitidos
[θ
max
k
, θ
min
k
] , sendo que Γ
k
= π − (θ
max
k
− θ
min
k
) /2 indica a metade da distˆancia
proibida de valores de ˆangulos de tor¸c˜ao, e ∆
k
´e o tamanho da viola¸c˜ao de restri¸c˜ao
de ˆangulo torcional.
O protocolo-padr˜ao de sa utilizado pelo dyana segue as seguintes etapas (P.
G
¨
untert e K. W
¨
uthrich, 1991):
(1) Uma conforma¸c˜ao inicial ´e criada, atribuindo-se valores aleat´orios para
todos os ˆangulos torcionais.
(2) Excluem-se todos os ´atomos de hidrogˆenio das verifica¸c˜oes de colis˜oes es-
20
t´ericas. Ajustam-se os valores dos raios de Van der Waals de todos os
´atomos ligados a ´atomos de hidrogˆenio, de modo a aproximar os resulta-
dos aos que seriam obtidos com uma representa¸c˜ao expl´ıcita de todos os
´atomos.
(3) Executam-se 100 passos de minimiza¸c˜ao com gradiente conjugado, in-
cluindo apenas res´ıduos distantes na seq
¨
uˆencia em at´e 3 posi¸c˜oes, depois
mais 100 passos, incluindo todos os res´ıduos no c´alculo da energia.
(4)
1
/5 do n´umero de passos de Dinˆamica Molecular especificados pelo usu´ario
s˜ao executados em um ambiente de alta temperatura T
alta
.
(5) Os
4
/5 passos restantes da dm s˜ao executados `a temperatura de referˆencia
T
ref
(s) = (1 − s)
4
T
alta
, onde s varia linearmente de 0 a 1 ao longo desta
etapa.
(6) Incluem-se todos os ´atomos nos c´alculos de colis˜ao est´erica, atribuindo no-
vamente os valores-padr˜ao aos raios de Van der Waals de todos os ´atomos.
Executam-se 100 passos de minimiza¸c˜ao com gradiente conjugado.
(7) Executam-se mais 200 passos de Dinˆamica Molecular `a temperatura de
referˆencia zero.
(8) Executam-se mais 1000 passos de minimiza¸c˜ao com gradiente conjugado,
incluindo todas as restri¸c˜oes.
1.4.5 X-PLOR/CNS/XPLOR-NIH
Os programas x-plor (A. T. Br
¨
unger, 1993) e seus derivados cns (A.T.
et al., 1998) e xplor-nih (C. D. Schwieters et al., 2003) tˆem sido altamente pop-
ulares em estudos de determina¸c˜ao de estruturas de prote´ınas atrav´es de rmn ou
cristalografia.
A fun¸c˜ao alvo do x-plor ´e dividida em duas categorias (A. T. Br
¨
unger,
21
1993):
E = E
EM P IRICA
+ E
EF ET IV A
(1.13)
Sendo que a parte emp´ırica da energia (E
EM P RICA
) ´e calculada a partir de um
campo de for¸ca parametrizado (o x-plor disponibiliza por padr˜ao v´arias vers˜oes do
charmm (Bernard R. Brooks et al., 1983) e do amber/OPLS (Jorgensen e Tirado-
Rives, 1988)). Diversas op¸c˜oes est˜ao dispon´ıveis para todos os seus termos, de
acordo com o campo de for¸ca escolhido e a sele¸c˜ao de diversos parˆametros, conforme
descrito detalhadamente em A. T. Br
¨
unger (1993). A parte efetiva (E
EF ET IV A
)
cont´em os termos derivados de dados experimentais e pode ser considerada uma
fun¸c˜ao de penalidade:
E
EF ET IV A
= E
NOE
+ E
CDIH
(1.14)
onde E
NOE
se refere `as restri¸c˜oes de distˆancias, e E
CDIH
, `as restri¸c˜oes de ˆangulos
diedrais. O X-PLOR disponibiliza diferentes classes de restri¸c˜oes de distˆancias, as
quais utilizam diferentes fun¸c˜oes de avalia¸c˜ao.
´
E poss´ıvel que, na mesma prote´ına,
existam distˆancias pertencentes a classes diferentes, de modo que o termo E
NOE
´e
a soma de todas as distˆancias pertencentes a todas as classes:
E
NOE
=
classes
restries
E
classe
NOE
(1.15)
Dentre as classes que definem E
classe
NOE
, destacam-se duas de uso mais geral.
1. A fun¸c˜ao bi-harmˆonica:
E
classe
NOE
= min
ceil,
SK
b
T
2c
2
ij
(r-d)
2
(1.16)
onde
c
ij
=
d
minus
se R < d
d
plus
se R > d
(1.17)
22
2. A fun¸c˜ao quadr´atica:
E
classe
NOE
= min (ceil, SC) ∆
exp
(1.18)
onde
∆ =
R − (d + d
plus
− d
off
) , se d + d
plus
− d
off
< R
0 , se d − d
minus
< R < d + d
plus
− d
off
(d − d
minus
− R) , se R < d − d
minus
(1.19)
Em ambos os casos, S, C, ceil e d
off
s˜ao constantes definidas pelo usu´ario,
T ´e a temperatura, R ´e a distˆancia encontrada entre dois ´atomos, d ´e o valor da
respectiva restri¸c˜ao de distˆancia, d
minus
´e a margem de erro inferior para a restri¸c˜ao,
e d
plus
, a margem de erro superior.
O termo E
CDIH
´e definido por:
E
CDIH
= S
Cwell(modulo
2π
(φ − φ
0
), ∆φ)
ed
(1.20)
onde
well(a, b) =
a − b , se a > b
0 , se − b < a < b
a + b , se a < −b
(1.21)
em que ∆ e ed s˜ao constantes especificadas com as restri¸c˜oes.
O x-plor e seus derivados fornecem ao usu´ario v´arios m´etodos alternativos
para determinar e refinar as estruturas de prote´ınas a partir de dados experimen-
tais de rmn. S˜ao disponibilizados protocolos para cria¸c˜ao de estruturas-modelo a
partir de topologias predefinidas, resolu¸c˜ao parcial e total de estruturas por geome-
tria de distˆancia, e annealing, entre outros. Todos os protocolos dispon´ıveis s˜ao
implementados como arquivos de script facilmente extens´ıveis e personaliz´aveis.
Para a maioria dos casos, os autores recomendam que se use a seguinte
seq
¨
uˆencia de etapas:
23
(1) Gera¸c˜ao de uma estrutura-modelo correspondente `a seq
¨
uˆencia de amino´a-
cidos da prote´ına-alvo. Este modelo, que deve servir como ponto inicial
para as etapas seguintes, ´e gerado a partir de topologias padronizadas para
cada amino´acido, inclu´ıdas no x-plor.
(2) Execu¸c˜ao do protocolo de geometria de distˆancia de sub-estruturas.
(3) Regulariza¸c˜ao das sub-estruturas geradas pela geometria de distˆancia atrav´es
de sa.
(4) Refinamento da estrutura completa por meio de sa.
O x-plor tamb´em inclui uma s´erie de protocolos de sa desenvolvidos para o refi-
namento de estruturas – os quais funcionam de maneira independente dos demais
protocolos, e tamb´em podem ser usados refinar para estruturas geradas por outros
programas.
1.5 Predi¸c˜ao de Estruturas de Prote´ınas
A obten¸c˜ao de estruturas de prote´ınas a partir de dados de experimentais
de rmn pode ser visto como um caso particular de uma ´area de estudo mais
ampla, a predi¸c˜ao das estruturas nativas de prote´ınas, que ´e um dos desafios mais
importantes da biologia computacional moderna.
O desenvolvimento de uma metodologia computacional que permita inferir
de maneira precisa a estrutura nativa de uma prote´ına a partir de sua seq
¨
uˆen-
cia prim´aria vem sendo continuamente buscado por grupos de pesquisa de todo
o mundo. A evolu¸c˜ao das t´ecnicas resultantes destes esfor¸cos s˜ao testadas bi-
anualmente na competi¸c˜ao casp (Critical assessment of methods of protein struc-
ture prediction). Os m´etodos de predi¸c˜ao de estruturas de prote´ınas se dividem
em duas classes principais: modelagem por homologia e ab initio. M´etodos per-
tencentes a qualquer uma dessas classes podem ser adaptados e estendidos para o
uso de dados experimentais de rmn.
24
1.5.1 Modelagem por homologia, ou modelagem comparativa
M´etodos de modelagem por homologia, ou modelagem comparativa utilizam,
al´em da seq
¨
uˆencia prim´aria da prote´ına a ser determinada, informa¸c˜oes prove-
nientes de uma ou mais estruturas experimentais j´a determinadas de prote´ınas
hom´ologas `aquela. O funcionamento das t´ecnicas de modelagem comparativa parte
da observa¸c˜ao de que, durante o processo evolutivo, a seq
¨
uˆencia de amino´acidos
de uma prote´ına tipicamente se altera mais rapidamente que sua estrutura tridi-
mensional, devido ao fato de que muitas das muta¸c˜oes que se fixam no genoma
envolvem a substitui¸c˜ao, adi¸c˜ao ou dele¸c˜ao de amino´acidos que n˜ao alteram signi-
ficativamente a estrutura e funcionamento da prote´ına expressa (
ˇ
Sali e Blundell,
1993).
O processo de modelagem por homologia consiste em quatro etapas (Baker
e
ˇ
Sali, 2001): (1) Busca de estruturas conhecidas (chamadas moldes) relacionadas
`a prote´ına-alvo; (2) alinhamento da seq
¨
uˆencia da prote´ına-alvo com as seq
¨
uˆencias
dos moldes; (3) constru¸c˜ao do modelo; (4) avalia¸c˜ao do modelo. A precis˜ao de
um modelo gerado por homologia est´a relacionada `a percentagem de identidade
de seq
¨
uˆencia na qual ele ´e baseado. Modelos comparativos de precis˜ao de at´e 1
˚
A
podem ser obtidos com o uso de seq
¨
uˆencias molde com identidade de ao menos
50% em rela¸c˜ao `a seq
¨
uˆencia-alvo (Baker e
ˇ
Sali, 2001).
1.5.1.1 MODELLER
O software modeller (
ˇ
Sali e Blundell, 1993) ´e a ferramenta de modelagem
por homologia mais comumente utilizada atualmente. O modeller ´e capaz de
obter modelos tridimensionais para a seq
¨
uˆencia desejada atrav´es da otimiza¸c˜ao da
satisfa¸c˜ao de restri¸c˜oes espaciais derivadas de seu alinhamento com estruturas rela-
cionadas. Essas restri¸c˜oes s˜ao expressas como fun¸c˜oes densidade de probabilidade.
Uma fun¸c˜ao densidade de probabilidade p(x), por defini¸c˜ao, ´e sempre n˜ao-negativa
e tem a propriedade:
+∞
−∞
p(x)dx = 1 (1.22)
25
A fun¸c˜ao p(x) define a probabilidade de um evento x
1
≤ x < x
2
atrav´es da
sua integra¸c˜ao:
p(x
1
≤ x < x
2
) =
x
2
x
1
p(x)dx (1.23)
As fun¸c˜oes densidade de probabilidade usadas pelo modeller s˜ao sempre
condicionais, isto ´e, especifica-se p(x|a, b, . . . , c) como a fun¸c˜ao densidade de p(x)
desde que sejam verdadeiras todas as express˜oes a, b, . . . , c. Tipicamente, x pode
ser, por exemplo, um valor para um ˆangulo χ
1
, e as condi¸c˜oes podem se referir
ao tipo de res´ıduo em que ele se encontra, os ˆangulos φ e ψ que ele forma com
os res´ıduos vizinhos, estruturas secund´arias, distˆancia Cα-Cα, acessibilidade do
res´ıduo ao solvente, entre outras.
Um banco de dados local de estruturas extra´ıdas do pdb foi constru´ıdo com
membros de 17 fam´ılias de prote´ınas e utilizado para construir um conjunto de
fun¸c˜oes densidade de probabilidade a partir da freq
¨
uˆencia relativa das diversas
condi¸c˜oes e ocorrˆencias. Fun¸c˜oes densidade tamb´em s˜ao geradas a partir dos alin-
hamentos fornecidos pelo usu´ario entre a seq
¨
uˆencia-alvo e as estruturas moldes.
O objetivo do algoritmo de modelagem da estrutura-alvo pelo modeller ´e
obter a estrutura mais consistente com todas as restri¸c˜oes espaciais descritas pelas
fun¸c˜oes densidade de probabilidade. A solu¸c˜ao para esse problema ´e buscada pela
combina¸c˜ao de todas as fun¸c˜oes em uma ´unica fun¸c˜ao densidade. A otimiza¸c˜ao
dessa fun¸c˜ao equivale `a minimiza¸c˜ao das restri¸c˜oes estabelecidas para o modelo.
O modeller utiliza como algoritmo de otimiza¸c˜ao a fun¸c˜ao de alvo vari´avel
(Braun e G¯o, 1985) com gradiente conjugado para a posi¸c˜ao de todos os ´atomos
n˜ao-hidrogˆenio. A conforma¸c˜ao inicial da prote´ına ´e aleat´oria. Inicialmente, s˜ao
usadas apenas as restri¸c˜oes que envolvem res´ıduos pr´oximos na seq
¨
uˆencia. Grada-
tivamente, restri¸c˜oes referentes a distˆancias maiores s˜ao inclu´ıdas no c´alculo de
minimiza¸c˜ao.
26
1.5.2 Predi¸c˜ao ab initio
O problema da previs˜ao da estrutura nativa de uma prote´ına apenas a par-
tir do conhecimento de sua seq
¨
uˆencia prim´aria, sem o aux´ılio de estruturas de
referˆencia pr´e-determinadas, ´e um dos maiores desafios atuais da Biologia Com-
putacional. M´etodos que seguem essa abordagem s˜ao conhecidos como m´etodos
ab initio, ou de previs˜ao de estruturas por primeiros princ´ıpios. A caracteriza¸c˜ao
do que constitui um m´etodo ab initio puro nem sempre pode ser feita de maneira
precisa: alguns dos m´etodos mais bem sucedidos que s˜ao assim classificados, como
o Rosetta (Simons et al., 1999) e o i-tasser (Zhang, 2007), fazem uso extensivo
de informa¸c˜oes oriundas de estruturas de prote´ınas j´a conhecidas.
1.5.2.1 Rosetta
O software para predi¸c˜ao de estruturas ab initio Rosetta (Bonneau et al.,
2001) foi o mais bem-sucedido no casp4, realizado no ano 2000. O m´etodo do
Rosetta se baseia no pressuposto de que a distibui¸c˜ao de conforma¸c˜oes amostrada
por um segmento local da cadeia polipet´ıdica pode ser aproximado pela distribui¸c˜ao
de estruturas adotadas por aquela seq
¨
uˆencia, assim como por seq
¨
uˆencias rela-
cionadas, em outras estruturas conhecidas (Bonneau et al., 2001). O Rosetta
utiliza o conceito de biblioteca de fragmentos: um conjunto formado por cadeias
pept´ıdicas em todas as poss´ıveis combina¸c˜oes de seq
¨
uˆencias de 3 e 9 res´ıduos, com
estruturas extra´ıdas a partir de prote´ınas depositadas no pdb. A explora¸c˜ao do
espa¸co de busca ´e realizada atrav´es de um procedimento Monte Carlo que favorece
estruturas compactas com folhas-β pareadas e res´ıduos hidrof´obicos enterrados.
Para cada seq
¨
uˆencia-alvo, o Rosetta realiza 1.000 simula¸c˜oes independentes. As
estruturas resultantes s˜ao agrupadas por similaridade e ordenadas de acordo com
o tamanho do grupo que representam, sendo o centro do grupo definido como a
estrutura de maior confian¸ca (Bonneau et al., 2001).
Bowers et al. (2000) apresentam uma varia¸c˜ao do Rosetta, a qual utiliza
dados provenientes de experimentos de nmr para aprimorar tanto o processo de
27
sele¸c˜ao dos fragmentos, quanto a identifica¸c˜ao de estruturas consistentes com o
enovelamento nativo. Os dados de rmn usados nos testes realizados pelos autores
foram aqueles tidos como os mais facilmente obtidos experimentalmente: restri¸c˜oes
de distˆancia noe da cadeia principal HN-HN e deslocamentos qu´ımicos. Os dados
de deslocamentos qu´ımicos s˜ao traduzidos em ˆangulos φ e ψ com o aux´ılio da ferra-
menta talos (Cornilescu et al., 1999). Todas essas informa¸c˜oes foram integradas
aos m´etodos j´a existentes de estrat´egias de sele¸c˜ao de fragmentos, e a fun¸c˜ao ob-
jetivo do Rosetta foi modificada com a adi¸c˜ao de um termo de restri¸c˜oes noe. O
m´etodo foi testado pelos autores em um conjunto de 9 estruturas, utilizando, para
cada uma, uma quantidade reduzida de restri¸c˜oes de longo e curto alcance. Foram
utilizadas tanto restri¸c˜oes reais (obtidas experimentalmente) quanto artificiais (ex-
tra´ıdas do conhecimento da estrutura final). Os valores de rmsd obtidos entre
entre as melhores estruturas geradas por essa metodologia e aquelas depositadas
no pdb variaram entre 1.34
˚
A e 7.98
˚
A (Bowers et al., 2000)
28
Cap´ıtulo 2
Objetivos
O objetivo deste trabalho ´e desenvolver uma vers˜ao do Algoritmo Gen´etico
de M´ultiplos M´ınimos implementado por Cust´odio (2008) adaptada ao problema de
resolu¸c˜ao de uma estrutura prot´eica a partir de sua seq
¨
uˆencia de amino´acidos e de
dados experimentais oriundos de experimentos de Ressonˆancia Magn´etica Nuclear.
2.1 Objetivos Espec´ıficos
Criar uma nova vers˜ao das topologias do gromos96 utilizadas no algo-
ritmo original, para incluir a representa¸c˜ao expl´ıcita de todos os ´atomos
de hidrogˆenio.
Desenvolver um mecanismo para leitura de arquivos que descrevem re-
stri¸c˜oes de rmn e incorporar essas restri¸c˜oes `a estrutura existente do pro-
grama.
Modificar a fun¸c˜ao de aptid˜ao do ag, para que este leve em considera¸c˜ao,
em cada indiv´ıduo, a viola¸c˜ao das restri¸c˜oes de rmn.
Desenvolver e testar diversas metodologias alternativas que implementem
varia¸c˜oes ao Algoritmo Gen´etico de M´ultiplos M´ınimos. Pesquisar as de-
mais modifica¸c˜oes que podem ser necess´arias em todas as etapas da al-
goritmo, de modo a maximizar a efic´acia do uso das novas informa¸c˜oes
incorporadas.
29
Validar o software desenvolvido, atrav´es da compara¸c˜ao com o desempenho
de outras solu¸c˜oes existentes.
30
Cap´ıtulo 3
Algoritmos Gen´eticos
3.1 Sele¸c˜ao Natural e Evolu¸c˜ao
3.1.1 A Origem das Esp´ecies
O ano de 1859 marca, na hist´oria da ciˆencia, a primeira descri¸c˜ao do princ´ı-
pio fundamental respons´avel pela origem de toda a diversidade da vida no plan-
eta Terra. A publica¸c˜ao de A Origem das Esp´ecies, pelo naturalista britˆanico
Charles Darwin, apresenta a solu¸c˜ao para um enigma que, at´e ent˜ao, permanecia
sem solu¸c˜ao cient´ıfica: que mecanismo natural poderia ser respons´avel pelo surgi-
mento, na natureza, de m´aquinas t˜ao complexas e eficientemente otimizadas para
a sobrevivˆencia e reprodu¸c˜ao, como s˜ao os seres vivos?
Darwin chegou `a resposta a essa pergunta ap´os v´arios anos de cuidadosa
observa¸c˜ao do mundo natural em sua carreira como naturalista, particularmente
em sua viagem ao redor do globo a bordo do navio HMS Beagle, entre 1831 e 1836.
O primeiro ponto da teoria de Darwin ´e a observa¸c˜ao de que todas as esp´e-
cies tˆem uma capacidade reprodutiva de crescimento potencialmente geom´etrico.
Entretanto, os recursos naturais `a disposi¸c˜ao dos seres vivos s˜ao limitados, e a
maioria das popula¸c˜oes biol´ogicas tende a se manter em n´umeros mais ou menos
est´aveis, contrariando esse potencial, pois, em qualquer esp´ecie, a maioria dos in-
div´ıduos morre antes de atingir a idade reprodutiva. Darwin observou que, na
natureza, ocorre uma luta constante pela sobrevivˆencia, e que a probabilidade de
cada indiv´ıduo atingir a idade reprodutiva pode estar diretamente relacionada a
31
sutis diferen¸cas entre sua constitui¸c˜ao e a de outros membros da mesma esp´ecie.
O segundo ponto da teoria prov´em da constata¸c˜ao de que muitas das carac-
ter´ısticas particulares de cada indiv´ıduo s˜ao herdadas e passadas para as pr´oximas
gera¸c˜oes. Entretanto, Darwin tamb´em observou que novas caracter´ısticas podem
surgir espontaneamente em novos indiv´ıduos, sem que sejam herdadas de qualquer
um dos seus pais, e passadas para as gera¸c˜oes seguintes. Esses eventos, chamados
de muta¸c˜oes, s˜ao aleat´orios, e s˜ao uma importante fonte de varia¸c˜ao nas popu-
la¸c˜oes. Uma segunda fonte de varia¸c˜ao ´e a reprodu¸c˜ao sexuada, em que um novo
indiv´ıduo ´e gerado com caracter´ısticas herdadas de dois indiv´ıduos parentais. Ao
longo das gera¸c˜oes, quaisquer novas caracter´ısticas que aumentem a probabilidade
de sobrevivˆencia dos indiv´ıduos tendem a se espalhar e se tornar dominantes na
popula¸c˜ao, enquanto caracter´ısticas prejudiciais tendem a desaparecer. Esse pro-
cesso foi chamado por Darwin de sele¸c˜ao natural.
O efeito acumulativo da sele¸c˜ao natural pode ser extremamente poderoso
no longo prazo, moldando em popula¸c˜oes organismos cada vez mais complexos e
melhor adaptados a seus respectivos ambientes, e levando ao surgimento de no-
vas esp´ecies. Em seu livro, Darwin ilustrou todos os aspectos de sua teoria com
observa¸c˜oes e exemplos fatuais, e antecipou e respondeu poss´ıveis cr´ıticas. Os
exemplares das primeiras edi¸c˜oes de A Origem das Esp´ecies se esgotaram rapida-
mente ap´os a publica¸c˜ao, e houve ampla aceita¸c˜ao de suas id´eias pela comunidade
cient´ıfica da ´epoca, apesar da controv´ersia suscitada por suas poss´ıveis implica¸c˜oes
filos´oficas. Desde ent˜ao, avan¸cos de todas as ´areas das ciˆencias Biol´ogicas, como
a Gen´etica e os estudos de anatomia e fisiologia comparadas, al´em das descober-
tas da Geologia e Paleontologia, tˆem comprovado e refinado a teoria proposta por
Darwin, que hoje ´e considerada a base te´orica de toda a Biologia moderna.
3.1.2 A Nova S´ıntese
Entre as descobertas cient´ıficas que contribu´ıram para a consolida¸c˜ao e ex-
pans˜ao das id´eias de Darwin no s´eculo xx, os avan¸cos da Gen´etica de Popula¸c˜oes
32
e da Gen´etica Molecular foram de especial importˆancia. Pode-se considerar que
os mecanismos da heran¸ca gen´etica nos seres vivos come¸caram a ser desvendados
em 1866, com a publica¸c˜ao dos experimentos com linhagens de ervilhas realiza-
dos pelo monge austr´ıaco Gregor Mendel. Entretanto, o trabalho de Mendel foi
largamente ignorado em sua ´epoca, e suas id´eias s´o come¸caram a repercutir na
comunidade cient´ıfica a partir da redescoberta de sua obra no ano de 1900. Di-
versas observa¸c˜oes e experimentos realizados pela comunidade cient´ıfica nos anos
seguintes culminaram na chamada“nova s´ıntese” da teoria da evolu¸c˜ao, que formou
os fundamentos do entendimento moderno do processo evolutivo.
Hoje se sabe que a informa¸c˜ao gen´etica nos seres vivos est´a armazenada em
suas c´elulas em mol´eculas de dna. Em organismos multicelulares e em certas
categorias de organismos unicelulares, o dna no interior das c´elulas ´e armazenado
em estruturas chamadas cromossomos. Cada cromossomo ´e formado por uma
longa mol´ecula cont´ınua de dna, ligado a prote´ınas que o estabilizam e regulam
suas fun¸c˜oes.
A informa¸c˜ao contida no dna ´e digital, isto ´e, pode ser lida como uma s´erie
de s´ımbolos discretos. Na Gen´etica moderna, distingue-se o gen´otipo de um in-
div´ıduo, que ´e o conjunto de suas seq
¨
uˆencias de dna, de seu fen´otipo, que ´e a
conseq
¨
uˆencia observada do gen´otipo. Exemplos de tra¸cos do fen´otipo abrangem
da estrutura de uma prote´ına `a colora¸c˜ao das penas de uma ave. O processo de
sele¸c˜ao natural necessariamente atua no fen´otipo: s˜ao as caracter´ısticas f´ısicas que
diferenciam um organismo mais apto de um menos apto, e n˜ao, diretamente, seus
genes. Entretanto, essas caracter´ısticas s˜ao freq
¨
uentemente produtos dos genes,
e apenas os genes s˜ao passados para as pr´oximas gera¸c˜oes. Essa distin¸c˜ao, de-
sconhecida na ´epoca de Darwin, ´e fundamental para a compreens˜ao de diversos
fenˆomenos evolutivos.
Um gene pode ser definido como um fragmento do cromossomo que codifica
uma fun¸c˜ao observ´avel no fen´otipo do organismo. Diferentes varia¸c˜oes de um
mesmo gene, ou seja, diferentes possibilidades de seq
¨
uˆencias de dna que podem
33
ocupar a mesma posi¸c˜ao, s˜ao chamadas alelos.
O conceito de deriva gˆenica, introduzido pelo geneticista americano Sewall
Wright na d´ecada de 1920, esclareceu outro importante fator-chave do processo
evolutivo. A deriva gˆenica ´e uma for¸ca evolutiva que resulta na mudan¸ca da fre-
q
¨
uˆencia dos gen´otipos entre diferentes gera¸c˜oes, de maneira independente da in-
fluˆencia do processo de sele¸c˜ao natural. Devido ao fenˆomeno estat´ıstico do desvio
de amostragem, ´e poss´ıvel que aconte¸ca, principalmente em popula¸c˜oes pequenas,
que o subconjunto dos indiv´ıduos de uma popula¸c˜ao que consegue se reproduzir
tenha, por um acaso, uma freq
¨
uˆencia genot´ıpica diferente daquela da popula¸c˜ao
total. Nesse caso, os alelos mais freq
¨
uentes nesse subconjunto tender˜ao a am-
pliar sua freq
¨
uˆencia na popula¸c˜ao em geral, sem que necessariamente estes tragam
qualquer benef´ıcio aos indiv´ıduos que o carregam. De maneira an´aloga, o mesmo
processo pode levar ao desaparecimento de alelos que n˜ao seriam necessariamente
desfavorecidos pela sele¸c˜ao natural.
3.2 Algoritmos Gen´eticos
O fenˆomeno da evolu¸c˜ao biol´ogica n˜ao demorou a chamar a aten¸c˜ao de
pesquisadores envolvidos na ent˜ao recente ´area de pesquisa das Ciˆencias da Com-
puta¸c˜ao, e serviu de inspira¸c˜ao para o desenvolvimento de diversas classes de algo-
ritmos, comumente agrupados na ´area de Computa¸c˜ao Evolucionista (ce). Dentre
os diversos tipos de algoritmos evolucion´arios, destaca-se uma classe particular
conhecida como algoritmos gen´eticos (ag). Algoritmos gen´eticos foram propos-
tos pela primeira vez por Holland (1975) e tˆem sido aplicados desde ent˜ao, com
sucesso, em uma gama crescente de problemas em diversas ´areas do conhecimento
humano.
Um algoritmo gen´etico pode ser descrito como uma t´ecnica de busca com-
putacional para se encontrarem solu¸c˜oes ´otimas ou aproximadas para problemas de
otimiza¸c˜ao. Um problema de otimiza¸c˜ao consiste no problema da minimiza¸c˜ao de
uma fun¸c˜ao f(x), onde x ∈ Ω ´e um vetor de vari´aveis de decis˜ao. Isto ´e, busca-se o
34
valor de x para o qual f(x) tenha o menor valor poss´ıvel. Ω ´e o espa¸co das solu¸c˜oes
fact´ıveis, tamb´em conhecido como espa¸co de busca. O espa¸co de busca pode ser
conceitualizado como uma superf´ıcie de m´ultiplas dimens˜oes (hipersuperf´ıcie), e os
poss´ıveis valores de f(x), como pontos nessa hipersuperf´ıcie.
Algoritmos gen´eticos lidam com o conceito de popula¸c˜oes formadas por in-
div´ıduos. Cada indiv´ıduo representa um valor para x, isto ´e, um ponto no espa¸co
de busca, o qual equivale uma poss´ıvel solu¸c˜ao para o problema proposto. Assim
como em popula¸c˜oes biol´ogicas, cada indiv´ıduo possui um gen´otipo e um fen´otipo.
O gen´otipo ´e uma estrutura de dados simples, quase sempre linear, formada por
uma seq
¨
uˆencia de s´ımbolos discretos, que representa o indiv´ıduo. A representa¸c˜ao
computacional do gen´otipo ´e conhecida como cromossomo. Tradicionalmente, o
cromossomo ´e codificado como uma cadeia bin´aria, isto ´e, uma seq
¨
uˆencia de s´ım-
bolos 0 e 1. Outras representa¸c˜oes podem ser usadas, de acordo com a natureza do
problema, mas, quase sempre, o cromossomo ´e definido como algum tipo de cadeia,
isto ´e, uma estrutura formada por uma seq
¨
uˆencia linear de dados. O fen´otipo de
um indiv´ıduo ´e determinado a partir do gen´otipo, e ´e definido como a estrutura de
dados mais conveniente para que se realize o c´alculo da aptid˜ao do indiv´ıduo, isto
´e, o valor de f(x), que se deseja minimizar. No caso mais simples, o fen´otipo pode
ser simplesmente o n´umero, inteiro ou de ponto flutuante, representado pela cadeia
bin´aria do gen´otipo. Para muitos problemas, entretanto, o fen´otipo costuma ser
definido como uma estrutura mais complexa, constru´ıda a partir das instru¸c˜oes
codificadas no gen´otipo.
O fato de os Algoritmos Gen´eticos, ao contr´ario do que ocorre em muitos
outros m´etodos de otimiza¸c˜ao, dispensarem o uso de informa¸c˜oes sobre o gradiente
da fun¸c˜ao objetivo, contribui para torn´a-los especialmente robustos e extensamente
aplic´aveis. ags tˆem sido utilizados com sucesso em diversas categorias de proble-
mas que s˜ao dif´ıceis ou imposs´ıveis de se tratar com m´etodos convencionais.
Em um ag, uma popula¸c˜ao ´e definida como um conjunto de indiv´ıduos,
representados por seus gen´otipos. Por conveniˆencia, costuma-se armazenar, junto
35
a cada gen´otipo, o valor de sua aptid˜ao (que ´e calculado a partir do fen´otipo
correspondente). Os valores iniciais dos indiv´ıduos da popula¸c˜ao s˜ao geralmente
aleat´orios. O objetivo do algoritmo gen´etico ´e simular os eventos que constituem
o processo de sele¸c˜ao natural, de modo a conduzir a popula¸c˜ao a ser formada por
indiv´ıduos com valores de aptid˜ao cada vez melhores. O processo geral percorrido
pela execu¸c˜ao de uma algoritmo gen´etico ´e descrito na figura 3.1.
1. Inicializar os indiv´ıduos da popula¸c~ao.
2. Repita:
2.1. Selecionar indiv´ıduos para reprodu¸c~ao.
2.2. Aplicar operadores gen´eticos.
2.3. Avaliar os novos indiv´ıduos.
2.4. Incorporar os novos indiv´ıduos `a popula¸c~ao.
At´e o crit´erio de parada ser satisfeito.
3. Fim.
Figura 3.1: Descri¸c˜ao geral de um algoritmo gen´etico.
O la¸co principal do algoritmo ´e executado at´e que seja atingido um crit´erio
de parada previamente especificado.
´
E comum utilizar como crit´erio de parada um
n´umero fixo de intera¸c˜oes ou a satisfa¸c˜ao de alguma condi¸c˜ao sobre a fun¸c˜ao de
aptid˜ao.
3.2.1 Popula¸c˜ao inicial
O tamanho e composi¸c˜ao da popula¸c˜ao inicial em um ag pode ser um dos
fatores mais importantes na determina¸c˜ao do seu sucesso. Popula¸c˜oes muito peque-
nas devem ser evitadas por serem mais suscet´ıveis ao efeito de deriva gˆenica, que
pode resultar na fixa¸c˜ao prematura de alelos independentemente do seu potencial
de aptid˜ao, prejudicando o desempenho do algoritmo. Al´em disso, a explora¸c˜ao
adequada do espa¸co de busca pode n˜ao ser poss´ıvel em uma popula¸c˜ao de tamanho
reduzido. Por outro lado, um algoritmo que lide com uma popula¸c˜ao muito grande
pode se tornar invi´avel devido ao tempo que levaria para chegar a uma solu¸c˜ao.
A escolha do tamanho da popula¸c˜ao em um ag costuma ser guiada, portanto, por
36
uma escolha de melhor balan¸co entre efic´acia e eficiˆencia (Reeves e Rowe, 2003).
A abordagem tradicional para a inicializa¸c˜ao dos indiv´ıduos da popula¸c˜ao ´e
o uso de seq
¨
uˆencias de valores aleat´orios. Outras formas de inicializa¸c˜ao podem
visar melhorar a amostragem do espa¸co de busca na popula¸c˜ao inicial (Heckendorn
et al., 1997), ou aplicar heur´ısticas para gerar indiv´ıduos com melhor aptid˜ao j´a
na popula¸c˜ao inicial. Esses m´etodos devem ser usados com cautela, pois podem
ocasionar convergˆencia prematura ou, por vezes, requerer um tempo computa-
cional suficientemente grande para contrabalancear seus poss´ıveis efeitos positivos
(Cust´odio, 2008).
3.2.2 Sele¸c˜ao
No in´ıcio de cada itera¸c˜ao do la¸co principal do programa, s˜ao selecionados
um ou mais indiv´ıduos para reprodu¸c˜ao. Essa sele¸c˜ao ´e realizada por um processo
estoc´astico, que pode ser completamente aleat´orio ou pode levar em considera¸c˜ao,
de alguma forma, as aptid˜oes dos indiv´ıduos.
No m´etodo de Sele¸c˜ao Proporcional `a Aptid˜ao (spa) (Goldberg, 1989), os
indiv´ıduos mais aptos s˜ao os que tˆem maior probabilidade de se reproduzir, de
maneira an´aloga ao que ocorre em popula¸c˜oes naturais. A probabilidade do indi-
v´ıduo i ser selecionado para reprodu¸c˜ao, de acordo com este m´etodo, ´e:
p
i
=
F
i
n
j=1
F
j
(3.1)
onde F
i
´e a aptid˜ao do indiv´ıduo i, e n, o tamanho da popula¸c˜ao. Este m´etodo
tamb´em ´e conhecido como Sele¸c˜ao por Roleta, pois pode-se imaginar a sele¸c˜ao do
indiv´ıduo como a rodada de uma roleta, em que cada indiv´ıduo ´e representado por
um setor proporcional `a sua aptid˜ao.
Uma vantagem ´obvia do m´etodo de Sele¸c˜ao por Roleta ´e o fato de privilegiar
a prolifera¸c˜ao dos indiv´ıduos mais aptos diretamente a partir da sele¸c˜ao. Entre-
tanto, nas ocasi˜oes em que existem na popula¸c˜ao alguns indiv´ıduos com aptid˜ao
muito superior `a dos demais, estes indiv´ıduos podem dominar o processo de repro-
37
du¸c˜ao, resultando em uma convergˆencia prematura, isto ´e, uma r´apida condu¸c˜ao
da popula¸c˜ao a um estado em que todos os indiv´ıduos s˜ao muito parecidos entre
si (Cust´odio, 2008). Essa perda de diversidade pode ser extremamente prejudi-
cial `a obten¸c˜ao de bons resultados, pois leva `a elimina¸c˜ao r´apida de uma grande
quantidade de informa¸c˜oes com potencial promissor que poderia estar contida nos
indiv´ıduos menos aptos, deixando o algoritmo, no pior caso, em uma situa¸c˜ao de
estagna¸c˜ao.
O efeito de convergˆencia prematura pode ser minimizado se o posto (rank)
do indiv´ıduo na popula¸c˜ao for usado como parˆametro para se determinar a proba-
bilidade de escolha de cada indiv´ıduo, ao inv´es de, diretamente, sua aptid˜ao. Esse
m´etodo, chamado Sele¸c˜ao por Posto, foi proposto pela primeira vez por Baker
(1985) e tem por objetivo evitar que um pequeno grupo de indiv´ıduos parentais
origine uma fra¸c˜ao muito elevada do total de filhos. O m´etodo reduz a press˜ao
seletiva quando a varia¸c˜ao de aptid˜oes ´e muito alta e ajuda a mantˆe-la quando a
varia¸c˜ao de aptid˜oes ´e pequena, pois a propor¸c˜ao dos valores na roleta para os in-
div´ıduos classificados na posi¸c˜ao i e i+1 ser´a sempre a mesma, independentemente
da diferen¸ca entre suas aptid˜oes (Mitchell, 1996).
O m´etodo de Sele¸c˜ao por Posto requer que se ordene a popula¸c˜ao periodica-
mente. A Sele¸c˜ao por Torneio (Brindle, 1981) ´e outra alternativa `a Sele¸c˜ao por
Roleta, similar `a Sele¸c˜ao por Posto em termos de press˜ao seletiva (Mitchell, 1996),
mas que n˜ao depende de ordenamento. Na Sele¸c˜ao por Torneio, forma-se um sub-
conjunto da popula¸c˜ao, com indiv´ıduos selecionados aleatoriamente. O indiv´ıduo
mais apto entre os membros desse subconjunto ´e, ent˜ao, selecionado para repro-
du¸c˜ao.
3.2.3 Operadores
O segundo passo do la¸co principal de um ag, ap´os a sele¸c˜ao dos indiv´ıduos
que entrar˜ao no processo de reprodu¸c˜ao, ´e a aplica¸c˜ao de operadores. Um oper-
ador ´e uma fun¸c˜ao que gera novos indiv´ıduos a partir de indiv´ıduos preexistentes.
38
Diversos tipos de operadores podem ser conceitualizados, mas dois tipos de oper-
adores, em especial, est˜ao presentes em qualquer algoritmo gen´etico: os operadores
de muta¸c˜ao e recombina¸c˜ao.
3.2.3.1 Operador de Muta¸c˜ao
Um operador de muta¸c˜ao gera um novo indiv´ıduo a partir da c´opia mod-
ificada de um indiv´ıduo preexistente, chamado parental. A natureza exata da
modifica¸c˜ao depende da estrutura de dados do cromossomo, mas ´e geralmente de
natureza pontual e sempre aleat´oria. Por exemplo, no algoritmo gen´etico cl´assico,
em que o cromossomo ´e uma cadeia bin´aria, o operador de muta¸c˜ao, ap´os criar
uma c´opia do indiv´ıduo parental, inverte o valor de um ou mais bits da cadeia
cromossˆomica, os quais s˜ao escolhidos aleatoriamente.
3.2.3.2 Operador de Recombina¸c˜ao
Um operador de recombina¸c˜ao simula a reprodu¸c˜ao sexuada, gerando um
novo indiv´ıduo a partir da combina¸c˜ao de fragmentos dos cromossomos de dois
outros indiv´ıduos. Novamente, a natureza exata da opera¸c˜ao de recombina¸c˜ao
depende da estrutura de dados utilizada. A seguinte forma geral, entretanto, ´e
comumente empregada: s˜ao escolhidos aleatoriamente um ou mais pontos de corte,
que s˜ao posi¸c˜oes na cadeia cromossˆomica. Os mesmos pontos de corte s˜ao usados
para os dois indiv´ıduos parentais, que trocam o conte´udo de seus cromossomos a
partir de cada posi¸c˜ao especificada por estes.
Uma grande variedade de operadores j´a foi descrita em m´etodos de ag, in-
clusive diversas varia¸c˜oes dos operadores de muta¸c˜ao e recombina¸c˜ao, muitos dos
quais podem ser mais ou menos aplic´aveis a diferentes problemas e estruturas de
dados. A escolha dos operadores mais adequados a um ag ´e uma das etapas mais
importantes de sua defini¸c˜ao e pode determinar o sucesso ou n˜ao do algoritmo na
explora¸c˜ao adequada do espa¸co de busca.
39
3.2.4 Substitui¸c˜ao Parental
Os novos indiv´ıduos gerados a partir dos operadores tˆem suas aptid˜oes avali-
adas a partir dos fen´otipos correspondentes. Neste ponto, ´e importante ressaltar
a diferen¸ca entre duas categorias de Algoritmos Gen´eticos: ags geracionais, ou
tradicionais, e Algoritmos Gen´eticos steady state.
Nos ags geracionais, s˜ao criados, a cada itera¸c˜ao, um conjunto de novos
indiv´ıduos de tamanho igual ao da popula¸c˜ao. Este novo conjunto, ent˜ao, substitui
totalmente a popula¸c˜ao anterior.
Nos algoritmos steady state, apenas um n´umero limitado de indiv´ıduos ´e
gerado a cada itera¸c˜ao. Cada novo indiv´ıduo pode ter dois destinos: substituir
algum outro indiv´ıduo na popula¸c˜ao, ou ser descartado. Essa decis˜ao pode ser
considerada de v´arias maneiras. No caso mais simples, a aptid˜ao do novo indiv´ıduo
´e comparada `a do indiv´ıduo de pior aptid˜ao da popula¸c˜ao. Caso seja melhor, o
novo indiv´ıduo substitui o existente; do contr´ario, ´e descartado.
Diversos tipos de varia¸c˜oes j´a foram propostas para ambos os m´etodos de
substitui¸c˜ao parental, de modo a contornar algumas de suas deficiˆencias ou mel-
horar a efic´acia de suas aplica¸c˜oes em tipos espec´ıficos de problemas.
Um dos obst´aculos encontrados `a busca de boa solu¸c˜oes com o algoritmo
tradicional para ags geracionais prov´em do fato de que bons indiv´ıduos podem ser
perdidos no processo de substitui¸c˜ao da popula¸c˜ao, o qual ocorre a cada gera¸c˜ao.
Para contornar esse problema, Jong (1975) propˆos uma adi¸c˜ao ao m´etodo chamada
elitismo, que consiste em selecionar os melhores indiv´ıduos a cada gera¸c˜ao e mantˆe-
los obrigatoriamente na popula¸c˜ao da gera¸c˜ao seguinte. Em diversos tipos de
problemas, pode ser demonstrado que o elitismo pode melhorar expressivamente o
desempenho do Algoritmo Gen´etico (Mitchell, 1996).
3.2.5 Nichos e Preserva¸c˜ao da Diversidade
Em problemas de otimiza¸c˜ao, faz-se uma distin¸c˜ao entre m´ınimos locais e o
m´ınimo global. Sendo f(x) a fun¸c˜ao que se deseja minimizar, diz-se que x
∗
´e um
40
m´ınimo local se, para nenhum valor vizinho a x
∗
no espa¸co de busca, a fun¸c˜ao f tem
valor menor que em f(x
∗
). Diz-se que x
∗∗
´e um m´ınimo global se a fun¸c˜ao f n˜ao
tem valor menor que em f(x
∗∗
) para nenhum outro ponto do espa¸co de busca. Para
que x
∗
seja um m´ınimo local, em problemas sem restri¸c˜oes, e com f(x) suave, faz-se
necess´ario que f
(x
∗
) = 0 e f
(x
∗
) ≥ 0, sendo f
e f
, respectivamente, a primeira
e a segunda derivadas de f. N˜ao existe um crit´erio geral para se caracterizar um
ponto m´ınimo global (Cust´odio, 2008).
A presen¸ca de muitos m´ınimos locais acentuados ao longo de uma hipersu-
perf´ıcie pode se constituir em um importante obst´aculo ao desempenho de v´arias
classes de algoritmos destinados a resolver problemas de otimiza¸c˜ao. Em Algorit-
mos Gen´eticos projetados conforme varia¸c˜oes do modelo tradicional, pode ocorrer
que, em algum momento, toda a popula¸c˜ao seja conduzida em dire¸c˜ao a um mesmo
m´ınimo local, diferente do m´ınimo global. A perda da diversidade resultante de
tal convergˆencia prematura da popula¸c˜ao pode acarretar que a execu¸c˜ao do algo-
ritmo permane¸ca estagnada ao redor do m´ınimo, impedindo que outras regi˜oes da
superf´ıcie de busca sejam sequer exploradas em itera¸c˜oes posteriores.
A fun¸c˜ao f5 introduzida por Jong (1975) (figura 3.2) ilustra um caso extremo
de superf´ıcie de busca com m´ultiplos e profundos m´ınimos locais. Esse problema
motivou a cria¸c˜ao de adapta¸c˜oes do mecanismo de substitui¸c˜ao parental em ags, de
modo a evitar a convergˆencia prematura em um m´ınimo local e permitir a m´ultipla
explora¸c˜ao simultˆanea de v´arias regi˜oes da superf´ıcie de busca.
Dentre os m´etodos propostos mais utilizados, encontra-se o mecanismo de
crowding, proposto por Jong (1975), que se baseia no fenˆomeno dos nichos ecol´ogi-
cos. Na natureza, o nicho ecol´ogico de uma esp´ecie descreve seu estilo de vida,
englobando fatores como localiza¸c˜ao geogr´afica, habitat preferencial, tipo e modo
de alimenta¸c˜ao. De modo geral, existe uma competi¸c˜ao mais acirrada entre indiv´ı-
duos que ocupam nichos ecol´ogicos mais parecidos, pois estes tendem a competir
pelos mesmos recursos necess´arios `a sobrevivˆencia.
Esse fenˆomeno ´e modelado em um ag com crowding atrav´es de uma modi-
41
Figura 3.2: Fun¸c˜ao f5 de Jong (1975) (fox-hole)
fica¸c˜ao no sistema de substitui¸c˜ao parental. No ag com crowding, cada novo indi-
v´ıduo gerado substitui o indiv´ıduo que lhe ´e mais parecido na popula¸c˜ao, entre um
determinado n´umero de indiv´ıduos pais escolhidos ao acaso. O crit´erio de semel-
han¸ca entre dois indiv´ıduos utilizado na compara¸c˜ao dos nichos pode ser avaliado
de acordo com a proximidade de seus gen´otipos, ou por algum tipo de avalia¸c˜ao de
similaridade dos fen´otipos correspondentes. O mecanismo de crowding n˜ao modela
o m´etodo pelo qual a popula¸c˜ao atinge um estado de alta diversidade, mas busca
manter a diversidade j´a existente na popula¸c˜ao (Mahfoud, 1992). A aplica¸c˜ao do
modelo tende a resultar na gera¸c˜ao de nichos de indiv´ıduos que competem mais
fortemente entre si que com os demais, podendo levar `a descoberta de diferentes
m´ınimos locais por diferentes subconjuntos da popula¸c˜ao.
3.3 Algoritmos Gen´eticos com Restri¸c˜oes
O problema de otimiza¸c˜ao com restri¸c˜oes tradicionalmente se refere `a mini-
miza¸c˜ao de uma fun¸c˜ao objetiva f(x), onde x ∈ R ´e o vetor de vari´aveis de decis˜ao,
sujeito `as restri¸c˜oes de igualdade e desigualdade (Barbosa e Lemonge, 2002):
h
q
(x) = 0, q = 1, 2, . . . , q (3.2)
g
p
(x) ≥ 0, p = 1, 2, . . . , p (3.3)
42
Das solu¸c˜oes que atendem a todas as restri¸c˜oes, diz-se que s˜ao vi´aveis; as
demais s˜ao consideradas invi´aveis.
Problemas de otimiza¸c˜ao com restri¸c˜oes s˜ao tamb´em referidos como proble-
mas de programa¸c˜ao n˜ao linear. Quatro casos especiais desse tipo de problema
podem, na pr´atica, ser identificados (Michalewicz e Schoenauer., 1996): problemas
de otimiza¸c˜ao linearmente restritos, quando todas as fun¸c˜oes h
q
e g
p
s˜ao lineares;
problemas de programa¸c˜ao quadr´atica se, al´em disso, a fun¸c˜ao objetiva f ´e no m´ax-
imo quadr´atica; problemas de programa¸c˜ao linear, quando a fun¸c˜ao objetiva f ´e
linear; otimiza¸c˜ao sem restri¸c˜oes, quando q = p = 0.
A conven¸c˜ao de se representarem as restri¸c˜oes conforme descrito nas equa¸c˜oes
3.2 e 3.3 se deve mais `a conveniˆencia de f´acil reprodutibilidade dos resultados
que a considera¸c˜oes pr´aticas (Barbosa e Lemonge, 2003b). Freq
¨
uentemente, as
restri¸c˜oes n˜ao podem ser explicitamente descritas como fun¸c˜oes, e n˜ao ´e incomum
que a simples verifica¸c˜ao da viola¸c˜ao de uma restri¸c˜ao requeira um processo caro
e complexo de simula¸c˜ao computacional.
A aplica¸c˜ao de Algoritmos Gen´eticos a problemas de otimiza¸c˜ao restrita n˜ao
´e poss´ıvel de maneira trivial. A fun¸c˜ao aptid˜ao em um ag pode ou n˜ao ser definida
para elementos invi´aveis, e mesmo o conhecimento preciso da medida de viabilidade
de uma solu¸c˜ao n˜ao fornece qualquer indica¸c˜ao de qu˜ao pr´oxima esta pode estar
do ´otimo global (Barbosa e Lemonge, 2003b). Freq
¨
uentemente, em problemas de
otimiza¸c˜ao com restri¸c˜oes, a solu¸c˜ao ´otima reside na fronteira da regi˜ao vi´avel, de
modo que muitas das solu¸c˜oes mais similares ao gen´otipo da solu¸c˜ao ´otima s˜ao
invi´aveis.
As t´ecnicas usadas para se lidar com restri¸c˜oes em algoritmos gen´eticos po-
dem ser classificadas como diretas (ou interiores), quando apenas elementos vi´aveis
s˜ao considerados ao longo de todo o processo, ou indiretas (exteriores), quando
s˜ao usados durante a busca tanto elementos vi´aveis quanto invi´aveis (Barbosa e
Lemonge, 2003b).
Ao se escolher uma t´ecnica de incorpora¸c˜ao de restri¸c˜oes a algoritmos gen´eti-
43
cos, devem-se levar em conta as peculiaridades do dom´ınio do problema a ser anal-
isado. Restringir a busca apenas ao espa¸co vi´avel pode dificultar o surgimento de
modelos que dirijam a popula¸c˜ao em dire¸c˜ao ao ´otimo; por outro lado, se a busca
for efetuada em uma regi˜ao muito ampla, muito tempo ser´a gasto na explora¸c˜ao
de regi˜oes distantes da regi˜ao vi´avel, e a busca poder´a se estagnar fora da regi˜ao
vi´avel (Coit et al., 1996).
3.3.1 T´ecnicas diretas
3.3.1.1 “Pena de morte”
A maneira mais simples e direta de se tratar um problema com restri¸c˜oes
em um ag ´e, a cada gera¸c˜ao, descartar as solu¸c˜oes que n˜ao atendem `as restri¸c˜oes,
independentemente do potencial que estas tenham para contribuir com informa¸c˜ao
para a cria¸c˜ao de solu¸c˜oes vi´aveis. Esse m´etodo pode fornecer bons resultados para
alguns tipos de problemas, mas, em geral, costuma ter um desempenho baixo em
rela¸c˜ao a outras alternativas (Michalewicz, 1995).
3.3.1.2 Decodificadores gulosos
Em alguns tipos de problemas, pode ser poss´ıvel projetar cromossomos que,
ao inv´es de codificar diretamente a solu¸c˜ao, codificam uma s´erie de parˆametros
que s˜ao usados por um decodificador especialmente projetado para sempre gerar
uma solu¸c˜ao vi´avel. Esse tipo de codifica¸c˜ao pode ser dif´ıcil ou imposs´ıvel de ser
projetado para a maioria dos problemas (Surry e Radcliffe, 1997).
3.3.1.3 Operadores especiais
Operadores podem ser especialmente desenvolvidos para que seus produtos
sempre estejam dentro do espa¸co de solu¸c˜oes poss´ıveis (n˜ao-restritas). Tais op-
eradores devem ser espec´ıficos ao tipo de problema a ser resolvido. Assim como
no caso dos decodificadores gulosos, para muitos tipos de problemas, essa t´ecnica
pode ser impratic´avel.
44
Um exemplo de algoritmo bem-sucedido que utiliza essa abordagem ´e o Geno-
cop (Michalewicz e Janikow, 1991). O Genocop, em sua primeira vers˜ao, assume
a presen¸ca de apenas restri¸c˜oes lineares, assim como uma popula¸c˜ao inicial que
j´a esteja dentro do espa¸co de busca permitido. Vers˜oes posteriores do algoritmo
estenderam o m´etodo para problemas com restri¸c˜oes n˜ao-lineares (Michalewicz e
Nazhiyath, 1995).
3.3.1.4 M´etodos de reparo
Uma varia¸c˜ao do m´etodo anterior ´e o uso de operadores de reparo, que servem
especificamente para transformar solu¸c˜oes invi´aveis em vi´aveis.
Operadores de reparo podem ser proibitivamente caros computacionalmente,
al´em de terem o potencial de perturbarem os aspectos superiores das solu¸c˜oes
j´a encontradas, prejudicando a pr´opria caracter´ıstica fundamental da reprodu¸c˜ao
em Algoritmos Gen´eticos (Coit et al., 1996). Em muitas situa¸c˜oes, entretanto,
m´etodos de reparo podem se constituir em uma alternativa pr´atica e eficiente para
o problema das restri¸c˜oes.
Existem dois cursos de a¸c˜ao poss´ıveis ap´os a aplica¸c˜ao de um m´etodo de
reparo. A primeira op¸c˜ao ´e incorporar ao genoma a solu¸c˜ao reparada, no lugar
do cromossomo invi´avel que lhe deu origem. Essa abordagem ´e conhecida como
lamarckianismo e tem a vantagem de permitir melhorias locais mais r´apidas, mas
pode dificultar a travessia de regi˜oes invi´aveis do espa¸co de busca (Surry e Radcliffe,
1997). A alternativa de manter os cromossomos em sua forma invi´avel pode trazer
vantagens por permitir a explora¸c˜ao de uma regi˜ao maior do espa¸co.
3.3.2 T´ecnicas indiretas
3.3.2.1 M´etodos baseados em penalidades
A abordagem mais comum para a incorpora¸c˜ao de restri¸c˜oes a um algoritmo
gen´etico ´e o uso de fun¸c˜oes que penalizam as solu¸c˜oes fora do espa¸co de busca
permitido, de modo a for¸c´a-las de volta a esse espa¸co. Essas fun¸c˜oes s˜ao usualmente
45
constru´ıdas de modo que a penalidade imposta a uma solu¸c˜ao seja proporcional
`a magnitude de sua viola¸c˜ao das restri¸c˜oes. Em muitos m´etodos, um conjunto de
fun¸c˜oes ´e usado para se construir a fun¸c˜ao de viola¸c˜ao, da seguinte forma (Barbosa
e Lemonge, 2002):
v
j
(x) =
|h
j
(x)|, , para o caso da igualdade
max{0, −g
j
(x)}, , para o caso da desigualdade
(3.4)
A fun¸c˜ao de viola¸c˜ao ´e, por sua vez, usada para se construir a fun¸c˜ao de
penalidade, cuja forma mais popular ´e (Barbosa e Lemonge, 2002):
penal(x) = k
m
j=1
(v
j
(x))
2
(3.5)
onde k ´e o parˆametro de penalidade. A defini¸c˜ao de um bom parˆametro de pe-
nalidade ´e dependente do problema e pode se constituir em um longo processo de
tentativa e erro (Barbosa e Lemonge, 2002).
A fun¸c˜ao objetivo, ent˜ao, ´e definida por:
F (x) = f(x) + penal(x) (3.6)
Diversas varia¸c˜oes e aprimoramentos j´a foram sugeridas para o esquema geral
representado em (3.4), (3.5) e (3.6). Homaifar et al. (1994) utilizam uma fun¸c˜ao de
aptid˜ao como em (3.5), mas permitem ao usu´ario a defini¸c˜ao de v´arios parˆametros
referentes a diversos n´ıveis de viola¸c˜ao das restri¸c˜oes. Essa abordagem permite um
controle preciso do processo de penaliza¸c˜ao, mas tem a desvantagem de necessitar
do ajuste de um alto n´umero de parˆametros.
Joines e Houck. (1994) propuseram um algoritmo em que o valor de k ´e
ajustado de forma crescente ao longo das gera¸c˜oes, atrav´es da aplica¸c˜ao de k =
(C × t)
α
, onde C ´e uma constante, t ´e o n´umero da gera¸c˜ao e α ´e um parˆametro
ajust´avel, que variou entre 1 e 2, nos testes apresentados pelos autores.
Bean e Alouane. (1992) sugeriram um processo adaptativo em que k = λ(t),
46
de acordo com as regras:
λ(t + 1) =
(
1
β
1
)λ(t) , se b
i
∈ F para todo t − g + 1 ≤ i ≤ t
β
2
λ(t) , se b
i
∈ F para todo t − g + 1 ≤ i ≤ t
λ(t) , caso contr´ario
(3.7)
onde b
i
´e o melhor elemento na gera¸c˜ao i, F representa o conjunto de solu¸c˜oes
vi´aveis e β
1
e β
2
s˜ao parˆametros que ajustam a raz˜ao em que a penalidade pode
crescer ou decrescer a cada etapa, sendo β
1
= β
2
e β
1
, β
2
> 1. Nesse m´etodo, a cada
gera¸c˜ao, o parˆametro de penalidade cresce quando todos os melhores elementos das
´ultimas g gera¸c˜oes forem invi´aveis e decresce quando todos estes forem vi´aveis.
O m´etodo proposto por Coit et al. (1996) usa a seguinte fun¸c˜ao objetivo:
F (x) = f(x) + (F
feas
(t) − F
all
(t))
m
j=1
(v
j
(x)/v
j
(t))
α
(3.8)
Em que F
all
(t) corresponde `a melhor solu¸c˜ao sem penalidade at´e a gera¸c˜ao
t, F
feas
corresponde `a melhor solu¸c˜ao vi´avel e α ´e uma constante.
Alguns m´etodos aplicam uma distin¸c˜ao mais expl´ıcita entre solu¸c˜oes vi´aveis
e invi´aveis. O m´etodo proposto por Schoenauer e Xanthakis. (1993) trata apenas
uma restri¸c˜ao por vez, considerando o surgimento de um n´umero suficiente de
indiv´ıduos vi´aveis na popula¸c˜ao como crit´erio para se passar `a restri¸c˜ao seguinte.
O m´etodo proposto por Powell e Skolnick. (1993) aplica uma fun¸c˜ao de penalidade
escrita de modo a tornar, para todos os indiv´ıduos vi´aveis x e todos os indiv´ıduos
invi´aveis y, F (x) < F (y).
´
E comum em problemas de otimiza¸c˜ao que as restri¸c˜oes estejam ativas na
regi˜ao do m´ınimo global. Nesses casos, o ´otimo da fun¸c˜ao restrita deve se localizar
na fronteira entre as regi˜oes restrita e permitida. Algumas abordagens baseadas em
penalidades aproveitam esse fato, estabelecendo fun¸c˜oes de penalidades e incentivos
que induzem ao percurso oscilat´orio da busca em torno da fronteira (Michalewicz
e Schoenauer., 1996; Schoenauer e Michalewicz, 1996).
47
Riche et al. (1995) utilizam dois conjuntos de solu¸c˜oes candidatas: o primeiro
avaliado com o parˆametro de penalidade k
1
, o segundo, com k
2
, sendo k1
k
2
. Essa solu¸c˜ao valoriza, por um lado, a manuten¸c˜ao de indiv´ıduos vi´aveis, sem
perder, por outro lado, as informa¸c˜oes que possam estar contidas nos invi´aveis,
incentivando a gera¸c˜ao de novas solu¸c˜oes que estejam pr´oximas `a fronteira entre
as duas regi˜oes do espa¸co de parˆametros.
3.3.2.2 Letaliza¸c˜ao
Uma varia¸c˜ao simplificada do m´etodo de penalidades ´e a chamada letaliza¸c˜ao,
em que um valor extremamente baixo de aptid˜ao ´e atribu´ıdo para qualquer solu¸c˜ao
que viole alguma restri¸c˜ao. Esse m´etodo apresenta a s´eria deficiˆencia de n˜ao levar
em considera¸c˜ao o n´ıvel de viola¸c˜ao das restri¸c˜oes de cada indiv´ıduo, al´em de
possivelmente possibilitar que uns poucos indiv´ıduos que n˜ao violem nenhuma
restri¸c˜ao na popula¸c˜ao inicial passem a dominar a popula¸c˜ao nas gera¸c˜oes seguintes.
Ainda assim, a letaliza¸c˜ao pode, em alguns casos espec´ıficos, ser t˜ao ou mais efetiva
que um ajuste preciso de fun¸c˜oes de penalidade (van Kampen et al., 1996).
3.3.2.3 Esquemas de penalidade adaptativos
Barbosa e Lemonge (2002) propuseram um mecanismo para o ajuste adap-
tativo da penalidade k em algoritmos gen´eticos geracionais que n˜ao depende de
nenhum parˆametro. A fun¸c˜ao objetivo ´e definida como:
F (x) =
f(x) , se x for vi´avel
h(x) +
m
j=1
k
j
v
j
(x) , caso contr´ario
(3.9)
onde
h(x) =
f(x) , se f(x) > f (x)
f(x) , caso contr´ario
(3.10)
e f(x) ´e a m´edia dos valores calculados pela fun¸c˜ao objetivo na popula¸c˜ao atual.
48
O parˆametro k
j
, ent˜ao, ´e definido a cada gera¸c˜ao por:
k
j
= |f(x)|
v
j
(x)
m
l=1
[v
l
(x)]
2
(3.11)
onde v
l
(x) ´e a m´edia da viola¸c˜ao da l-´esima restri¸c˜ao na popula¸c˜ao atual.
Al´em de ser mais simples e genericamente aplic´avel que outras t´ecnicas pro-
postas, esse m´etodo obteve resultados superiores aos obtidos pelos demais em di-
versos problemas analisados pelos autores (Barbosa e Lemonge, 2002).
Em uma continua¸c˜ao desse trabalho (Barbosa e Lemonge, 2003a), o m´etodo
foi estendido para que possa ser aplicado em algoritmos do tipo steady-state. Nesse
caso, as equa¸c˜oes (3.10) e (3.13) passam a ser definidas como:
h(x) =
f(x
pior
) , se n˜ao h´a indiv´ıduos vi´aveis na popula¸c˜ao
f(x
melhorviavel
) , caso contr´ario
(3.12)
k
j
= h
v
j
(x)
m
l=1
[v
l
(x)]
2
(3.13)
h ´e redefinido e todos os valores de aptid˜ao s˜ao recalculados em duas ocasi˜oes:
quando o n´umero de novos elementos inseridos na popula¸c˜ao atinge um certo valor,
e cada vez que ´e gerado um elemento vi´avel que seja melhor que o melhor membro
da popula¸c˜ao atual.
A defini¸c˜ao de h(x) dada em (3.12) implica que, enquanto nenhum elemento
vi´avel estiver presente na popula¸c˜ao, o algoritmo est´a, na realidade, minimizando
a distˆancia dos indiv´ıduos ao conjunto vi´avel. No momento em que um indiv´ıduo
vi´avel ´e encontrado, entretanto, ele imediatamente entra na popula¸c˜ao, pois, ap´os
serem atualizados todos os valores de aptid˜ao de acordo com as (3.12), (3.13) e
(3.9), ele se torna o indiv´ıduo mais apto.
O m´etodo descrito pˆode produzir resultados competitivos com os melhores
resultados dispon´ıveis na literatura, sem requerer do usu´ario o ajuste manual de
quaisquer parˆametros (Barbosa e Lemonge, 2003a).
49
3.3.2.4 M´etodos baseados em formula¸c˜oes multi-objetivo
Um problema de otimiza¸c˜ao multi-objetivo ´e definido por um conjunto de
fun¸c˜oes objetivo f
1
, f
2
, . . . , f
N
, todas as quais devem, idealmente, ser minimizadas.
Um problema de otimiza¸c˜ao com restri¸c˜oes pode ser visto, portanto, como uma
varia¸c˜ao desse tipo de problema, em que a fun¸c˜ao f(x) corresponde a uma das
fun¸c˜oes a ser minimizada, f
1
e cada restri¸c˜ao corresponde a uma das demais fun¸c˜oes
f
n
.
Problemas multi-objetivo geralmente envolvem fun¸c˜oes que competem entre
si, no sentido de que a melhoria na avalia¸c˜ao por uma fun¸c˜ao implica em degrada¸c˜ao
na avalia¸c˜ao por outra. Diz-se que uma solu¸c˜ao x domina uma solu¸c˜ao y se e
somente se:
∀i ∈ {1, 2, . . . , n} : f
i
(x) ≤ f
i
(y)
e ∃j ∈ {1, 2, . . . , n} : f
j
(x) < f
j
(y) (3.14)
Nesses casos, a abordagem mais satisfat´oria ´e a de buscar n˜ao uma ´unica
solu¸c˜ao global, mas um conjunto de solu¸c˜oes Pareto-´otimas (Surry e Radcliffe,
1997). Este ´e definido como o conjunto de solu¸c˜oes que n˜ao s˜ao dominadas por
nenhuma outra solu¸c˜ao no espa¸co de busca.
O algoritmo comoga (Surry e Radcliffe, 1997) trata o problema de otimiza-
¸c˜ao de acordo com essa abordagem, atrav´es de um algoritmo adaptativo com poucos
parˆametros definidos pelo usu´ario. No comoga, ap´os cada avalia¸c˜ao, as solu¸c˜oes
s˜ao classificadas e selecionadas para inser¸c˜ao na popula¸c˜ao, tanto pelo crit´erio de
minimiza¸c˜ao da fun¸c˜ao de avalia¸c˜ao de aptid˜ao, quanto de acordo com o crit´erio de
Pareto para as demais fun¸c˜oes, que representam as restri¸c˜oes. A propor¸c˜ao entre as
solu¸c˜oes escolhidas de acordo com ambos os crit´erios ´e ajustada adaptativamente
ao longo da execu¸c˜ao.
50
3.3.2.5 Ranking estoc´astico
O trabalho de Runarsson e Yao (2000) apresentou uma abordagem de algo-
ritmo gen´etico com restri¸c˜oes que enfatiza explicitamente o processo propriamente
dito de sele¸c˜ao dos indiv´ıduos, em detrimento de quaisquer modifica¸c˜oes na fun¸c˜ao
objetivo devido a restri¸c˜oes.
A cada rodada do algoritmo, todos os indiv´ıduos s˜ao previamente classifi-
cados em um ranking constru´ıdo atrav´es de um algoritmo similar ao bubble-sort.
Para efeitos dessa classifica¸c˜ao, dois indiv´ıduos vi´aveis sempre s˜ao comparados de
acordo com sua aptid˜ao, conforme medida pela fun¸c˜ao objetivo. Caso ao menos
um dos indiv´ıduos seja invi´avel, entretanto, h´a uma probabilidade (1 − P
f
) de que
eles sejam comparados apenas de acordo com as fun¸c˜oes de penalidade. Os autores
sugerem para P
f
valores entre 0.4 e 0.5 e obtiveram bons resultados (Runarsson e
Yao, 2000) em um conjunto-teste usualmente empregado na literatura.
3.3.3 GENFOLD
O programa GENFOLD (Bayley et al., 1998) representa possivelmente a
´unica implementa¸c˜ao j´a descrita de um algoritmo gen´etico para o problema da
resolu¸c˜ao de estruturas prot´eicas a partir de restri¸c˜oes de rmn.
No GENFOLD, as prote´ınas s˜ao representadas nos cromossomos atrav´es de
suas coordenadas internas. As restri¸c˜oes de ˆangulo s˜ao consideradas na pr´opria
sele¸c˜ao de operadores, que nunca geram indiv´ıduos que violem os ˆangulos diedrais
permitidos. Antes da avalia¸c˜ao, cada prote´ına ´e convertida temporariamente em
sua representa¸c˜ao equivalente em coordenadas cartesianas, para que possam ser
calculados os parˆametros baseados em distˆancia. A popula¸c˜ao inicial, de 500 indi-
v´ıduos, ´e gerada atrav´es da atribui¸c˜ao de valores aleat´orios para todos os ˆangulos
diedrais de cada indiv´ıduo.
A fun¸c˜ao objetivo ´e composta por um termo referente `as restri¸c˜oes de dis-
51
tˆancia (F
NOE
) e outro referente `as restri¸c˜oes de colis˜ao est´ericas (E
vdW
):
E = E
NOE
+ AE
vdW
(3.15)
O termo A ´e um parˆametro controlado por operadores, sendo que, tipica-
mente, A = 5. O termo F
NOE
´e dado por:
E
NOE
=
(
noe
max
n=0
w
n
f
n
)
noe
max
(3.16)
onde noe
max
´e o n´umero m´aximo de restri¸c˜oes de distˆancia, e f
n
´e dada por:
f
n
=
(d
n
− d
upper
n
)
P
, para d
n
> d
upper
(d
lower
n
− d
n
)
P
, para d
n
< d
lower
0 , para d
lower
< d < d
upper
(3.17)
onde d
n
´e a distˆancia encontrada entre o par de ´atomos na estrutura, d
lower
n
e
d
upper
n
s˜ao, respectivamente, os limites inferior e superior da restri¸c˜ao, e w
n
e P
s˜ao parˆametros definidos pelo usu´ario. Nos c´alculos apresentados pelos autores, foi
utilizado w
n
= P = 1.
O termo E
vdW
´e dado por:
E
vdW
=
N
atomos
i=1
N
atomos
j>i
E
i
E
j
1
a
12
ij
−
2
a
6
ij
N
−1,5
atomos
(3.18)
onde a
ij
= r
ij
/(R
i
+ R
j
), e r
ij
´e a distˆancia entre os ´atomos i e j. Os valores
para o raio de van der Waals do ´atomo i, R
i
, e a constante de escalonamento de
van der Waals E
i
s˜ao obtidas a partir dos valores determinados no campo de for¸ca
TRIPOS (Matthew Clark et al., 1989).
O GENFOLD ´e um algoritmo gen´etico do tipo steady state, isto ´e, a cada
passo, ´e gerada uma solu¸c˜ao filha que substitui um ´unico membro da popula¸c˜ao,
nesse caso, aquele com a menor aptid˜ao. Os indiv´ıduos s˜ao escolhidos para repro-
du¸c˜ao atrav´es do m´etodo da roleta, isto ´e, a probabilidade de um dado cromossomo
52
ser escolhido, a cada passo, ´e diretamente proporcional `a sua aptid˜ao. Para cada
parental ou par de parentais, ´e escolhido aleatoriamente e com igual probabilidade
um dos seis poss´ıveis operadores: (1) muta¸c˜ao aleat´oria; (2) pequena mudan¸ca
aleat´oria em um valor; (3) crossover de um ponto; (4) crossover de dois pontos;
(5) varia¸c˜ao estrutural local, implementada como a altera¸c˜ao do valor φ de um
res´ıduo e do valor φ do res´ıduo precedente em valores iguais e opostos; (6) varia¸c˜ao
estrutural similar `a anterior para grupos de 3 a 5 res´ıduos.
Na implementa¸c˜ao do algoritmo GENFOLD, inicialmente ´e escolhida uma
seq
¨
uˆencia dos 20 res´ıduos consecutivos que contenham o maior n´umero de restri¸c˜oes
de distˆancia, e a fun¸c˜ao objetivo ´e avaliada apenas para esse grupo, em todos os
cromossomos. Ap´os um determinado n´umero de avalia¸c˜oes, essa janela de sele¸c˜ao ´e
movida 10 res´ıduos em um sentido aleat´orio, e assim sucessivamente, at´e que todo
o cromossomo tenha sido coberto em algum momento. Essa solu¸c˜ao foi descrita
pelos autores como mais eficiente que a alternativa de se avaliar o cromossomo
completo ao longo de toda a execu¸c˜ao (Bayley et al., 1998).
No desenvolvimento do genfold, partiu-se do princ´ıpio de que ags tipica-
mente produzem boas solu¸c˜oes aproximadas, mas s˜ao otimizadores pobres (Bayley
et al., 1998). Por esse motivo, foi considerado que a realiza¸c˜ao de um procedimento
posterior ao ag, para otimiza¸c˜ao das estruturas encontradas, seria essencial ao ob-
jetivo de se encontrarem estruturas pr´oximas `as nativas, com poucas viola¸c˜oes de
restri¸c˜oes.
As estruturas produzidas pelo genfold para seu conjunto-teste foram refi-
nadas utilizando o programa x-plor
1
, com vers˜oes modificadas de seus protoco-
los de recozimento simulado. O primeiro protocolo utilizado iniciava a simula¸c˜ao a
uma temperatura de 2.000K, executava 1.500 passos nessa temperatura e decrescia
a temperatura gradualmente ao longo de mais 2.000 passos; o segundo iniciava a
1.000K e executava 4.000 passos `a medida que decrescia a temperatura.
O processo de otimiza¸c˜ao com os protocolos do x-plor foi capaz de reduzir
1
Se¸c˜ao ??.
53
o rmsd entre as estruturas geradas pelo genfold e as estruturas de referˆencia,
de valores em torno de 3-4
˚
A, para valores em torno de 1
˚
A, para as estrutruras
mais simples do conjunto-teste. Para a estrutura considerada mais desafiadora,
essa redu¸c˜ao foi de 8.94
˚
A para 1.60
˚
A (Bayley et al., 1998).
54
Cap´ıtulo 4
Metodologia
Foi desenvolvido neste trabalho um Algoritmo Gen´etico (ag) para predi¸c˜ao
de estruturas de prote´ınas a partir de dados experimentais de rmn representados
como restri¸c˜oes de distˆancia entre pares de ´atomos e restri¸c˜oes de intervalos para
ˆangulos diedrais em segmentos da estrutura pept´ıdica. O algoritmo foi implemen-
tado como uma vers˜ao modificada do ag para predi¸c˜ao ab initio de estruturas de
prote´ınas gapf, desenvolvido por Cust´odio (2008).
O problema da predi¸c˜ao ab initio se refere `a resolu¸c˜ao de estruturas pro-
t´eicas apenas a partir do conhecimento de uma seq
¨
uˆencia de amino´acidos, sem
informa¸c˜oes experimentais. O problema objeto deste trabalho, portanto, pode
ser considerado como um caso especial do problema de predi¸c˜ao ab initio, com
a importante varia¸c˜ao de que, neste caso, disp˜oe-se de um conjunto adicional de
informa¸c˜oes a respeito da prote´ına: os resultados experimentais de rmn.
Muitos dos desafios inerentes ao problema de predi¸c˜ao de estruturas usando
dados de rmn s˜ao comuns aos m´etodos de predi¸c˜ao ab initio. Entre esses, incluem-
se a escolha da melhor forma de representa¸c˜ao computacional de estruturas, a
constru¸c˜ao de uma boa fun¸c˜ao de energia e de um m´etodo de busca eficaz. Ainda,
no caso da escolha de um ag como m´etodo computacional, ambos os problemas
podem se beneficar das mesmas solu¸c˜oes para in´umeras decis˜oes de implementa¸c˜ao,
como constru¸c˜ao da popula¸c˜ao inicial, defini¸c˜ao dos operadores e de seus m´etodos
de sele¸c˜ao, assim como determina¸c˜ao dos crit´erios de substitui¸c˜ao parental.
55
A abordagem de se incorporarem restri¸c˜oes de rmn a um algoritmo ab initio
tem como objetivo principal permitir, em futuras vers˜oes, que seja poss´ıvel realizar
a predi¸c˜ao de estruturas com um n´umero de restri¸c˜oes menor que em algoritmos
tradicionais.
4.1 GAPF
O gapf ´e um algoritmo gen´etico de m´ultiplos m´ınimos desenvolvido para
abordar o problema da predi¸c˜ao da estrutura tridimensional de uma prote´ına a
partir do conhecimento de sua seq
¨
uˆencia linear de amino´acidos.
Assim como ocorre tipicamente em algoritmos ab initio, o algoritmo do gapf
pode ser descrito como uma busca realizada em uma hipersuperf´ıcie de energia
associada a poss´ıveis estruturas conformacionais de prote´ınas. Cada ponto da
hipersuperf´ıcie representa uma estrutura compat´ıvel com a seq
¨
uˆencia dada, e, a
cada estrutura, pode ser associado um valor de energia. Conforme abordado na
se¸c˜ao 1.2, essa energia ´e calculada de maneira necessariamente aproximada. O
objetivo do algoritmo ´e encontrar o ponto da hipersuperf´ıcie que corresponde `a
estrutura de menor energia. Parte-se da proposi¸c˜ao de que essa estrutura deve ser,
se n˜ao idˆentica, ao menos satisfatoriamente similar `a da estrutura biol´ogica nativa.
A constru¸c˜ao vi´avel de um algoritmo ab initio s´o pode ser concebida, por-
tanto, a partir da implementa¸c˜ao adequada de, no m´ınimo, dois aspectos fun-
damentais: a defini¸c˜ao da hipersuperf´ıcie de busca e a constru¸c˜ao da fun¸c˜ao de
energia. O primeiro aspecto est´a relacionado `a maneira como as estruturas con-
formacionais das prote´ınas s˜ao representadas; o segundo, ao crit´erio de avalia¸c˜ao
de cada estrutura. A formula¸c˜ao de uma fun¸c˜ao de energia cuja estrutura de valor
m´ınimo corresponda `a estrutura mais pr´oxima poss´ıvel da estrutura nativa, ´e, por
si s´o, um problema desafiador e ainda n˜ao totalmente resolvido.
56
Figura 4.1: O cromossomo utilizado no gapf representa uma prote´ına como uma
cadeia de res´ıduos de amino´acidos. Cada res´ıduo, por sua vez, ´e modelado como
um conjunto de ˆangulos φ, ψ e, opcionalmente, χ
1
, ..., χ
n
, sendo 1 ≥ n ≥ 4, de
acordo com a quantidade de ˆangulos χ definida para o amino´acido correspondente.
4.1.1 O Cromossomo do GAPF
A abordagem mais direta para a representa¸c˜ao de prote´ınas em uma estru-
tura de dados computacional ´e a listagem de um conjunto de ´atomos, cada um dos
quais identificado por suas coordenadas cartesianas. Nessa representa¸c˜ao, entre-
tanto, grande parte dos vizinhos de qualquer estrutura ´e invi´avel, devido a colis˜oes
est´ericas e `a forma¸c˜ao ˆangulos de valˆencia e liga¸c˜oes covalentes fisicamente im-
prov´aveis. Tal caracter´ısica a torna pouco pr´atica para uso em um processo de
otimiza¸c˜ao. Por esse motivo, o gapf utiliza uma representa¸c˜ao em coordenadas
internas
1
, as quais permitem uma navega¸c˜ao mais natural pelo espa¸co de poss´ıveis
conforma¸c˜oes.
No gapf, o cromossomo, que representa todas as informa¸c˜oes associadas a
cada indiv´ıduo da popula¸c˜ao, ´e uma estrutura de dados em cadeia que cont´em,
em ordem, a seq
¨
uˆencia de res´ıduos de amino´acidos da prote´ına. Cada res´ıduo
´e implementado como um conjunto de ˆangulos diedrais. Os ˆangulos diedrais da
cadeia principal φ e ψ est˜ao representados em todos os res´ıduos. Adicionalmente,
dependendo do tipo de amino´acido correspondente, podem estar representados
tamb´em entre zero e 4 ˆangulos diedrais da cadeia lateral, χ
1
,χ
2
,χ
3
e χ
4
(Figura
4.1).
As estruturas geradas pelos operadores do gapf sempre mant´em constantes
as distˆancias de liga¸c˜ao covalentes e os ˆangulos entre as liga¸c˜oes, que s˜ao os mesmos
1
Se¸c˜ao 1.1.5
57
pelas topologias do gromos (Scott et al., 1999). Apenas s˜ao pass´ıveis de modifi-
ca¸c˜ao os ˆangulos diedrais representados no cromossomo. Mol´eculas biol´ogicas reais
podem apresentar pequenas varia¸c˜oes nesses valores, e essa restri¸c˜ao pode resultar
em estruturas ligeiramente distorcidas em rela¸c˜ao `a estrutura nativa (Cust´odio,
2008). Entretanto, a aproxima¸c˜ao ´e empregada por permitir a f´acil manuten¸c˜ao
da geometria das liga¸c˜oes qu´ımicas durante a busca, sem custo computacional adi-
cional.
4.1.1.1 Rotˆameros
Como uma maneira de reduzir o n´umero de graus de liberdade do problema,
os operadores do gapf manipulam diretamente apenas os ˆangulos φ e ψ do cromos-
somo. Os ˆangulos de tor¸c˜ao χ
n
, que definem a conforma¸c˜ao das cadeias laterais,
s˜ao ajustados automaticamente com o uso de uma biblioteca de rotˆameros. Um
rotˆamero ´e definido como uma s´erie de ˆangulos χ
n
aplic´aveis a um tipo espec´ıfico
de amino´acido.
A biblioteca de rotˆameros utilizada ´e a vers˜ao truncada de uma biblioteca
publicada em maio de 2002 a partir de 850 estruturas retiradas do pdb com res-
olu¸c˜ao melhor ou igual a 1,7
˚
A (Dunbrack, 2002) e cont´em os ˆangulos m´edios de
tor¸c˜ao das cadeias laterais de cada tipo de amino´acido, associados a suas respectivas
freq
¨
uˆencias de ocorrˆencia em fun¸c˜ao dos valores de φ e ψ em que s˜ao encontrados
nas estruturas. Na vers˜ao truncada, foram considerados apenas os rotˆameros que
apresentavam freq
¨
uˆencia maior ou igual a 5% na biblioteca original. Essa sim-
plifica¸c˜ao foi realizada devido ao grande espa¸co em disco ocupado pela biblioteca
completa, a qual poderia atrasar a execu¸c˜ao do programa devido a um aumento
de acesso a disco e consumo de mem´oria (Cust´odio, 2008).
Sempre que ocorre alguma modifica¸c˜ao em um dos ˆangulos da cadeia prin-
cipal, a biblioteca de rotˆameros ´e consultada, e um rotˆamero ´e escolhido para
aplica¸c˜ao ao res´ıduo modificado. A escolha do rotˆamero ´e realizada de acordo com
o m´etodo de roleta, em que a probabilidade de que um rotˆamero seja escolhido ´e
58
proporcional a sua freq
¨
uˆencia para os valores de φ e ψ daquele res´ıduo.
4.1.2 Fun¸c˜ao Aptid˜ao
A fun¸c˜ao utilizada pelo gapf para avaliar o grau de aptid˜ao de cada indiv´ıduo
no algoritmo gen´etico ´e baseada na energia de intera¸c˜ao dos ´atomos da prote´ına,
calculada de acordo com o campo de for¸ca molecular cl´assico gromos96 (van
Gunsteren e Berendsen, 1987; Schuler et al., 2001).
A fun¸c˜ao de energia do gromos96 tem a forma geral apresentada na equa¸c˜ao
1.2, composta pela soma de 5 termos, que modelam, respectivamente, a energia
relacionada `a varia¸c˜ao na extens˜ao da liga¸c˜ao covalente, ao ˆangulo da liga¸c˜ao co-
valente, `a rota¸c˜ao da liga¸c˜ao covalente (ˆangulo diedral), `as intera¸c˜oes n˜ao ligadas
de curto alcance (van der Waals e colis˜oes est´ericas), e `as intera¸c˜oes eletrost´ati-
cas. Uma vez que a extens˜ao e ˆangulo das liga¸c˜oes covalentes s˜ao invari´aveis na
representa¸c˜ao de dados empregada no m´etodo, a inclus˜ao dos dois primeiros ter-
mos ´e desnecess´aria na fun¸c˜ao aptid˜ao do gapf, que apresenta, ent˜ao, a seguinte
formula¸c˜ao (Cust´odio, 2008):
E
total
(r
i
) =
N
φ
n=1
K
φn
[1 + cos(n
n
· φ
n
− δ
n
)]
E
torc
+ (4.1)
+ p ×
N
´atomos
i≤k
−
A
ij
r
ij
6
+
B
ij
r
ij
12
E
LJ
+ (4.2)
+
N
´atomos
i≤k
q
i
q
j
4πε
0
ε
r
(r
ij
)r
ij
E
coul
, (4.3)
onde E
torc
se refere ao termo que modela a energia da liga¸c˜ao torsional; E
LJ
, ao
potencial de Lennard-Jones; E
coul
, ao potencial de Coulomb.
O termo torsional (E
torc
, equa¸c˜ao 4.1) modela as varia¸c˜oes de energia prove-
nientes da rota¸c˜ao dos ˆangulos diedrais, isto ´e, as barreiras energ´eticas entre os
valores que esses ˆangulos podem assumir; o parˆametro K
φn
´e a constante de ener-
59
gia associada `a rota¸c˜ao de uma liga¸c˜ao qu´ımica, φ
n
´e o ˆangulo de tors˜ao, n
n
´e a
periodicidade do ˆangulo, e δ
n
, o ˆangulo de fase.
O potencial de Lennard-Jones (E
LJ
, equa¸c˜ao 4.2) modela a repuls˜ao entre
os ´atomos a distˆancias muito curtas (termo r
−12
) e as intera¸c˜oes atrativas de van
der Waals (termo r
−6
). Nesse termo, r
ij
´e a distˆancia entre os ´atomos i e j, e A
ij
e B
ij
s˜ao os parˆametros de Lennard-Jones.
O potencial de Coulomb (E
coul
, equa¸c˜ao 4.3) ´e utilizado para modelar as
intera¸c˜oes eletrost´aticas, isto ´e, as for¸cas de atra¸c˜ao e repuls˜ao el´etricas entre os
´atomos carregados. q
i
e q
j
s˜ao, respectivamente, as cargas atˆomicas parciais dos
´atomos i e j, e ε
r
´e a fun¸c˜ao diel´etrica sigmoidal dependente da distˆancia, a qual
modela o efeito de blindagem do solvente nas intera¸c˜oes eletrost´aticas (Arora e
Jayaram, 1997). Os parˆametros desse termo foram extra´ıdos do campo de for¸cas
gromos 43b1 (van Gunsteren et al., 1996).
4.1.3 Suaviza¸c˜ao do Potencial de Lennard-Jones
A natureza do termo repulsivo (r
−12
) do potencial de Lennard-Jones (E
LJ
)
implica que estruturas que contenham dois ou mais ´atomos espacialmente muito
pr´oximos ter˜ao uma energia total extremamente elevada, mesmo que sejam estru-
turas de boa qualidade em rela¸c˜ao a quaisquer outros fatores de sua geometria.
No processo de Dinˆamica Molecular (dm, se¸c˜ao 1.2), para as quais os termos
do campo de for¸ca foram originalmente desenvolvidos, a dire¸c˜ao das for¸cas atuando
sobre cada ´atomo ´e levada em considera¸c˜ao ao se realizarem modifica¸c˜oes nas
estruturas. Por esse motivo, dificilmente s˜ao geradas, em qualquer momento da
execu¸c˜ao, estruturas com valores de energia extraordinariamente altos.
Em um Algoritmo Gen´etico, entretanto, devido ao mecanismo de aplica¸c˜ao de
operadores, as estruturas podem sofrer, em uma ´unica etapa, altera¸c˜oes muito mais
significativas – e potencialmente destrutivas – que aquelas ocorridas em simula¸c˜oes
de dm. Algoritmos que, como o gapf, empregam bibliotecas de rotˆameros para
o ajuste das cadeias laterias, s˜ao especialmente suscet´ıveis `a gera¸c˜ao repentina de
60
estruturas com essas caracter´ısticas (Pokala e Handel, 2005). Para evitar que tais
estruturas sejam imediatamente descartadas, m´etodos de predi¸c˜ao de estruturas
de prote´ınas comumente empregam processos de suaviza¸c˜ao do termo repulsivo de
Lennard-Jones. O gapf utiliza uma vers˜ao modificada da abordagem, j´a testada
no problema de docking prote´ına-ligante (de Magalh˜aes et al., 2004), que introduz
ao termo o multiplicador p dado por:
p = min
1,
neval
c × maxeval
(4.4)
que varia com o n´umero de avalia¸c˜oes da fun¸c˜ao (neval). O parˆametro c vale
0,5, de modo que, quando neval for igual `a metade do total de avalia¸c˜oes fixado,
maxeval, o potencial de Lennard-Jones passa a funcionar sem suaviza¸c˜ao.
Uma vez que a principal raz˜ao em se utilizar o recurso de suaviza¸c˜ao no
gapf vem do posicionamento das cadeias laterais, devido `a aplica¸c˜ao de rotˆameros
oriundos de uma biblioteca, o multiplicador p s´o ´e utilizado no gapf para o c´alculo
do potencial de lj nas itera¸c˜oes da equa¸c˜ao 4.2 em que i ou j correspondam a um
´atomo da cadeia lateral, excluindo carbonos β.
4.1.4 Popula¸c˜ao inicial
As estruturas da popula¸c˜ao inicial s˜ao geradas, a princ´ıpio, como cadeias
estendidas com varia¸c˜oes de at´e 20
◦
nos ˆangulos φ e ψ. Os ˆangulos ω s˜ao inicial-
izados na forma trans (180
◦
) e sofrem perturba¸c˜ao de at´e 2
◦
. Em seguida, para
cada indiv´ıduo, ´e selecionada, com igual probabilidade, uma das trˆes estruturas se-
cund´arias: α-h´elice, fita β ou random coil, e, tamb´em aleatoriamente, trˆes res´ıduos
consecutivos, nos quais s˜ao alterados os valores de φ e ψ, de acordo com a tabela
4.1.4 (Cust´odio, 2008). As cadeias laterais s˜ao geradas de acordo com o m´etodo
descrito na se¸c˜ao 4.1.1.1.
61
Tabela 4.1: Valores de φ e ψ em graus.
Conforma¸c˜ao φ ψ
α-h´elice −60 ± 3 −44 ± 3
folha β −129 ± 3 +125 ± 3
random coil +180 ± 60 +180 ± 60
4.1.5 Operadores
O gapf seleciona aleatoriamente os indiv´ıduos que ser˜ao utilizados no pro-
cesso de reprodu¸c˜ao e define seis poss´ıveis operadores. A escolha de qual deles ser´a
aplicado a cada indiv´ıduo selecionado ocorre no gapf atrav´es de um procedimento
adaptativo. O objetivo do procedimento ´e atribuir maior probabilidade de sele¸c˜ao
aos operadores mais eficientes em gerar boas estruturas, em detrimento daqueles
menos eficientes. O m´etodo implementado foi baseado no proposto por Davis et al.
(1996) e consiste em duas partes: (i) computa¸c˜ao do desempenho do operador e
(ii) adapta¸c˜ao da probabilidade do operador (Cust´odio, 2008).
Inicialmente, todos os operadores tˆem igual probabilidade de aplica¸c˜ao:
P (O
i
) =
1
N
operadores
, 1 ≤ i ≤ N
operadores
(4.5)
onde P (O
i
) ´e a probabilidade de aplica¸c˜ao do operador i e N
operadores
= 6 ´e o
n´umero total de operadores definidos pelo gapf.
O desempenho dos operadores ´e computado atrav´es de um sistema de cr´edi-
tos: Cada vez que um novo indiv´ıduo ´e gerado, compara-se sua aptid˜ao (E
filho
)
com a do melhor indiv´ıduo da popula¸c˜ao (E
melhor
). Se a aptid˜ao do novo indiv´ıduo
for melhor que a deste, atribui-se ao operador que o gerou um valor de cr´edito igual
`a diferen¸ca entre estas aptid˜oes (Equa¸c˜ao 4.6):
C
A
= E
melhor
− E
filho
(4.6)
onde C
A
´e o cr´edito a ser adicionado ao operador que gerou o novo indiv´ıduo.
62
Adicionamente, atribui-se:
C
B
=
C
A
2
(4.7)
onde C
B
´e o cr´edito adicionado ao operador que, em etapas anteriores, havia gerado
o indiv´ıduo que, por sua vez, gerou o novo indiv´ıduo.
A cada 10 itera¸c˜oes, a probabilidade dos operadores ´e modificada. Para tal,
soma-se todo o cr
´
´edito atribu´ıdo a um operador durante este intervalo, e divide-se
esse n´umero pela quantidade de filhos gerados (Equa¸c˜ao 4.8). Considera-se o valor
resultante da divis˜ao como o desempenho do operador durante as ´ultimas itera¸c˜oes.
D(O
i
) =
C(O
i
)
N(O
i
)
(4.8)
onde D(O
i
) ´e o desempenho do operador i; C(O
i
) ´e o cr´edito total associado ao
operador i durante as 10 ´ultimas itera¸c˜oes; N(O
i
) ´e o n´umero de filhos gerados
pelo operador i durante as 10 ´ultimas itera¸c˜oes.
Se o desempenho de todos os operadores for nulo, as probabilidades per-
manecem inalteradas. Do contr´ario, os valores de desempenho dos operadores s˜ao
multiplicados por uma constante de modo que a soma de todos eles seja igual a
0.05. As probabilidades atuais dos operadores tamb´em s˜ao multiplicadas por uma
constante, de modo que a soma destas passe a ser 0.95. Ent˜ao, cada nova proba-
bilidade passa a ser, em porcentagem, a soma do valor de sua antiga probabilidade
com o valor de sua medida de desempenho ajustada (Equa¸c˜ao 4.9):
P
novo
(O
i
) = 0.95 × P (O
i
) +
0.05 × D(O
i
)
1≤l≤N
operadores
D(O
l
)
(4.9)
Para evitar que um operador desapare¸ca do processo seletivo em algum mo-
mento da execu¸c˜ao, ´e implementada uma probabilidade m´ınima de 0,02 para cada
operador. Uma vez definidas todas as probabilidades de aplica¸c˜ao, a escolha do
63
operador ´e realizada como uma Sele¸c˜ao por Roleta
2
.
Uma vez que diferentes operadores podem ser mais importantes em diferentes
etapas da execu¸c˜ao do algoritmo, ´e importante assegurar que a atribui¸c˜ao de altos
valores de probabilidades para um operador em um determinado momento n˜ao
implique na estagna¸c˜ao desses valores durante todo o restante da processo. Por esse
motivo, ´e aplicada uma penalidade de 1 cr´edito ao operador que ´e executado 10.000
vezes. Dessa forma, quando se torna rara a gera¸c˜ao de indiv´ıduos com melhor
aptid˜ao que os j´a existentes na popula¸c˜ao, a tendˆencia ´e que as probabilidades dos
operadores retornem `a distribui¸c˜ao uniforme inicial.
Os seis operadores definidos pelo gapf s˜ao:
4.1.5.1 Operador Crossover de 2 pontos (2X)
O operador de recombina¸c˜ao Crossover de 2 pontos (2X) funciona como
o operador de recombina¸c˜ao padr˜ao descrito na se¸c˜ao 3.2.3.2. S˜ao selecionados
aleatoriamente duas posi¸c˜oes no cromossomo, chamadas pontos de corte. Dois
indiv´ıduos parentais s˜ao escolhidos, e os filhos s˜ao gerados atrav´es da c´opia dos
cromossomos parentais, com a troca m´utua dos trechos delimitados pelos dois
pontos de corte.
4.1.5.2 Operador Crossover de M´ultiplos Pontos (MPX)
O operador mpx funciona da mesma maneira que o Crossover de 2 pontos,
mas, ao inv´es de dois, ´e escolhido um n´umero aleat´orio de pontos de corte, calculado
em fun¸c˜ao do comprimento da seq
¨
uˆencia em estudo, de acordo com:
npontos = nint
S
10
(4.10)
onde S ´e o comprimento do cromossomo e nint(n) ´e a fun¸c˜ao que retorna o n´umero
inteiro mais pr´oximo a n.
2
Se¸c˜ao 3.2.2
64
4.1.5.3 Muta¸c˜ao de Segmentos (SMUT)
Esse operador altera o valor φ e ψ de trˆes res´ıduos consecutivos em uma
posi¸c˜ao aleat´oria do cromossomo. Os novos valores tamb´em s˜ao escolhidos aleato-
riamente, dentro do intervalo [−180
◦
, +180
◦
].
4.1.5.4 Muta¸c˜ao Incremental (IMUT)
O operador de muta¸c˜ao incremental (imut) realiza pequenas altera¸c˜oes na es-
trutura da prote´ına, adicionando um valor aleat´orio dentro do intervalo [−10
◦
, +10
◦
]
ao ˆangulo φ ou ψ do res´ıduo corespondente a uma posi¸c˜ao selecionada aleatoria-
mente no cromossomo.
4.1.5.5 Muta¸c˜ao Compensat´oria (CMUT)
Funciona de maneira simular ao operador imut, mas, ap´os adicionar um
valor n a um dos dois ˆangulos diedrais pass´ıveis de modifica¸c˜ao por operadores em
um res´ıduo (φ ou ψ), adiciona o valor −n ao outro ˆangulo, no mesmo res´ıduo.
4.1.5.6 Troca Cont´ıgua (TC)
O operador de Troca Cont´ıgua (tc) provoca uma pequena perturba¸c˜ao na
cadeia, trocando os valores dos ˆangulos φ e ψ de dois res´ıduos consecutivos.
4.1.6 Substitui¸c˜ao Parental
O algoritmo gen´etico implementado pelo gapf ´e do tipo steady state
3
, isto
´e, n˜ao utiliza o conceito de gera¸c˜oes: apenas uma popula¸c˜ao de tamanho fixo
permanece armazenada ao longo de toda a execu¸c˜ao do programa, e cada novo
indiv´ıduo gerado pelos operadores pode ou n˜ao ser incorporado a essa popula¸c˜ao,
substituindo um indiv´ıduo anterior.
As regras que regem a inser¸c˜ao de novos indiv´ıduos da popula¸c˜ao s˜ao esta-
belecidas atrav´es de um mecanismo de crowding
4
, que tem por objetivo possibil-
3
Ver Se¸c˜ao 3.2.4
4
Ver Se¸c˜ao 3.2.5.
65
Tabela 4.2: Classifica¸c˜ao dos amino´acidos como hidrof´obicos e n˜ao-hidrof´obicos
(Callebaut et al., 1997).
Hidrof´obicos
N˜ao-
hidrof´obicos
val ala
ile arg
phe cys
met gln
tyr thr
trp glu
lys
his
ser
asn
asp
pro
gly
itar a buscar simultˆanea de v´arias regi˜oes da hipersuperf´ıcie de busca, atrav´es da
preserva¸c˜ao da diversidade populacional ao longo de toda a execu¸c˜ao.
No gapf, cada novo indiv´ıduo gerado pelo ag s´o ´e incorporado `a popula¸c˜ao
se puder substituir aquele que lhe ´e mais parecido na popula¸c˜ao existente. A
medida do grau de semelhan¸ca entre estruturas, usada no processo de escolha
desse indiv´ıduo, ´e realizada a partir da diferen¸ca na matriz de distˆancia entre os
monˆomeros hidrof´obicos (Distance Matrix Error, dme):
dme =
N
i=1,j>i
(p
ij
− q
ij
)
2
N(n-1)
2
(4.11)
onde N ´e o n´umero de res´ıduos hidrof´obicos da estrutura considerada, p
ij
´e a
distˆancia euclidiana entre a posi¸c˜ao dos Cα do res´ıduos i e j no primeiro indiv´ıduo,
e q
ij
, no segundo. A classifica¸c˜ao dos amino´acidos como hidrof´obicos ou n˜ao-
hidrof´obicos foi realizada de acordo com os crit´erios de Callebaut et al. (1997)
(Tabela 4.1.6).
A principal vantagem do dme como crit´erio de compara¸c˜ao, em rela¸c˜ao ao m´etodo
mais usado para este fim, o desvio m´edio quadr´atico (Root Mean Square Devia-
66
tion, rmsd), ´e n˜ao requerer o alinhamento estrutural pr´evio entre os indiv´ıduos,
uma opera¸c˜ao computacionalmente custosa. Al´em disso, todas as distˆancias p
ij
e q
ij
requeridas para o c´alculo do dme j´a est˜ao previamente calculadas, devido `a
computa¸c˜ao anterior dos termos n˜ao-ligados da fun¸c˜ao de energia.
A inclus˜ao de apenas res´ıduos hidrof´obicos no c´alculo do dme se justifica
pela abordagem do gapf de tentar preservar a diversidade de n´ucleos hidrof´obicos
na popula¸c˜ao, uma vez que o efeito hidrof´obico ´e um dos principais fatores que
impulsionam o enovelamento de uma prote´ına (Cust´odio, 2008).
4.2 GAPF-NMR
O software gapf-nmr ´e uma varia¸c˜ao do gapf desenvolvida neste trabalho
para resolver o problema da resolu¸c˜ao de uma estrutura prot´eica com o aux´ılio de
dados oriundos de experimentos de rmn.
De acordo com o ponto de vista do usu´ario, a principal diferen¸ca entre a
execu¸c˜ao do gapf e a execu¸c˜ao do gapf-nmr ´e que, no segundo caso, al´em da
seq
¨
uˆencia de amino´acidos da prote´ına a se modelada, deve ser passado tamb´em
ao programa um arquivo contendo a lista de restri¸c˜oes de rmn que devem ser
consideradas. A partir deste ponto, a execu¸c˜ao do programa se comporta exata-
mente como no gapf, sendo a maioria das modifica¸c˜oes implementadas de maneira
transparente ao usu´ario.
4.2.1 Arquivos de entrada
As restri¸c˜oes estruturais obtidas a partir dos experimentos de rmn s˜ao co-
mumente armazenadas em arquivos de texto simples formatados de acordo com
alguma conven¸c˜ao especificada pelo autor. Atualmente inexiste um formato uni-
versal padronizado para a formata¸c˜ao desses arquivos, e cada software desenvolvido
para lidar com dados de rmn tem uma especifica¸c˜ao de formatos diferente. O for-
mato usado pelo gapf-nmr ´e uma vers˜ao simplificada do formato usado pelos
programas da fam´ılia x-plor(A. T. Br
¨
unger, 1993), projetado para ser simples
67
de ser lido e gerado automaticamente. gapf-nmr inclui utilit´arios conversores,
desenvolvidos especificamente para este trabalho, que lˆeem arquivos de restri¸c˜ao
baseados no formato do X-PLOR e geram como sa´ıda o arquivo equivalente. O
formato utilizado segue a conven¸c˜ao ilustrada na Figura 4.2.
Cada linha representa uma restri¸c˜ao, a qual consiste em v´arios campos al-
fanum´ericos separados por um ou mais espa¸cos. O primeiro campo especifica o
tipo da restri¸c˜ao. H´a dois tipos de restri¸c˜oes de distˆancia: “edist”, que especifica
a distˆancia entre dois ´atomos pertencentes a res´ıduos diferentes, e “idist”, que es-
pecifica a distˆancia entre dois ´atomos pertencentes ao mesmo res´ıduo. Ambos os
casos seguem a formata¸c˜ao esquematizada na Figura 4.3. Cada restri¸c˜ao especifica
que a distˆancia entre o ´atomo atm
i
do res´ıduo res
i
e o ´atomo atm
j
do res´ıduo res
j
deve ser maior que d − d
minus
e menor que d + d
plus
.
H´a trˆes tipos de restri¸c˜oes de ˆangulos: “phi”, “psi” e “chi”, referentes, re-
spectivamente, aos ˆangulos diedrais φ, ψ e χ
n
. Os trˆes casos seguem a seguinte
formata¸c˜ao esquematizada na Figura 4.4.
A restri¸c˜ao de ˆangulo especifica que o ˆangulo diedral formado entre os quatro
´atomos indicados deve ser maior que φ
0
− ∆φ e menor que φ
0
+ ∆φ. Os campos C
e ed s˜ao opcionais, mantidos por compatibilidade com o formato X-Plor, e n˜ao
s˜ao usados no gapf-nmr.
Em todos os casos, os nomes dos ´atomos mant´em a nomenclatura do gapf,
que, por sua vez, segue a conven¸c˜ao utilizada pelo pdb (H.M.Berman et al., 2000)
(diferentemente da utilizada pelo x-plor).
4.2.2 Resolu¸c˜ao de distˆancias com pseudo-´atomos
´
E comum que restri¸c˜oes de distˆancias oriundas de dados experimentais de
rmn envolvam algum grau de ambig
¨
uidade em rela¸c˜ao aos ´atomos a que se referem.
Tipicamente, pode n˜ao ser poss´ıvel especificar a qual dos dois ou trˆes ´atomos de
hidrogˆenio ligados a um ´atomo de carbono uma determinada restri¸c˜ao se refere. De
acordo com as conven¸c˜oes adotadas pelo gapf-nmr, nas restri¸c˜oes de distˆancia,
68
idist 1 H 1 ha 4.0 2.2 1.0
idist 1 H 1 2HB 4.0 2.2 1.0
idist 1 H 1 1HB 3.0 1.2 0.3
(...)
edist 5 +HD 29 ha 3.0 1.2 1.8
edist 5 +HD 30 H 4.0 2.2 2.5
edist 5 2HG1 30 ha 4.0 2.2 1.0
(...)
phi 1 C 2 N 2 ca 2 C 1.0 -110.0 45.0 2
phi 2 C 3 N 3 ca 3 C 1.0 -60.0 20.0 2
phi 3 C 4 N 4 ca 4 C 1.0 -80.0 35.0 2
(...)
psi 15 N 15 ca 15 C 16 N 1.0 120.0 50.0 2
psi 16 N 16 ca 16 C 17 N 1.0 -10.0 50.0 2
psi 17 N 17 ca 17 C 18 N 1.0 -30.0 50.0 2
(...)
chi 12 N 12 ca 12 cb 12 cg 1.0 -60.0 30.0 2
chi 14 N 14 ca 14 cb 14 cg 1.0 -60.0 30.0 2
chi 19 N 19 ca 19 cb 19 cg1 1.0 -60.0 30.0 2
Figura 4.2: Formato de entrada das restri¸c˜oes do gapf-nmr.
edist/idist res
i
atm
i
res
j
atm
j
d d
minus
d
plus
Figura 4.3: Restri¸c˜oes de distˆancia no arquivo de entrada.
phi/psi/chi
res
i
atm
i
res
j
atm
j
res
k
atm
k
res
l
atm
l
C φ
0
∆φ
ed
Figura 4.4: Restri¸c˜oes de ˆangulos diedrais no arquivo de entrada.
69
o sinal de + na nomenclatura de um ´atomo caracteriza um pseudo-´atomo, isto ´e
uma entidade amb´ıgua que pode representar dois ou mais ´atomos. O ´atomo +HD,
por exemplo, pode significar 1HD, 2HD, 3HD, etc. As restri¸c˜oes de ˆangulos n˜ao
podem conter pseudo-´atomos.
Como cada pseudo-´atomo pode representar diferentes ´atomos em diferentes
posi¸c˜oes, a defini¸c˜ao da distˆancia entre dois pseudo-´atomos, ou entre um pseudo-
´atomo e um ´atomo definido, ´e necessariamente inexata: se m ´e o n´umero de ´atomos
que pode ser representado pelo primeiro pseudo-´atomo, e n, pelo segundo, existe
um conjunto de distˆancias D = {R
i,j
: 0 ≤ i < m, i ≤ j < n}, em que R
ij
´e a dis-
tˆancia entre o ´atomo i e o ´atomo j.
´
E necess´ario transformar esse conjunto em um
´unico valor representativo, R, que ser´a considerado, para efeitos de c´alculo, como
a distˆancia entre os dois pseudo´atomos, ou entre um ´atomo e um pseudo´atomo.
A fun¸c˜ao de resolu¸c˜ao das distˆancias envolvendo pseudo-´atomos no gapf-nmr ´e
similar `a fun¸c˜ao “AVER” usada no X-Plor (A. T. Br
¨
unger, 1993):
R =
0≤i<m
i≤j<n
R
−6
ij
−
1
6
(4.12)
4.2.3 Adapta¸c˜ao das topologias do GROMOS96
A maior parte das restri¸c˜oes de distˆancia oriundas de dados experimentais
de rmn se refere a ´atomos de hidrogˆenio. Entretanto, a maior parte destes ´ato-
mos n˜ao est˜ao representada nas topologias dos amino´acidos utilizadas no campo de
for¸ca cl´assico gromos96 (van Gunsteren e Berendsen, 1987; Schuler et al., 2001).
As ´unicas exce¸c˜oes s˜ao os ´atomos de hidrˆogenio apolares, usados na aproxima¸c˜ao
de ´atomo unido. Seria imposs´ıvel, portanto, utilizando as topologias originais do
gromos96, incluir no gapf-nmr qualquer informa¸c˜ao relacionada `as restri¸c˜oes
de distˆancia. Por esse motivo, foi criada uma nova vers˜ao das topologias, com a
adi¸c˜ao da representa¸c˜ao expl´ıcita dos ´atomos de hidrogˆenio `as estruturas de cada
amino´acido. Essa nova vers˜ao ´e requerida para o funcionamento do gapf-nmr.
Adicionalmente, uma vez que os ´atomos de hidrogˆenio adicionados s˜ao invis´ıveis
70
a todos os termos do campo de for¸ca, as novas topologias podem ser utilizadas
tamb´em na vers˜ao original do gapf, sem qualquer influˆencia na execu¸c˜ao do algo-
ritmo.
4.2.4 Incorpora¸c˜ao das restri¸c˜oes ao GAPF
A codifica¸c˜ao dos gen´otipos dos indiv´ıduos como vetores de ˆangulos diedrais
sugere de imediato um m´etodo para a incorpora¸c˜ao de restri¸c˜oes de ˆangulos, atrav´es
do uso de operadores inteligentes. Assim como ocorre no GENFOLD (Bayley
et al., 1998)
5
, a popula¸c˜ao inicial ´e gerada de modo que todos os indiv´ıduos
estejam dentro do espa¸co de busca vi´avel em rela¸c˜ao a esse tipo de restri¸c˜ao, e
esta propriedade ´e mantida para todos os novos indiv´ıduos que s˜ao criados pelos
operadores.
A incorpora¸c˜ao das restri¸c˜oes de distˆancia, em contraste, n˜ao pode ser feita
diretamente ao gen´otipo. No gapf-nmr, essas restri¸c˜oes s˜ao consideradas a partir
da adi¸c˜ao de um novo termo `a fun¸c˜ao de energia, tamb´em an´alogo ao usado pelo
GENFOLD:
E
NOE
= k
noe
max
n=0
f
n
noe
max
(4.13)
onde noe
max
´e o n´umero m´aximo de restri¸c˜oes de distˆancia, k ´e um parˆametro
ajust´avel pelo usu´ario (por padr˜ao, k = 10.000) e f
n
´e dada por:
f
n
=
R
n
− d
sup
n
, para R
n
> d
sup
n
d
inf
n
− R
n
, para R
n
< d
inf
n
0 , para d
inf
n
< R < d
sup
n
(4.14)
onde R
n
´e a distˆancia entre o par de ´atomos considerado, e d
inf
n
e d
sup
n
s˜ao,
respectivamente, os limites inferior e superior da restri¸c˜ao de distˆancia, isto ´e,
d
inf
n
= d
n
+ d
plus
n
e d
sup
n
= d
n
− d
minus
n
.
5
Se¸c˜ao 3.3.3.
71
4.2.5 Operadores
O gapf-nmr utiliza seis operadores. Quatro deles s˜ao idˆenticos aos descritos
para o gapf na Se¸c˜ao 4.1.5: Crossover de 2 pontos (2X), Crossover de m´ultiplos
pontos (mpx), Muta¸c˜ao de segmentos (smut) e troca cont´ıgua (tc). Dois novos
operadores substituem as muta¸c˜oes incremental (imut) e compensat´oria (cmut):
4.2.5.1 Muta¸c˜ao de Cauchy (MUTACAUCHY)
O operador de muta¸c˜ao de Cauchy seleciona aleatoriamente um dos ˆangulos
φ ou ψ do ind´ıviduo e modifica seu valor, atrav´es da soma de um n´umero aleat´orio
obtido por uma distribui¸c˜ao de Cauchy, que ´e dada por:
C(α, β, x) =
β
π
β
2
+ (x − α)
2
(4.15)
onde os parˆametros utilizados foram α = 0 e β = π.
4.2.5.2 Muta¸c˜ao n˜ao Uniforme (MUTANU)
O operador mutanu escolhe um res´ıduo aleatoriamente. Se este res´ıduo
pertencer a alguma distˆancia de ˆangulo diedral, ´e escolhido aleatoriamente um novo
valor para o ˆangulo φ ou ψ deste res´ıduo, de acordo com uma distribui¸c˜ao uniforme
de probabilidades, dentro do intervalo permitido pela restri¸c˜ao. Do contr´ario, ao
ˆangulo escolhido ´e acrescido o valor a, em graus, dado pela Equa¸c˜ao 4.16:
a = 360 ·
1 − r
(
1−
n
N
)
(4.16)
onde r ´e um n´umero escolhido aleatoriamente entre 0 e 360, n ´e o n´umero de
avalia¸c˜oes j´a efetivadas pelo ag (ou, se aplic´avel, o n´umero de avalia¸c˜oes executadas
desde que se come¸cou a atuar no fragmento atual), e N, ou n´umero total de
avalia¸c˜oes (do algoritmo ou, se aplic´avel, do fragmento atual).
O operador, portanto, tende a aplicar maiores varia¸c˜oes aos ˆangulos escolhi-
dos no in´ıcio da execu¸c˜ao, e estas varia¸c˜oes se tornam progressivamente menores,
72
`a medida que o algoritmo avan¸ca. Esse comportamento permite que o algoritmo
possa experimentar mais agressivamente a busca de regi˜oes diferentes na hiper-
superf´ıcie, no in´ıcio do algoritmo, e refine as estruturas encontradas, nas etapas
finais.
4.2.6 Vers˜oes do Algoritmo
Uma vez que tipicamente uma grande parcela das restri¸c˜oes obtidas por
rmn se refere a intera¸c˜oes entre ´atomos pr´oximos na estrutura prim´aria, pode ser
vantajoso que um algoritmo de resolu¸c˜ao de estruturas por rmn analise prefer-
encialmente essas intera¸c˜oes. Por esse motivo, foram desenvolvidas cinco vers˜oes
diferentes do gapf-nmr, chamadas Walk, MemWalk, Grow, Fold e Full, que ex-
ploram diferentes maneiras de analisar o cromossomo ao longo da execu¸c˜ao do
algoritmo. A vers˜ao Full ´e a mais pr´oxima a um algoritmo gen´etico tradicional,
que opera em todo o cromossomo durante todas as etapas da execu¸c˜ao. A ver-
s˜ao Fold ser´a descrito ao final da se¸c˜ao. As trˆes demais vers˜oes trabalham, em
diferentes momentos da execu¸c˜ao, em uma por¸c˜ao limitada do cromossomo, de-
nominada fragmento, definida por um res´ıduo inicial r
i
e um res´ıduo final r
f
. Um
res´ıduo r, portanto, pertence ao fragmento se r
i
≤ r ≤ r
f
. O fragmento tem o
tamanho inicial predefinido T
frag
= r
f
− r
i
= 20. Para os trˆes m´etodos, antes
do in´ıcio da execu¸c˜ao do algoritmo gen´etico, calcula-se o n´umero de fragmentos
em que se segmentar´a a prote´ına, N
frags
=
2N
res
/T
f rag
, onde N
res
´e o n´umero
de res´ıduos da prote´ına. O n´umero de avalia¸c˜oes que o algoritmo dispender´a em
cada fragmento ´e calculado como N
aval(frag)
=
N
aval
/N
f rags
+1, onde N
aval
´e o n´umero
total de avalia¸c˜oes especificado pelo usu´ario. Em qualquer uma das trˆes vers˜oes,
ao final, ´e executada mais uma rodada de N
aval
avalia¸c˜oes similares `a vers˜ao Full,
em que o fragmento considerado ´e igual a toda a extens˜ao da prote´ına.
73
Figura 4.5: Esquematiza¸c˜ao da vers˜ao Walk.
4.2.6.1 Vers˜ao Walk
Nesta vers˜ao, o fragmento inicial ´e formado pelos T
frag
primeiros res´ıduos,
isto ´e, r
i
= 1, r
f
= T
frag
. Todos os operadores s˜ao aplicados apenas nos res´ıduos
pertencentes ao fragmento em uso. O c´alculo da fun¸c˜ao de energia ´e efetuado
considerando-se apenas os ´atomos pertencentes ao fragmento, e s˜ao consideradas,
para o c´alculo do termo nmr, apenas as restri¸c˜oes de distˆancia que se referem a
dois ´atomos que estejam no fragmento. Ap´os N
aval(frag)
avalia¸c˜oes, acrescenta-se
o valor
T
f rag
/2 tanto a r
i
, quanto a r
f
. Assim, como esquematizado na figura 4.5, o
fragmento efetivamente se move do in´ıcio ao fim da prote´ına ao longo da execu¸c˜ao,
a cada passo fazendo uma intersec¸c˜ao de 50% com a ´area ocupada pelo fragmento
na etapa anterior. Esta vers˜ao ´e a mais similar `a empregada pelo GENFOLD
(Bayley et al., 1998).
Na vers˜ao Walk, assim como nas vers˜oes Grow e MemWalk, que ser˜ao ap-
resentados em seguida, as probabilidades de aplica¸c˜ao de todos os operadores s˜ao
reinicializadas a cada mudan¸ca de fragmento. Al´em disso, nesses casos, e os termos
n e N da equa¸c˜ao 4.16 do operador mutanu passam a se referir, respecivamente,
ao n´umero de avalia¸c˜oes efetuadas no fragmento corrente, e o n´umero total de
avalia¸c˜oes deste fragmento. Isto ´e, a mudan¸ca progressiva de amplitude das mu-
ta¸c˜oes realizadas pelo operador passa a ocorrer v´arias vezes ao longo da execu¸c˜ao
do algoritmo, sendo uma vez para cada fragmento.
Assim como nas outras vers˜oes que envolvem fragmentos, na vers˜ao Walk,
ap´os todos os fragmentos serem avaliados, s˜ao executadas mais N
aval(frag)
avali-
a¸c˜oes em que o c´alculo de energia envolve toda a a prote´ına.
74
Figura 4.6: Esquematiza¸c˜ao da vers˜ao Grow.
4.2.6.2 Vers˜ao Grow
Esta vers˜ao ´e similar a Walk, exceto que o valor de r
i
nunca ´e atualizado.
Como conseq
¨
uˆencia, conforme ilustrado na figura 4.6, o fragmento cresce
T
f rag
/2
res´ıduos a cada N
aval(frag)
avalia¸c˜oes, at´e consistir em toda a prote´ına.
4.2.6.3 Vers˜ao MemWalk
Uma das principais vantagens do m´etodo Walk, em rela¸c˜ao ao m´etodo Grow,
´e o fato de poder concentrar a aplica¸c˜ao de operadores em uma por¸c˜ao pequena
do cromossomo, a cada etapa, facilitando a descoberta de intera¸c˜oes locais mais
rapidamente, com um n´umero comparativamente menor de opera¸c˜oes. Entretanto,
a aplica¸c˜ao desta vers˜ao do algoritmo pode ocasionar o desfavorecimento de bons
indiv´ıduos gerados em etapas anteriores, pois a fun¸c˜ao de energia de cada indiv´ıduo
´e calculada utilizando-se um fragmento do cromossomo.
A vers˜ao MemWalk (forma abreviada de Memory Walk) foi concebido como
um misto das vers˜oes Walk e Grow, de modo a abordar esse problema. Na vers˜ao
MemWalk, o fragmento ´e inicializado e atualizado de maneira idˆentica `a vers˜ao
Walk, no que se refere `a por¸c˜ao do cromossomo em que s˜ao aplicados os operadores.
Entretanto, neste caso, o c´alculo da fun¸c˜ao de energia ´e efetuado como no m´etodo
Grow, isto ´e, considerando sempre r
i
= 0. Desse modo, segmentos da prote´ına cujas
estruturas j´a haviam contribu´ıdo para o c´alculo da aptid˜ao em etapas anteriores
continuam sendo levados em considera¸c˜ao no c´alculo da aptid˜ao da mesma prote´ına
em etapas posteriores. Como conseq
¨
uˆencia, evita-se que sejam perdidas, ao longo
da execu¸c˜ao, as boas estruturas anteriormente geradas.
75
4.2.6.4 Vers˜ao Fold
Assim como ocorre nas vers˜oes do algoritmo Grow e MemWalk, a vers˜ao Fold
envolve uma amplia¸c˜ao gradual do n´umero de restri¸c˜oes utilizadas pelo algoritmo,
ao longo da execu¸c˜ao. Entretanto, ´e a ´unica das vers˜oes (al´em da Full) que n˜ao
utiliza o conceito de fragmentos.
A distˆancia na seq
¨
uˆencia entre dois res´ıduos de amino´acidos ´e definida como
a diferen¸ca entre suas posi¸c˜oes na seq
¨
uˆencia prim´aria da prote´ına. A execu¸c˜ao
na vers˜ao Fold ´e dividida em n =
(maxdist+1)
/4 etapas, onde maxdist ´e a maior
distˆancia na seq
¨
uˆencia encontrada entre pares de ´atomos que participam de uma
restri¸c˜ao de distˆancia. Na primeira etapa (isto ´e, nas primeiras
N
aval
/n execu¸c˜oes),
s˜ao utilizadas apenas as restri¸c˜oes que envolvem pares de res´ıduos cuja distˆancia
na seq
¨
uˆencia ´e menor que 4 res´ıduos. Na segunda, s˜ao adicionadas as restri¸c˜oes
que envolvem pares de res´ıduos com distˆancia na seq
¨
uˆencia menor que 8 res´ıduos,
e assim por diante, aumentanto o limite em 4 res´ıduos por etapa, at´e que, ao final,
todas as restri¸c˜oes s˜ao utilizadas.
Em todas as etapas, a vers˜ao Fold do algoritmo calcula a energia da prote´ına
utilizando todos os seus res´ıduos, isto ´e, r
i
= 0; r
f
= N
res
. Por esse motivo, seu
tempo de execu¸c˜ao ´e equivalente ao da vers˜ao Full, tipicamente bastante superior ao
empregado pelas vers˜oes baseadas em fragmentos. Nesta vers˜ao, as probabilidades
de aplica¸c˜ao de todos os operadores s˜ao reinicializadas a cada etapa de execu¸c˜ao,
e o operador mutanu ´e atualizado ao longo de cada etapa e reinicializado em
seguida, como nas vers˜oes com fragmentos.
A vers˜ao Fold simula o modelo de enovelamento que privilegia, ao in´ıcio,
a forma¸c˜ao de estruturas locais e, posteriormente, o enovelamento gradativo de
estruturas que envolvem intera¸c˜oes globais. Esta ´e a vers˜ao que mais se assemelha
`a empregada pelo modeller (
ˇ
Sali e Blundell, 1993).
76
4.2.7 Substitui¸c˜ao Parental
A substitui¸c˜ao parental no gapf-nmr segue um mecanismo de crowding
semelhante ao descrito na Se¸c˜ao 4.1.6 para o gapf. No caso de determina¸c˜ao de
estruturas por rmn, entretanto, ´e importante que a diversidade da popula¸c˜ao a
ser preservada n˜ao se restrinja ao n´ucleo hidrof´obico, uma vez que as restri¸c˜oes
derivadas de dados experimentais podem envolver res´ıduos de amino´acidos perten-
centes a todas as regi˜oes da prote´ına. Por esse motivo, o c´alculo do dme utilizado
na etapa de substitui¸c˜ao parental do gapf-nmr envolve os Cα de todos os amino´a-
cidos da estrutura, independentemente de sua hidrofobicidade.
77
Cap´ıtulo 5
Resultados e Discuss˜ao
O algoritmo desenvolvido neste trabalho foi avaliado em um conjunto-teste
(Tabela 5) composto por 7 seq
¨
uˆencias pept´ıdicas
1
, cada uma associada a restri¸c˜oes
experimentais oriundas de dados de Ressonˆancia Magn´etica Nuclear. As estruturas
correspondentes a essas seq
¨
uˆencias j´a s˜ao conhecidas, tendo sido determinadas
atrav´es da aplica¸c˜ao de outras metodologias computacionais. Tanto as estruturas,
quanto as restri¸c˜oes experimentais que foram usadas para ger´a-las, est˜ao publi-
camente dispon´ıveis no banco de dados Protein Data Bank (pdb, Berman et al.
(2003)). Como ´e comum em resultados de rmn, para a maioria das mol´eculas
pertencentes ao conjunto-teste, h´a mais de uma estrutura dispon´ıvel no respectivo
arquivo pdb.
Em todos os casos, os arquivos de estruturas depositados no pdb s˜ao acom-
panhados de arquivos que descrevem as restri¸c˜oes experimentais de rmn que foram
usadas para ger´a-los. Estes mesmos arquivos, ap´os convers˜ao de formatos, foram
usados como entrada para o gapf-nmr.
A medida da semelhan¸ca espacial entre duas prote´ınas pode ser avaliada por
meio do c´alculo do desvio m´edio quadr´atico (Root Mean Square Deviation, rmsd)
entre as posi¸c˜oes dos ´atomos do esqueleto pept´ıdico (C, Cα e N) de ambas as
1
Ao longo desta se¸c˜ao, o termo “prote´ına” ser´a aplicado livremente para descrever todas as
seq
¨
uˆencias pet´ıdicas do conjunto-teste, embora algumas destas se refiram apenas a dom´ınios ou
motivos espec´ıficos dentro de uma estrutura prot´eica.
78
Tabela 5.1: Conjunto-teste de prote´ınas utilizado neste estudo.
C´odigo
pdb
Tamanho
Estruturas
Secund´arias
Pontes
dissulfeto
M´etodo
Computacional
1GB4 57 α + β 0 x-plor
1BBL 36 α 0 x-plor
1FYJ 57 α 0 x-plor
1PIT
a
58 α + β 3 Diana/Amber
1OCP
a
67 α 0 x-plor
1AFI 72 α + β 0 x-plor
1KUL
a
108 β 1 x-plor
a
Prote´ınas usadas no conjunto-teste do genfold (Bayley et al., 1998).
79
mol´eculas. O rmsd ´e dado por:
rmsd =
N
i
(x
i
− x
iref
)
2
+ (y
i
− y
iref
)
2
+ (z
i
− z
iref
)
2
N
(5.1)
onde x
i
, y
i
e z
i
representam as coordenadas cartesianas do ´atomo i de uma estrutura
(no caso, o modelo gerado); x
iref
, y
iref
e z
iref
representam as coordenadas do
mesmo ´atomo na estrutura de referˆencia, e N ´e o n´umero total de ´atomos.
O gapf-nmr foi executado 10 vezes para cada prote´ına do conjunto-teste.
Em cada execu¸c˜ao, foram realizadas 100.000 avalia¸c˜oes para cada fragmento. Nas
vers˜oes Full e Fold do algoritmo – as quais n˜ao utilizam fragmentos – foi realizado
um n´umero de avalia¸c˜oes igual ao n´umero total de avalia¸c˜oes realizados para a
mesma prote´ına nas demais vers˜oes. Ao final de cada execu¸c˜ao do programa, foi
escolhida, na popula¸c˜ao final, a estrutura que apresentava menor viola¸c˜ao m´edia
das restri¸c˜oes de distˆancia. O uso desse crit´erio para a escolha da estrutura se justi-
fica pela boa correla¸c˜ao positiva encontrada, em indiv´ıduos das popula¸c˜oes finais,
entre a viola¸c˜ao m´edia das restri¸c˜oes de distˆancia e o rmsd entre as estruturas
geradas e as de referˆencia (Figura 5.1). A estrutura escolhida foi comparada com
todas as estruturas depositadas no pdb para aquela mol´ecula.
Conforme observado por Cust´odio (2008), a utiliza¸c˜ao de valores fixos para os
ˆangulos e comprimentos das liga¸c˜oes atˆomicas no modelo adotado pelo gapf/GAPF-
NMR dificulta a obten¸c˜ao de rmsds menores que 2
˚
A entre as estruturas geradas e
as estruturas de referˆencia. A obten¸c˜ao de valores suficientemente pr´oximos a essa
medida, entretanto, pode sinalizar que ´e poss´ıvel encontrar uma estrutura muito
semelhante `a procurada, com o uso de uma etapa posterior de refinamento, uti-
lizando algum m´etodo de otimiza¸c˜ao local. Valores de rmsd menores que 4
˚
A s˜ao
considerados bons resultados (Kryshtafovych et al., 2005); pode-se considerar que
o enovelamento da prote´ına est´a correto, quando se encontra um rmsd entre 3
˚
A e
4
˚
A (Mart´ı-Renom et al., 2000).
O n´umero de configura¸c˜oes distintas em que seria poss´ıvel testar o gapf-nmr
´e bastante elevado, devido `as diferentes vers˜oes e op¸c˜oes de execu¸c˜ao suportados
80
Figura 5.1: Correla¸c˜ao entre a viola¸c˜ao m´edia das restri¸c˜oes de distˆancia em indi-
v´ıduos da popula¸c˜ao final e seus rmsds em rela¸c˜ao a uma estrutura de referˆencia.
Os dados se referem a uma execu¸c˜ao do algoritmo para dom´ınio β1 modificado da
prote´ına G (Se¸c˜ao 5.1), na vers˜ao MemWalk, com uso do termo de Coulomb.
81
pela implementa¸c˜ao. Uma vez que n˜ao ´e vi´avel testar todas as poss´ıveis config-
ura¸c˜oes em todas as prote´ınas, escolheu-se uma estrutura representativa (c´odigo
pdb: 1GB4) para se efetuarem a maioria dos testes, a fim de se descobrir quais
configura¸c˜oes se revelam mais eficazes. Para as demais prote´ınas, apenas essas
configura¸c˜oes foram utilizadas.
5.1 1GB4; Dom´ınio modificado β1 da prote´ına G
A estrutura pdb de c´odigo 1GB4 ´e uma prote´ına artificial, resultante de
modifica¸c˜oes no dom´ınio β1 da prote´ına G de Streptococcus (Malakauskas e Mayo,
1998) (Figura 5.2). As 47 estruturas depositadas no pdb para esta mol´ecula foram
obtidas com o software x-plor, a partir de um conjunto de restri¸c˜oes de distˆancia
determinadas experimentalmente.
Figura 5.2: Estrutura prim´aria e estrutura secund´aria do dom´ınio β1 da prote´ına
G de Streptococcus c´odigo pdb: 1GB4). (Malakauskas e Mayo, 1998).
A estrutura da prote´ına apresenta trˆes caracter´ısticas que a tornam atrativa
como alvo para o teste da melhor configura¸c˜ao do gapf-nmr (Figura 5.2): (1)
comprimento de 57 res´ıduos, suficientemente grande para representar um desafio
ao algoritmo, mas n˜ao grande demais a ponto de comprometer seu desempenho;
(2) presen¸ca tanto de uma α-h´elice como de folhas β; (3) ausˆencia de pontes dis-
sulf´ıdicas.
As 47 estruturas depositadas no pdb para esta prote´ına tˆem, entre si, um
rmsd m´edio 1,182
˚
A, com desvio-padr˜ao de 0,123
˚
A. O menor rmsd entre duas
estruturas ´e 0,921
˚
A; o maior, 1,507
˚
A.
Um total de 10 configura¸c˜oes diferentes no gapf-nmr foi testado para a
estrutura 1GB4: em diferentes rodadas, foram testadas as cinco vers˜oes do algo-
ritmo descritas na se¸c˜ao 4.2.6, alternando a utiliza¸c˜ao ou n˜ao do termo de energia
82
Tabela 5.2: Resultados obtidos pelo gapf-nmr para o Dom´ınio modificado β1 da
prote´ına G, em rela¸c˜ao `a estrutura de referˆencia depositada sob o c´odigo 1GB4 no
pdb.
Termo de
Coulomb
Vers˜ao do
algoritmo
RMSD
M´edio
Desvio-
Padr˜ao
M´ınimo M´aximo
Sim Walk
5,21
˚
A 0,86
˚
A 3,73
˚
A 6,83
˚
A
Sim MemWalk
2,93
˚
A 0,40
˚
A 2,23
˚
A 3,82
˚
A
Sim Grow
3,47
˚
A 0,65
˚
A 2,31
˚
A 4,86
˚
A
Sim Fold
5,73
˚
A 3,17
˚
A 2,60
˚
A 12,33
˚
A
Sim Full
7,00
˚
A 1,72
˚
A 5,17
˚
A 9,42
˚
A
N˜ao Walk
5,46
˚
A 0,71
˚
A 4,29
˚
A 6,90
˚
A
N˜ao MemWalk
3,00
˚
A 0,50
˚
A 2,33
˚
A 3,98
˚
A
N˜ao Grow
2,96
˚
A 0,24
˚
A 2,49
˚
A 3,55
˚
A
N˜ao Fold
3,88
˚
A 0,82
˚
A 2,58
˚
A 5,46
˚
A
N˜ao Full
6,57
˚
A 1,53
˚
A 4,62
˚
A 9,08
˚
A
de Coulomb (4.3). Para cada configura¸c˜ao, foram realizadas 10 execu¸c˜oes diferentes
do algoritmo. A estrutura que apresentava menor viola¸c˜ao m´edia das restri¸c˜oes de
distˆancia foi escolhida ao final de cada execu¸c˜ao, e comparada `as 47 estruturas
depositadas no pdb. Os resultados est˜ao dispostos na tabela 5.2.
Conforme ´e poss´ıvel observar na Tabela 5.2, as vers˜ao MemWalk e Grow se
mostram mais eficazes que as demais na obten¸c˜ao de uma estrutura pr´oxima `a de
referˆencia. N˜ao ´e poss´ıvel determinar inequivocamente se o termo de Coulomb na
fun¸c˜ao de energia melhora ou n˜ao o desempenho do algoritmo. Por esse motivo,
nos testes referentes aos demais elementos do conjunto-teste, ser˜ao utilizadas ape-
nas as vers˜oes MemWalk e Grow, alternando execu¸c˜oes com e sem a inclus˜ao do
termo de Coulomb. As Figuras 5.2-5.5 ilustram os resultados obtidos com a vers˜ao
MemWalk, sem o termo de Coulomb.
A Tabela 5.3 exibe o tempo m´edio de execu¸c˜ao do gapf-nmr em cada uma
de suas vers˜oes, em uma m´aquina Intel Core 2 Duo e6550 (2.33GHz), com
2GB de mem´oria ram.
Para avaliar a importˆancia do mecanismo de M´ultiplos M´ınimos
2
no desem-
penho do gapf-nmr, foi realizada uma s´erie de 10 execu¸c˜oes da vers˜ao MemWalk
2
Descrito na Se¸c˜ao 4.1.6.
83
Tabela 5.3: Tempo m´edio de execu¸c˜ao do gapf em diferentes configura¸c˜oes para
o Dom´ınio modificado β1 da prote´ına G, em rela¸c˜ao `a estrutura de referˆencia
depositada sob o c´odigo 1GB4 no pdb em uma m´aquina Intel Core 2 Duo
e6550 (2.33GHz), com 2GB de mem´oria ram.
Termo de
Coulomb
Vers˜ao do algoritmo
Tempo m´edio de
execu¸c˜ao
Sim Walk 02h16min48s
Sim MemWalk 04h11min18s
Sim Grow 04h06min41s
Sim Fold 07h03min01s
Sim Full 07h01min32s
N˜ao Walk 01h17min39s
N˜ao MemWalk 02h33min33s
N˜ao Grow 02h28min41s
N˜ao Fold 04h01min24s
N˜ao Full 04h04min12s
84
Tabela 5.4: Resultados obtidos pelo gapf-nmr para o Dom´ınio modificado β1 da
prote´ına G, em rela¸c˜ao `a estrutura de referˆencia depositada sob o c´odigo 1GB4 no
pdb, sem o mecanismo de crowing (M´ultiplos M´ınimos).
Termo de
Coulomb
Vers˜ao do
algoritmo
RMSD
M´edio
Desvio-
Padr˜ao
M´ınimo M´aximo
Sim MemWalk
6,29
˚
A 1,13
˚
A 4,14
˚
A 7,86
˚
A
N˜ao MemWalk
5,64
˚
A 2,5
˚
A 2,76
˚
A 11,65
˚
A
com um mecanismo de steady state tradicional, sem crowding. Os resultados obti-
dos est˜ao dispostos na Tabela 5.4 e s˜ao claramente inferiores as obtidos na Tabela
5.2, para o mesmo m´etodo, com o crowding habilitado.
A Figura ilustra a varia¸c˜ao de todos os termos de energia ao longo da exe-
cu¸c˜ao do algoritmo.
´
E poss´ıvel observar os picos de energia ocorridos sempre que
um novo fragmento passa a ser considerado, seguidos por uma r´apida suaviza¸c˜ao.
A Figura 5.4 compara uma das estruturas calculadas pelo programa com
uma estrutura de referˆencia e indica as restri¸c˜oes de distˆancia mais fortemente
violadas na estrutura calculada. Pode-se observar que o algoritmo foi capaz de
encontrar uma estrutura bastante parecida com a de referˆencia, com o mesmo en-
ovelamento e, aproximadamente, as mesmas estruturas secund´arias. As restri¸c˜oes
menos satisfeitas se concentram predominantemente na regi˜ao das folhas β.
Foram avaliadas as viola¸c˜oes das restri¸c˜oes de distˆancia para as 10 estru-
turas finais obtidas atrav´es das 10 execu¸c˜oes do algoritmo na vers˜ao MemWalk,
sem o termo de Coulomb. Entre estas estruturas, ocorre viola¸c˜ao em 34,44% das
restri¸c˜oes de distˆancia. A viola¸c˜ao m´edia foi de 1,16
˚
A, e as restri¸c˜oes menos sat-
isfeitas em cada estrutura tˆem, em m´edia, uma viola¸c˜ao de 6,87
˚
A. Em contraste,
nas estruturas de referˆencia, somente 15,56% das restri¸c˜oes, em m´edia, n˜ao est˜ao
satisfeitas, com uma viola¸c˜ao m´edia de 0,07
˚
A e uma viola¸c˜ao m´axima m´edia de
apenas 0,26
˚
A. Tal diferen¸ca pode estar relacionada `a dificuldade de se obter es-
truturas com rmsd menor que 2
˚
A em rela¸c˜ao `a referˆencia. Uma etapa final de
otimiza¸c˜ao local que n˜ao fosse limitada por ˆangulos e distˆancias predeterminados
e levasse em considera¸c˜ao as informa¸c˜oes fornecidas pelas restri¸c˜oes de distˆancia
85
poderia certamente ser utilizada para refinar os resultados obtidos pelo ag.
A Figura 5.5 mostra todas as restri¸c˜oes de distˆancia utilizadas para o c´alculo
da estrutura da prote´ına 1GB4. Cada restri¸c˜ao ´e representada por uma linha que
une os dois res´ıduos de amino´acidos correspondentes aos ´atomos que a comp˜oem.
A cor da linha indica o grau de viola¸c˜ao da restri¸c˜ao na estrutura final: linhas
azuis representam restri¸c˜oes com pouca ou nenhuma viola¸c˜ao; linhas vermelhas,
restri¸c˜oes fortemente violadas. Pode-se perceber, no gr´afico, que as restri¸c˜oes mais
violadas na estrutura gerada se referem a res´ıduos bastante distantes na seq
¨
uˆencia.
Esse padr˜ao se tornar´a consistente nos testes seguintes e se deve ao fato de que
as restri¸c˜oes entre res´ıduos muito pr´oximos na seq
¨
uˆencia geralmente podem ser
resolvidas com operadores de efeito local, sem efetuar altera¸c˜oes significativas na
estrutura.
`
A medida que cresce a distˆancia na seq
¨
uˆencia dos res´ıduos envolvidos,
mudan¸cas mais expressivas na estrutura passam a ser necess´arias para satisfazer a
restri¸c˜ao, e tais mudan¸cas costumam ser penalizadas pelo algoritmo, por ocasionar
um aumento na viola¸c˜ao de outras restri¸c˜oes. Tal fato explica a maior facilidade
encontrada pelo gapf-nmr de encontrar as α-h´elices das estruturas estudadas, e a
predominˆancia de altas viola¸c˜oes de restri¸c˜oes entre as folhas β, onde as intera¸c˜oes
de longa distˆancia na seq
¨
uˆencia s˜ao essenciais para a estabilidade da estrutura.
86
Figura 5.3: Varia¸c˜ao dos termos da fun¸c˜ao de aptid˜ao ao longo de uma execu¸c˜ao da
vers˜ao MemWalk do gapf-nmr, com termo de Coulomb, para o dom´ınio modifi-
cado β1 da prote´ına G (c´odigo pdb: 1GB4). A cada 100.000 execu¸c˜oes, o algoritmo
passa a operar em um novo fragmento.
Figura 5.4: Esquematiza¸c˜ao das viola¸c˜oes de distˆancia mais violadas em (a) uma
das estruturas finais geradas pelo gapf-nmr para o Dom´ınio modificado β1 da
prote´ına G, usando a vers˜ao MemWalk do algoritmo, sem o termo de Coulomb (b)
uma estrutura de referˆencia (c´odigo pdb: 1GB4).
87
Figura 5.5: Mapa de viola¸c˜ao de restri¸c˜oes do dom´ınio modificado β1 da prote´ına
G (ver texto).
(a) Estrutura gerada. (b) Estrutura de referˆencia experimental.
88
5.2 1BBL; Dom´ınio de liga¸c˜ao a E3 da cadeia E2o do complexo
2-OGDH de E. coli
O complexo multi-enzim´atico 2-Oxoglutarato Desidrogenase (2-OGDH) est´a
entre os respons´aveis pela descarboxila¸c˜ao oxidativa de diferentes substratos, re-
sultando na produ¸c˜ao de acil-CoA. Em E. coli, esse complexo ´e formado por 3
subunidades enzim´aticas: E1o, E2o e e3. O dom´ınio de liga¸c˜ao a e3 da cadeia
E2o do complexo 2-OGDH foi estudado por Robien et al. (1992) e teve sua estru-
tura determinada atrav´es da aplica¸c˜ao do software x-plor a dados de restri¸c˜oes
estruturais obtidos atrav´es de experimentos de rmn. O resultado foi depositado
no pdb como uma ´unica estrutura final, sob o c´odigo 1BBL.
Figura 5.6: Estrutura prim´aria e estrutura secund´aria do dom´ınio de liga¸c˜ao a e3
da cadeia E2o do complexo 2-OGDH de E. coli (c´odigo pdb: 1BBL).
A estrutura depositada no pdb tem comprimento de 37 res´ıduos (Figura
5.6) e ´e formada principalmente por duas α-h´elices, cada uma com comprimento
de 7 res´ıduos, dispostas paralelamente no espa¸co e unidas por uma longa regi˜ao
composta por turnos e uma pequena α-h´elice de apenas 4 res´ıduos. Devido ao seu
comprimento relativamente curto e `a ausˆencia de folhas β ou pontes dissulf´ıdicas,
esta pode ser considerada, entre as estruturas inclu´ıdas no conjunto-teste, a que
deve apresentar menos obst´aculos ao bom desempenho de sua resolu¸c˜ao pelo gapf-
nmr.
De fato, conforme disposto na Tabela 5.5, o resultado m´edio de rmsd obtido
pela vers˜ao do gapf-nmr que n˜ao utiliza o termo de Coulomb foi melhor que o
limiar de 3
˚
A; ainda, o resultado de algumas execu¸c˜oes foi melhor que 2
˚
A, que ´e,
aproximadamente, o limite esperado da metodologia com as restri¸c˜oes de distˆancias
de liga¸c˜ao e ˆangulos entre liga¸c˜oes impostas.
A Figura 5.7 mostra que, no in´ıcio da cada fragmento, a energia foi otimizada
89
Tabela 5.5: Resultados obtidos pelo gapf-nmr para o dom´ınio de liga¸c˜ao a e3 da
cadeia E2o do complexo 2-OGDH de E. coli, em rela¸c˜ao `a estrutura de referˆencia
depositada sob o c´odigo 1BBL no pdb.
Vers˜ao do
algoritmo
Termo de
Coulomb
RMSD
M´edio
Desvio-
Padr˜ao
M´ınimo M´aximo
MemWalk Sim
3,42
˚
A 0,47
˚
A 2,59
˚
A 4,2
˚
A
MemWalk N˜ao
2,63
˚
A 0,64
˚
A 1,65
˚
A 3,53
˚
A
Grow Sim
3,53
˚
A 0,47
˚
A 2,52
˚
A 4,36
˚
A
Grow N˜ao
3,33
˚
A 0,59
˚
A 2,52
˚
A 4,23
˚
A
muito rapidamente; em seguida, permaneceu consistentemente baixa. O n´umero
de execu¸c˜oes utilizado foi, portanto, bem superior ao m´ınimo necess´ario para a
otimiza¸c˜ao dessa estrutura. A Figura 5.8 mostra uma das estruturas geradas pelo
gapf-nmr, em compara¸c˜ao a uma estrutura de referˆencia. A Figura 5.9 compara
as viola¸c˜oes das restri¸c˜oes de distˆancia em uma estrutura gerada com as de uma
estrutura de referˆencia. Para essas trˆes figuras, assim como para todas as seguintes,
as mesmas conven¸c˜oes das Figuras , 5.4 e 5.5 foram utilizadas.
90
Figura 5.7: Varia¸c˜ao dos termos de energia ao longo da execu¸c˜ao do algoritmo,
para o dom´ınio de liga¸c˜ao a e3 da cadeia E2o do complexo 2-OGDH de E. coli.
Figura 5.8: (a) Estrutura final calculada por uma das execu¸c˜oes do gapf NMR
para o dom´ınio de liga¸c˜ao a e3 da cadeia E2o do complexo 2-OGDH de E. coli.
As liga¸c˜oes em vermelho indicam as restri¸c˜oes de distˆancia mais violadas. (b)
Estrutura de referˆencia (c´odigo pdb: 1BBL).
91
Figura 5.9: Mapa de viola¸c˜ao de restri¸c˜oes do dom´ınio de liga¸c˜ao a e3 da cadeia
E2o do complexo 2-OGDH de E. coli. (a) Estrutura gerada. (b) Estrutura de
referˆencia experimental.
92
5.3 1FYJ; Motivo EPRS-R1 da prote´ına Glutamil-Prolil-tRNA
sintetase (EPRS-R1)
Aminoacil-tRNA sintetases (arss) s˜ao prote´ınas que catalisam a liga¸c˜ao de
amino´acidos a seus respectivos tRNAs, no processo de s´ıntese prot´eica. A Glutamil-
Prolil-tRNA sintetase (eprs) ´e uma ars bifuncional, isto ´e, est´a envolvida no
processo de liga¸c˜ao de dois amino´acidos diferentes: o Glutamato e a Prolina. Em
eucariotos, a eprs est´a contida em um complexo multiprote´ına, que envolve, al´em
de outras arss, um conjunto de prote´ınas auxiliares (Jeong et al., 2000).
Figura 5.10: Estrutura prim´aria e estrutura secund´aria do motivo eprs-r1 da
prote´ına Glutamil-Prolil-tRNA sintetase (c´odigo pdb: 1FYJ).
A estrutura do motivo eprs-r1 da prote´ına eprs foi determinada por Jeong
et al. (2000). Esse motivo tem um comprimento de 57 res´ıduos e consiste princi-
palmente em duas α-h´elices, cada uma com comprimento de 20 res´ıduos, dispostas
paralelamente entre si e unidas por uma volta de 4 res´ıduos (Figura 5.10). Os
´ultimos 10 res´ıduos c-terminais da estrutura n˜ao tˆem estrutura est´avel.
O arquivo depositado no pdb para esta prote´ına (c´odigo 1FYJ) cont´em 20
estruturas. S´o foram considerados os resultados obtidos na parte est´avel da es-
trutura – neste caso, os res´ıduos 1-47. O rmsd m´edio entre esses res´ıduos nas
estruturas de referˆencia ´e de 1,52
˚
A, com desvio-padr˜ao de 0,16
˚
A; O menor rmsd
entre duas estruturas ´e de 1,22
˚
A; o maior, 1,81
˚
A.
A Tabela 5.6 mostra a compara¸c˜ao entre os resultados obtidos pelo gapf-
nmr e as estruturas de referˆencia. Nesse caso, tamb´em foi obtido um resultado
ligeiramente melhor, quando n˜ao se usou o termo de Coulomb na fun¸c˜ao de energia.
A Figura 5.11 ilustra a varia¸c˜ao dos valores calculados para os termos que
comp˜oem a fun¸c˜ao de aptid˜ao do ag, ao longo de uma rodada completa. A exe-
cu¸c˜ao de cada fragmento inicia com uma r´apida queda da energia da popula¸c˜ao,
93
Tabela 5.6: Resultados obtidos pelo gapf-nmr para a prote´ına eprs-r1, em
rela¸c˜ao `as estruturas de referˆencia depositadas sob o c´odigo 1FYJ no pdb.
Vers˜ao do
algoritmo
Termo de
Coulomb
RMSD
M´edio
Desvio-
Padr˜ao
M´ınimo M´aximo
MemWalk Sim
5,1
˚
A 1,41
˚
A 2,46
˚
A 7,71
˚
A
MemWalk N˜ao
4,57
˚
A 0,92
˚
A 3,07
˚
A 6,35
˚
A
Grow Sim
4,99
˚
A 0,89
˚
A 3,43
˚
A 6,28
˚
A
Grow N˜ao
5,56
˚
A 0,8
˚
A 4,06
˚
A 7,01
˚
A
seguida por um per´ıodo comparativamente longo de estagna¸c˜ao. Tal comporta-
mento indica que os resultados encontrados nestes testes provavelmente poderiam
ser reproduzidos em uma execu¸c˜ao com um n´umero reduzido de avalia¸c˜oes.
A Figura 5.12 compara uma das estruturas geradas pelo gapf-nmr com uma
estrutura de referˆencia. Pode-se notar que, embora a estrutura regular que forma
as duas α-h´elices que comp˜oem a estrutura nativa n˜ao tenha sido reproduzida
com perfei¸c˜ao, pˆode-se chegar a uma aproxima¸c˜ao do enovelamento global correto,
a qual provavelmente poderia ser melhorada atrav´es do uso de um m´etodo de
otimiza¸c˜ao local.
Adicionalmente, ´e importante observar que as estruturas encontradas pelo
ag apresentaram viola¸c˜ao m´edia das restri¸c˜oes de distˆancia menor que as estru-
turas de referˆencia, conforme ilustrado na Figura 5.13. Na estrutura de referˆencia,
os maiores ´ındices de viola¸c˜ao nas restri¸c˜oes de distˆancias foram observados en-
tre res´ıduos de amin´acidos pr´oximos na seq
¨
uˆencia, nas regi˜oes da prote´ına que
formaram as α-h´elices.
94
Figura 5.11: Varia¸c˜ao dos termos de energia ao longo da execu¸c˜ao do algoritmo,
para a prote´ına eprs-r1.
Figura 5.12: (a) Estrutura final calculada por uma das execu¸c˜oes do gapf-nmr
para a prote´ına eprs-r1. As liga¸c˜oes em vermelho indicam as restri¸c˜oes de dis-
tˆancia mais violadas. (b) Estrutura de referˆencia (c´odigo pdb: 1FYJ).
95
Figura 5.13: Mapa de viola¸c˜ao de restri¸c˜oes da prote´ına eprs-r1. (a) Estrutura
gerada. (b) Estrutura de referˆencia experimental.
96
5.4 1PIT; Prote´ına Inibidora da Tripsina Pancre´atica (BPTI)
A estrutura tridimensional da Prote´ına Inibidora da Tripsina Pancre´atica
(bpti, Bovine Pancreatic Trypsin Inhibitor) em solu¸c˜ao aquosa foi determinada a
partir de dados experimentais de nmr por Berndt et al. (1992). O arquivo est´a
depositado no pdb sob o c´odigo 1PIT. Esta ´e uma das estruturas participantes do
conjunto-teste do genfold
3
(Bayley et al., 1998), e ´e a ´unica prote´ına testada
no presente trabalho cujas estruturas de referˆencia depositadas no pdb n˜ao foram
geradas com o x-plor; antes, foi utilizada uma combina¸c˜ao do diana
4
(P. G
¨
untert
e K. W
¨
uthrich, 1991) e do pacote de modelagem molecular amber (Pearlman et al.,
1995). Antes de ser usado como entrada no gapf-nmr, o arquivo de restri¸c˜oes
experimentais depositado no pdb foi convertido ao formato x-plor com o aux´ılio
da su´ıte de aplicativos aqua (Laskowski et al., 1996).
Figura 5.14: Estrutura prim´aria e estrutura secund´aria da prote´ına Prote´ına In-
ibidora da Tripsina Pancre´atica (c´odigo pdb: 1PIT).
A prote´ına bpti tem um comprimento de 58 res´ıduos de amino´acidos, aprox-
imadamente o mesmo tamanho que a estrutura analisada anteriormente, por´em
apresenta caracter´ısticas estruturais comparativamente mais desafiadoras ao ag:
al´em de ser formada por uma combina¸c˜ao de folhas β e α-h´elices, unidas por longas
regi˜oes de loops e voltas, a estrutura da prote´ına ´e estabilizada por trˆes liga¸c˜oes
dissulf´ıdicas (Figura 5.14), cuja forma¸c˜ao n˜ao ´e explicitamente prevista pelo algo-
ritmo, nem indicada de maneira inequ´ıvoca pelas restri¸c˜oes de distˆancia.
Neste trabalho, assim como no genfold, foram considerados para todos os
c´alculos de rmsd apenas os res´ıduos 2-56, considerados como a parte est´avel da
estrutura. O rmsd m´edio entre esses res´ıduos nas estruturas de referˆencia ´e de
3
Se¸c˜ao 3.3.3.
4
Antecessor do software dyana (P. G
¨
untert et al., 1997), descrito na se¸c˜ao 1.9.
97
Tabela 5.7: Resultados obtidos pelo gapf-nmr para a prote´ına bpti, em rela¸c˜ao
`as estruturas de referˆencia depositadas sob o c´odigo 1PIT no pdb. Na ´ultima linha,
para efeito de compara¸c˜ao, ´e exibido o resultado obtido pelo genfold.
Vers˜ao do
algoritmo
Termo de
Coulomb
RMSD
M´edio
Desvio-
Padr˜ao
M´ınimo M´aximo
MemWalk Sim
4,33
˚
A 1,04
˚
A 2,68
˚
A 6,91
˚
A
MemWalk N˜ao
3,46
˚
A 0,36
˚
A 3,32
˚
A 4,7
˚
A
Grow Sim
5,77
˚
A 2,75
˚
A 3,25
˚
A 13,27
˚
A
Grow N˜ao
5,1
˚
A 0,88
˚
A 4,03
˚
A 7,2
˚
A
genfold -
4,34
˚
A
N/D N/D N/D
1,54
˚
A, com desvio-padr˜ao de 0,14
˚
A. O menor rmsd entre duas estruturas ´e de
1,38
˚
A; o maior, 2,00
˚
A.
Conforme disposto na Tabela 5.7, o gapf-nmr foi capaz de encontrar re-
sultados equivalentes aos do genfold, quando se utilizou o termo de Coulomb
na fun¸c˜ao de energia. Nos testes em que n˜ao se usou o termo de Coulomb, foram
encontrados resultados superiores aos do genfold.
A Figura 5.15 compara uma das estruturas geradas pelo gapf-nmr com
uma estrutura de referˆencia. A compara¸c˜ao das posi¸c˜oes dos res´ıduos de ciste´ına,
indicados na figura para ambas as estruturas, permite a percep¸c˜ao de que um dos
principais empecilhos `a forma¸c˜ao de uma estrutura corretamente enovelada pelo
ag foi a dificuldade de forma¸c˜ao das pontes dissulf´ıdicas.
A Figura 5.16 exibe a varia¸c˜ao dos termos da fun¸c˜ao de energia ao longo da
execu¸c˜ao. A energia permanece com valores razoavelmente baixos at´e a execu¸c˜ao
do segundo fragmento (res´ıduos 1 a 30, na vers˜ao MemWalk). A partir do terceiro
fragmento (res´ıduos 1 a 40), as pontes dissulf´ıdicas passam a ser importantes para a
estabiliza¸c˜ao da estrutura, e o algoritmo passa a encontrar dificuldades em reduzir
expressivamente a energia da popula¸c˜ao.
A Figura 5.17 compara as viola¸c˜oes nas restri¸c˜oes de distˆancia entre uma
estrutura gerada e uma estrutura de referˆencia.
98
Figura 5.15: (a) Estrutura final calculada por uma das execu¸c˜oes do gapf-nmr
para a prote´ına bpti. (b) Estrutura de referˆencia (c´odigo pdb: 1PIT). Em ambas
as figuras, est˜ao indicados os res´ıduos de ciste´ına.
Figura 5.16: Varia¸c˜ao dos termos de energia ao longo da execu¸c˜ao do algoritmo,
para a prote´ına bpti.
99
Figura 5.17: Mapa de viola¸c˜ao de restri¸c˜oes da prote´ına bpti. (a) Estrutura
gerada. (b) Estrutura de referˆencia experimental.
100
5.5 1OCP; Dom´ınio POU
H
da prote´ına OCT3
A prote´ına oct3 ´e expressa nas c´elulas embrion´arias de camundongos e reg-
ula a diferencia¸c˜ao do tronco nervoso. O dom´ınio pou
H
dessa prote´ına, que tem
importˆancia em mecanismos de afinidade com o dna, teve sua estrutura determi-
nada atrav´es de dados experimentais de rmn, com o aux´ılio do software x-plor,
por Morita et al. (1995). Essa estrutura foi uma das trˆes utilizadas no conjunto-
teste do genfold.
Figura 5.18: Estrutura prim´aria e estrutura secund´aria do dom´ınio pou
H
da pro-
te´ına oct3 (c´odigo pdb: 1OCP).
O dom´ınio pou
H
´e composto por uma seq
¨
uˆencia de 67 res´ıduos de amino´aci-
dos. Os primeiros 15 res´ıduos da regi˜ao n-terminal da prote´ına n˜ao formam uma
estrutura bem definida, assim como os ´ultimos 7 res´ıduos c-terminais. Entre essas
regi˜oes, formam-se trˆes α-h´elices est´aveis (Figura 5.18).
O arquivo depositado no pdb para esta prote´ına (c´odigo 1OCP) cont´em 20
estruturas. O rmsd m´edio entre a parte est´avel dessas estruturas (res´ıduos 16-60)
´e de 1,49
˚
A, com desvio-padr˜ao de 0,13
˚
A. O menor rmsd entre duas estruturas ´e
de 1,31
˚
A; o maior, 1,67
˚
A. A varia¸c˜ao estrutural nas se¸c˜oes inst´aveis que comp˜oem
as regi˜oes n-terminal e c-terminal nessas estruturas de referˆencia ´e extremamente
alta, por isso, essas regi˜oes n˜ao ser˜ao consideradas nessa an´alise – o mesmo pro-
cedimento adotado nos testes do genfold.
A Tabela 5.8 mostra os resultados obtidos. Os desvios-padr˜ao encontrados
entre os resultados das v´arias execu¸c˜oes de cada algoritmo para esta prote´ına est˜ao
entre os maiores deste estudo, indicando uma grande diversidade de solu¸c˜oes finais
encontradas. As melhores execu¸c˜oes resultaram em estruturas bastante pr´oximas
`as de referˆencia, embora outras tenham gerado estruturas que podem ser consid-
eradas insatisfatoriamente distantes. Em m´edia, os resultados para esta prote´ına
101
Tabela 5.8: Resultados obtidos pelo gapf-nmr para o dom´ınio pou
H
da prote´ına
oct3, em rela¸c˜ao `as estruturas de referˆencia depositadas sob o c´odigo 1OCP no
pdb.
Vers˜ao do
algoritmo
Termo de
Coulomb
RMSD
M´edio
Desvio-
Padr˜ao
M´ınimo M´aximo
MemWalk Sim
6,25
˚
A 2,11
˚
A 2,75
˚
A 8,71
˚
A
MemWalk N˜ao
7,24
˚
A 1,76
˚
A 3,97
˚
A 10,25
˚
A
Grow Sim
6,11
˚
A 2,13
˚
A 3,73
˚
A 9,19
˚
A
Grow N˜ao
6,5
˚
A 2,06
˚
A 3,55
˚
A 8,98
˚
A
genfold -
3,74
˚
A
N/D N/D N/D
n˜ao foram melhores que os obtidos pelo genfold.
A Figura 5.19 mostra a varia¸c˜ao dos termos da fun¸c˜ao de energia em uma
das execu¸c˜oes do ag. A Figura 5.20 compara uma das estruturas geradas com
uma estrutura de referˆencia. A estrutura indicada foi uma das melhores geradas
pelo algoritmo; pode-se notar que, neste caso, as trˆes α-h´elices que caracterizam a
parte est´avel da estrutura foram reproduzidas quase integralmente. A Figura 5.21
compara o mapa de viola¸c˜oes da mesma estrutura indicada na figura anterior com
uma estrutura de referˆencia.
102
Figura 5.19: Varia¸c˜ao dos termos de energia ao longo da execu¸c˜ao do algoritmo,
para o dom´ınio pou
H
da prote´ına oct3.
Figura 5.20: (a) Estrutura final calculada por uma das execu¸c˜oes do gapf NMR
para o dom´ınio pou
H
da prote´ına oct3. As liga¸c˜oes em vermelho indicam as
restri¸c˜oes de distˆancia mais violadas. (b) Estrutura de referˆencia (c´odigo pdb:
1OCP).
103
Figura 5.21: Mapa de viola¸c˜ao de restri¸c˜oes do dom´ınio pou
H
da prote´ına oct3..
(a) Estrutura gerada. (b) Estrutura de referˆencia experimental.
104
Tabela 5.9: Resultados obtidos pelo gapf-nmr para a prote´ına MerP, em rela¸c˜ao
`as estruturas de referˆencia depositadas sob o c´odigo 1AFI no pdb.
Vers˜ao do
algoritmo
Termo de
Coulomb
RMSD
M´edio
Desvio-
Padr˜ao
M´ınimo M´aximo
MemWalk Sim
5,39
˚
A 2,16
˚
A 3,39
˚
A 9,67
˚
A
MemWalk N˜ao
4,92
˚
A 1,51
˚
A 3,54
˚
A 8,58
˚
A
Grow Sim
5,72
˚
A 2,22
˚
A 2,69
˚
A 8,52
˚
A
Grow N˜ao
4,35
˚
A 0,65
˚
A 3,47
˚
A 5,84
˚
A
5.6 1AFI; Prote´ına Bacterial Peripl´asmica MerP
A prote´ına bacterial MerP ´e uma das prote´ınas envolvidas em um sistema
bacterial de desintoxica¸c˜ao mercurial que transforma a forma reagente do merc´urio
em sua forma vol´atil. A MerP est´a envolvida nas etapas iniciais de reconhecimento,
liga¸c˜ao e transporte do merc´urio. As formas reduzida e ligada ao merc´urio da
prote´ına MerP de Shigella flexineri tiveram sua estrutura determinada por Steele
e Opella (1997) atrav´es de dados experimentais de rmn, com o uso do programa
x-plor. A forma reduzida da prote´ına, que ser´a utilizada como referˆencia nesse
trabalho, foi depositada no pdb como um conjunto de 20 estruturas, sob o c´odigo
1AFI. O rmsd m´edio entre essas estruturas ´e 1,17
˚
A, com desvio-padr˜ao de 0,09
˚
A.
O menor rmsd entre duas estruturas ´e de 1,01
˚
A; o maior, 1,33
˚
A.
Figura 5.22: Estrutura prim´aria e estrutura secund´aria da prote´ına MerP (c´odigo
pdb: 1AFI).
A prote´ına MerP tem comprimento de 72 amino´acidos (Figura 5.22) e sua
estrutura secund´aria ´e formada por duas α-h´elices e quatro fitas β.
´
E, portanto,
uma estrutura mais desafiadora ao algoritmo que as anteriores, exceto pelo fato de
n˜ao formar pontes dissulf´ıdicas.
A Tabela 5.9 mostra os resultados obtidos pelo programa para a prote´ına
MerP. Conforme esperado, as estruturas geradas para esta prote´ına s˜ao menos
105
Figura 5.23: (a) Estrutura final calculada por uma das execu¸c˜oes do gapf NMR
para a prote´ına MerP. As liga¸c˜oes em vermelho indicam as restri¸c˜oes de distˆancia
mais violadas. (b) Estrutura de referˆencia (c´odigo pdb: 1AFI).
precisas que as anteriores; ainda assim, como pode ser observado na Figura 5.23,
a geometria geral da estrutura de referˆencia foi encontrada com um grau razo´avel
de aproxima¸c˜ao. A Figura 5.24 mostra a varia¸c˜ao dos termos de energia ao longo
de uma execu¸c˜ao.
106
Figura 5.24: Varia¸c˜ao dos termos de energia ao longo da execu¸c˜ao do algoritmo,
para a prote´ına MerP.
107
5.7 1KUL; Dom´ınio de liga¸c˜ao ao amido granular (SBD) da Gli-
coamilase
Glicoamilases s˜ao uma classe de amilases, isto ´e, enzimas que degradam
amido em glicose. A enzima glicoamilase 1 ´e encontrada no fungo Aspergillus
niger e consiste em dois dom´ınios: o dom´ınio catal´ıtico n-terminal e o dom´ınio c-
terminal de liga¸c˜ao ao amido granular (starch binding domain, sbd). A estrutura
do dom´ınio sbd dessa enzima foi determinada por Sorimachi et al. (1996) atrav´es
de dados experimentais de rmn e do uso do software x-plor. Os resultados foram
depositados no pdb como um conjunto de 5 estruturas, sob o c´odigo 1KUL. O
rmsd m´edio entre essas estruturas ´e 1,81
˚
A, com desvio-padr˜ao de 0,12
˚
A. O menor
rmsd entre duas estruturas ´e de 1,71
˚
A; o maior, 1,99
˚
A. Esta ´e a terceira e ´ultima
das prote´ınas utilizadas no conjunto-teste do genfold.
Figura 5.25: Estrutura prim´aria e estrutura secund´aria do dom´ınio sbd da gli-
coamilase 1 (c´odigo pdb: 1KUL).
Com um comprimento de 108 res´ıduos (Figura 5.25), o dom´ınio sbd da
glicoamilase 1 ´e a maior estrutura participante dos conjuntos-teste, tanto deste
trabalho, quanto do genfold. Al´em do tamanho, essa estrutura apresenta duas
caracter´ısticas que a tornam particularmente desafiadora: a presen¸ca de uma ponte
dissulf´ıdica (entre os res´ıduos 1 e 96) e o fato de ter a estrutura secund´aria formada
quase exclusivamente por folhas β.
A Tabela 5.10 mostra os resultados obtidos pelo gapf-nmr para o dom´ınio
sbd da glicoamilase 1. Os resultados encontrados foram superiores aos descritos
pelo genfold (tamb´em dispostos na tabela), embora, como esperado, tenham sido
108
Tabela 5.10: Resultados obtidos pelo gapf-nmr para o dom´ınio sbd da glicoami-
lase 1, em rela¸c˜ao `as estruturas de referˆencia depositadas sob o c´odigo 1KUL no
pdb.
Vers˜ao do
algoritmo
Termo de
Coulomb
RMSD
M´edio
Desvio-
Padr˜ao
M´ınimo M´aximo
MemWalk Sim
6,26
˚
A 1,37
˚
A 4,21
˚
A 9,21
˚
A
MemWalk N˜ao
5,89
˚
A 1,49
˚
A 3,81
˚
A 9,38
˚
A
Grow Sim
5,95
˚
A 1,22
˚
A 4,15
˚
A 8,27
˚
A
Grow N˜ao
5,8
˚
A 1,51
˚
A 3,97
˚
A 9,5
˚
A
genfold -
8,94
˚
A
N/D N/D N/D
menos satisfat´orios que os obtidos para as prote´ınas mais simples do conjunto-teste.
A Figura 5.26 mostra a varia¸c˜ao dos termos de energia ao longo de uma execu¸c˜ao.
A Figura 5.27 compara uma das estruturas geradas com uma das estruturas de
referˆencia.
´
E poss´ıvel observar que a ponte dissulf´ıdica n˜ao foi formada na estrutura
gerada pelo gapf-nmr.
109
Figura 5.26: Varia¸c˜ao dos termos de energia ao longo da execu¸c˜ao do algoritmo,
para o dom´ınio sbd da glicoamilase 1.
Figura 5.27: (a) Estrutura final calculada por uma das execu¸c˜oes do gapf-nmr
para o dom´ınio sbd da glicoamilase 1. As liga¸c˜oes em vermelho indicam as re-
stri¸c˜oes de distˆancia mais violadas. (b) Estrutura de referˆencia (c´odigo pdb:
1KUL). Em ambas as figuras, est˜ao indicados os res´ıduos de ciste´ına.
110
Cap´ıtulo 6
Conclus˜oes e Perspectivas
Foi desenvolvido neste trabalho um Algoritmo Gen´etico de M´ultiplos M´ın-
imos para predi¸c˜ao de estruturas de prote´ınas a partir de dados oriundos de ex-
perimentos de espectropia de Ressonˆancia Magn´etica Nuclear. O algoritmo foi
implementado como uma vers˜ao modificada de trabalho anterior desenvolvido por
Cust´odio (2008), para predi¸c˜ao ab initio de estruturas. Foram desenvolvidas 5 ver-
s˜oes diferentes do algoritmo, com diferentes varia¸c˜oes na maneira como a fun¸c˜ao
de energia ´e calculada ao longo da execu¸c˜ao.
Nos testes realizados, o desempenho do algoritmo foi avaliado atrav´es da
compara¸c˜ao entre as estruturas geradas por ele e as estruturas de referˆencia corre-
spondentes, geradas por outros m´etodos j´a conhecidos para a mesma prote´ına e o
mesmo conjunto de restri¸c˜oes experimentais. Observou-se que duas das vers˜oes do
algoritmo, MemWalk e Grow, foram capazes de gerar estruturas mais pr´oximas `as
estruturas de referˆencias que as demais vers˜oes. Essas duas vers˜oes tˆem em comum
o fato de aumentarem progressivamente a regi˜ao da prote´ına utilizada no c´alculo
de energia, ao longo da execu¸c˜ao.
Tamb´em foi comparado o desempenho do algoritmo com e sem a inclus˜ao
do termo de Coulomb na fun¸c˜ao de energia, e os resultados n˜ao foram conclusivos.
Em muitos casos, a inclus˜ao do termo possibilita a obten¸c˜ao de melhores resulta-
dos entre as melhores execu¸c˜oes de cada teste, em detrimento de uma queda na
qualidade m´edia dos resultados.
111
Tamb´em foi observado que a abordagem de M´ultiplos M´ınimos (crowding) ´e
capaz de conduzir o algoritmo a resultados finais expressivamente melhores que os
obtidos com a abordagem steady-state tradicional.
Para todas as prote´ınas do conjunto-teste, conseguiu-se chegar a uma estru-
tura com o enovelamento correto ou, ao menos, aproximado. Em uma das prote´ınas
(1FYJ), a viola¸c˜ao m´edia das restri¸c˜oes de distˆancia das estruturas gerada pelo al-
goritmo foi menor que as da estrutura de referˆencia, ainda que esta apresente uma
forma¸c˜ao de estruturas secund´arias mais regular (duas α-h´elices paralelas).
Trˆes das prote´ınas usadas no conjunto-teste deste trabalho tamb´em per-
tencem ao conjunto teste do genfold, que ´e, at´e o momento, a ´unica implemen-
ta¸c˜ao alternativa conhecida de um Algoritmo Gen´etico para o problema de predi¸c˜ao
de estruturas a partir de dados de rmn. Para a primeira prote´ına (1PIT), que tem
um comprimento de 58 res´ıduos e uma estrutura estabilizada por uma combina¸c˜ao
de α-h´elices, folhas β e pontes dissulf´ıdicas, o desempenho do algoritmo, conforme
medido pelo rmsd entre a estrutura obtida e a estrutura de referˆencia, pode ser
considerado equivalente ou superior ao do genfold. Para a segunda prote´ına
(1OCP), que tem um n´umero maior (67) de res´ıduos, mas uma estrutura mais
simples – formada basicamente por α-h´elices – o algoritmo teve um desempenho
inferior ao do genfold. A terceira prote´ına (1OCP) ´e a mais longa de todo o es-
tudo (108), e tem uma estrutura estabilizada por um conjunto de folhas β, al´em de
uma ponte dissulf´ıdica. Para esta prote´ına, o algoritmo desenvolvido neste trabalho
foi capaz de encontrar uma estrutura melhor que a encontrada pelo genfold. Por
envolver intera¸c˜oes entre res´ıduos de amino´acidos distantes na seq
¨
uˆencia, a mod-
elagem da forma¸c˜ao de folhas β costuma ser mais desafiadora que a da forma¸c˜ao
de α-h´elices em algoritmos de predi¸c˜ao de estruturas de prote´ınas.
A vers˜ao atual do algoritmo desenvolvido foi, portanto, capaz de demonstrar
bons resultados, e sua abordagem conta com perspectivas promissoras de desen-
volvimento e aprimoramento futuro.
112
6.1 Perspectivas Futuras
Para melhorar o desempenho do algoritmo desenvolvido, planejam-se para
futuras vers˜oes:
O desenvolvimento de novos operadores que sejam capazes de realizar
movimentos em regi˜oes pequenas e espec´ıficas da prote´ına, sem alterar
o restante da estrutura. Um operador com essas caracter´ısticas pode ter o
potencial de ajustar mais rapidamente estruturas prot´eicas que j´a estejam
pr´oximas ao ´otimo da fun¸c˜ao de energia do ag.
O desenvolvimento de um mecanismo de otimiza¸c˜ao que permita refinar o
resultado gerado pelo algoritmo, explorando todos os graus de liberdade da
estrutura prot´eica. Tal procedimento ser´a fundamental para a supera¸c˜ao
das limita¸c˜oes inerentes ao modelo atualmente usado, em que as prote´ınas
s˜ao representadas por conjuntos de ˆangulos torcionais com comprimentos
fixos e ˆangulos diedrais predeterminados.
Utiliza¸c˜ao de uma biblioteca de fragmentos, para acelerar a modelagem da
estrutura prot´eica, de maneira an´aloga ao realizado no software Rosetta
1
.
A adi¸c˜ao um termo do solvata¸c˜ao `a fun¸c˜ao de energia do algoritmo, e a
avalia¸c˜ao de seus efeitos.
O teste do comportamento do algoritmo e da qualidade dos resultados ger-
ados, `a medida que se eliminam gradualmente as restri¸c˜oes experimentais
usadas na determina¸c˜ao da estrutura prot´eica. O objetivo ´e chegar a um
algoritmo que consiga gerar estruturas pr´oximas `as nativas, com o m´ınimo
poss´ıvel de restri¸c˜oes experimentais.
A explora¸c˜ao de adapta¸c˜oes que podem ser realizadas ao algoritmo para
se lidarem com as situa¸c˜oes em que uma restri¸c˜ao de distˆancia pode repre-
1
Se¸c˜ao 1.5.2.1
113
sentar, na realidade, uma m´edia temporal das distˆancias entre ´atomos em
diferentes conforma¸c˜oes da mesma prote´ına.
O desenvolvimento do algoritmo para predi¸c˜oes usando restri¸c˜oes de rmn
em continuidade com o algoritmo de M´ultiplos M´ınimos para predi¸c˜oes
ab initio que lhe deu origem, de modo que as inova¸c˜oes decorrentes em
qualquer uma das vers˜oes possam ser imediatamente aproveitadas na outra.
114
Referˆencias Bibliogr´aficas
A. E. Torda, R. M. Scheek, e W. F. van Gunsteren. Time-dependent distance
restraints in molecular dynamics simulations. Chemical Physics Letters, 157
(4):289–294, Maio 1989.
A. E. Torda, R. M. Scheek, e W. F. van Gunsteren. Time-averaged nuclear Over-
hauser effect distance restraints applied to tendamistat. J Mol Biol, 214(1):
223–35, 1990.
A. Leach. Molecular Modelling: Principles and Applications. Prentice Hall,
2001.
A. T. Br
¨
unger. XPLOR Manual Version 3.1. Yale University Press,
http://www.embl-heidelberg.de/nmr/xplor/htmlman/, New Haven, 1993.
N. Arora e B. Jayaram. Strength of hydrogen bonds in α helices. J Comput
Chem, 18:1245–1252, 1997.
Brunger A.T., Adams P.D., Clore G.M., DeLano W.L., Gros P., Grosse-Kunstleve
R.W., Jiang J.S., Kuszewski J., Nilges M., Pannu N.S., Read R.J., Rice L.M.,
T. Simonson, e Warren G.L. Crystallography & NMR system: A new software
suite for macromolecular structure determination. Acta Crystallogr D Biol
Crystallogr, 54(Pt 5):905–21, 1998.
D. Baker e A.
ˇ
Sali. Protein Structure Prediction and Structural Genomics, 2001.
J.E. Baker. Adaptive Selection Methods for Genetic Algorithms. Proceedings
of the 1st International Conference on Genetic Algorithms, p´aginas
101–111, 1985.
115
H. J. C. Barbosa e A. C. C. Lemonge. An adaptive penalty scheme in genetic
algorithms for constrained optimization problems. In Proc. of the Genetic
and Evolutionary Computation Conference (GECCO-2002), 2002.
H. J. C. Barbosa e A. C. C. Lemonge. An adaptive penalty scheme for steady-state
genetic algorithms. In Genetic and Evolutionary Computation – GECCO
2003, 2003a.
H. J. C. Barbosa e A. C. C. Lemonge. A new adaptive penalty scheme for genetic
algorithms. Information Sciences, 156:215–251, 2003b.
M. J. Bayley, G. Jones, P. Willett, e M. P. Williamson. GENFOLD: a genetic
algorithm for folding protein structures using NMR restraints. Protein Sci, 7
(2):491–9, 1998.
J. C. Bean e A. B. Alouane. A dual genetic algorithm for bounded integer programs.
Relat´orio t´ecnico, Departament of Industrial and Operations Engineering, The
University of Michigan, 1992.
H. M. Berman, J. Westbrook, C. Zardecki, e P. E. Bourne. The Protein Data
Bank. Protein Structure: Determination, Analysis, and Applications
for Drug Discovery, 2003.
Bernard R. Brooks, Robert E. Bruccoleri, Barry D. Olafson, David J. States, S.
Swaminathan, e Martin Karplus. CHARMM: a program for macromolecular
energy, minimization, and dynamics calculations. Journal of computational
chemistry, 4(2):187–217, 1983.
K. D. Berndt, P. G
¨
untert, L. P. Orbons, e K. W
¨
uthrich. Determination of a high-
quality nuclear magnetic resonance solution structure of the bovine pancreatic
trypsin inhibitor and comparison with three crystal structures. J Mol Biol, 227
(3):757–75, 1992.
R. Bonneau, J. Tsai, I. Ruczinski, D. Chivian, C. Rohl, C. E. M. Strauss, e
116
D. Baker. Rosetta in CASP 4: Progress in ab initio protein structure prediction.
Proteins Structure Function and Genetics, 45(s 5):119–126, 2001.
P. M. Bowers, C. E. M. Strauss, e D. Baker. De novo protein structure determina-
tion using sparse NMR data. Journal of Biomolecular NMR, 18(4):311–318,
2000.
C. Branden e J. Tooze. Introduction to Protein Structure, 2nd Edition.
Garland Publishing, 1998.
W. Braun e N. G¯o. Calculation of protein conformations by proton-proton distance
constraints: a new efficient algorithm. Journal of molecular biology, 186(3):
611–626, 1985.
A. Brindle. Genetic algorithms for function optimization. Tese de
Doutorado, University of Alberta, 1981.
C. D. Schwieters, J. J. Kuszewski, N. Tjandra, e G. M. Clore. The Xplor-NIH
NMR molecular structure determination package. J Magn Reson, 160(1):65–
73, 2003.
I. Callebaut, G. Labesse, P. Durand, A. Poupon, L. Canard, J. Chomilier, B. Hen-
rissat, e JP. Mornon. Deciphering protein sequence information through hy-
drophobic cluster analysis (HCA): current status and perspectives. Cellular
and Molecular Life Sciences (CMLS), 53(8):621–645, 1997.
D. W. Coit, A. E. Smith, e D. M. Tate. Adaptive penalty methods for genetic
optimization of constrained combinatorial problems. INFORMS Journal on
Computing, 1996.
G. Cornilescu, F. Delaglio, e A. Bax. Protein backbone angle restraints from
searching a database for chemical shift and sequence homology. Journal of
Biomolecular NMR, 13(3):289–302, 1999.
117
F. L. C. Cust´odio. Algoritmos Gen´eticos para Predi¸c˜ao Ab Initio de Estru-
tura de Prote´ınas. Tese de Doutorado, Laborat´orio Nacional de Computa¸c˜ao
Cient´ıfica, 2008.
L. Davis et al. Handbook of genetic algorithms. London International Thom-
son Computer Press, Boston, 1996.
C. S. de Magalh˜aes, H. J. C. Barbosa, L. E. Dardenne, e A. G. Vargas. Selection-
Insertion Schemes in Genetic Algorithms for the Flexible Ligand Docking Prob-
lem. GECCO 2004: Genetic and Evolutionary Computation Confer-
ence, Proceedings, p´aginas 368–379, 2004.
R. L. Dunbrack. Rotamer Libraries in the 21st Century. Current Opinion in
Structural Biology, 12(4):431–440, 2002.
G. M. Crippen. A novel approach to the calculation of conformation : Distance
geometry. J. Comp. Phys., 26:449–452, 1977.
G. M. Crippen e T. F Havel. Distance Geometry and Molecular Conforma-
tion. Research Studies Press., Taunton, UK, 1988.
G. Wagner, W. Braun, T. F. Havel, T. Schaumann, N. Go, e K. W
¨
uthrich. Protein
structures in solution by nuclear magnetic resonance and distance geometry. The
polypeptide fold of the basic pancreatic trypsin inhibitor determined using two
different algorithms, DISGEO and DISMAN. J. Mol. Biol., 196:611–639, 1987.
D. E. Goldberg. Genetic algorithms in search, optimization, and machine
learning. Addison-Wesley, Reading, Mass.; Tokyo, 1989.
R. B. Heckendorn, D. Whitley, e S. Rana. Nonlinearity, Hyperplane Ranking and
the Simple Genetic Algorithm. Foundations of Genetic Algorithms 4, 1997.
H.M.Berman, J.Westbrook, Z.Feng, G.Gilliland, T.N.Bhat, H.Weissig,
I.N.Shindyalov, e P.E.Bourne. The Protein Data Bank. Nucleic Acids
Research, 28:235–242, 2000.
118
J. H. Holland. Adaptation in Natural and Artificial Systems. Ann Arbor
MI: University of Michigan Press, 1975.
H. Homaifar, S. H. Y. Lai, e X. Qi. Constrained optimization via genetic algo-
rithms. Simulation, 1994.
J. B. Lambert e E. P. Mazzola. Nuclear Magnetic Resonance Spectroscopy:
An Introduction to Principles, Applications, and Experimental Meth-
ods. Pearson Professional, 2003.
E. J. Jeong, G. S. Hwang, K. H. Kim, M. J. Kim, S. Kim, e K. S. Kim. Struc-
tural analysis of multifunctional peptide motifs in human bifunctional tRNA
synthetase: identification of RNA-binding residues and functional implications
for tandem repeats. Biochemistry, 39(51):15775–15782, 2000.
J. A Joines e C. R. Houck. On the use of non-stationary penalty functions to solve
nonlinear constrained optimization problems with gas. In Z. Michalewicz;
J.D. Schaffer; H.-P. Schwefel; D.B. Fogel and H. Kitano, editors, Proc.
of the First IEEE Int. Conf. on Evolutionary Computation, 1994.
K. A. De Jong. Analysis of the behavior of a class of genetic adaptive
systems. Tese de Doutorado, University of Michigan, 1975.
W. L. Jorgensen e J. Tirado-Rives. The OPLS potential functions for proteins. En-
ergy minimizations for crystals of cyclic peptides and crambin. J. Am. Chem.
Soc., 110(6):1657–1666, 1988.
A. Kryshtafovych, M. Milostan, L. Szajkowski, P. Daniluk, e K. Fidelis. CASP6
Data Processing and Automatic Evaluation at the Protein Structure Prediction
Center. Proteins Struct Funct Bioinf, p´aginas 19–23, 2005.
L. M. Blumenthal. Theory and Applications of Distance Geometry. Cam-
bridge University Press., 1953.
119
R. A. Laskowski, J. A. C. Rullmann, M. W. MacArthur, R. Kaptein, e J. M.
Thornton. AQUA and PROCHECK-NMR: Programs for checking the quality
of protein structures solved by NMR. Journal of Biomolecular NMR, 8(4):
477–486, 1996.
M. Karplus. Vicinal proton coupling in nuclear magnetic resonance. Journal of
the American Chemical Society, 1963.
S. W. Mahfoud. Crowding and Preselection Revisited. Parallel Problem Solving
From Nature, 2:27–36, 1992.
S. M. Malakauskas e S. L. Mayo. Design, structure and stability of a hyperther-
mophilic protein variant. Nature Structural Biology, 5:470–475, 1998.
M. A. Mart´ı-Renom, A. C. Stuart, A. Fiser, R. S´anchez, F. Melo, e A.
ˇ
Sali. Compar-
ative Protein Structure Modeling of Genes and Genomes. Annu Rev Biophys
Biomol Struct, 29:291–325, 2000.
Matthew Clark, Richard D. Cramer III, e Nicole Van Opdenbosch. Validation of the
general purpose tripos 5.2 force field. Journal of Computational Chemistry,
10(8):982–1012, 1989.
Z. Michalewicz. Genetic algorithms, numerical optimization and constraints. In
Eshelman (Ed.) Proceedings of the 6th International Conference on
Genetic Algorithms, 1995.
Z. Michalewicz e C. Janikow. Handling constraints in genetic algorithms. In
Proceedings of the Fourth ICGA, 1991.
Z. Michalewicz e G. Nazhiyath. Genocop iii: A co-evolutionary algorithm for
numerical optimization problems with nonlinear constraints. In D. B. Fogel,
editor, Proceedings of the Second IEEE International Conference on
Evolutionary Computation, 1995.
120
Z. Michalewicz e M. Schoenauer. Evolutionary algorithms for constrained param-
eter optimization problems. Evolutionary Computation, 1996.
M. Mitchell. An Introduction to Genetic Algorithms. Bradford Books, 1996.
E. H. Morita, M. Shirakawa, F. Hayashi, M. Imagawa, e Y. Kyogoku. Structure
of the Oct-3 POU-homeodomain in solution, as determined by triple resonance
heteronuclear multidimensional NMR spectroscopy. Protein Science, 4(4):729,
1995.
P. G
¨
untert. Structure calculation of biological macromolecules from NMR data.
Quarterly Reviews of Biophysics, (31):145–237, 1 Maio 1998.
P. G
¨
untert. Automated NMR Structure Calculation With CYANA. Methods
Mol Biol, 78:353–378, 2004.
P. G
¨
untert, C. Mumenthaler, e K. W
¨
uthrich. Torsion angle dynamics for NMR
structure calculation with the new program DYANA. J Mol Biol, 273(1):
283–98, 1997.
P. G
¨
untert e K. W
¨
uthrich. Improved efficiency of protein structure calculations
from NMR data using the program DIANA with redundant dihedral angle con-
straints. J. Biomol. NMR, 1:446–456, 1991.
D. A. Pearlman, D. A. Case, J. W. Caldwell, W. S. Ross, T. E. Cheatham, S. De-
Bolt, D. Ferguson, G. Seibel, e P. Kollman. AMBER, a package of computer
programs for applying molecular mechanics, normal mode analysis, molecular
dynamics and free energy calculations to simulate the structural and energetic
properties of molecules. Computer Physics Communications, 91(1-3):1–41,
1995.
N. Pokala e T. M. Handel. Energy Functions for Protein Design: Adjustment
with Protein–Protein Complex Affinities, Models for the Unfolded State, and
Negative Design of Solubility and Specificity. Journal of Molecular Biology,
347(1):203–227, 2005.
121
D. Powell e M. M. Skolnick. Using genetic algorithms in engineering design op-
timization with non-linear constraints. In S. Forrest, editor, Proc. of the
Fifth Int. Conf. on Genetic Algorithms, 1993.
C. R. Reeves e J. E. Rowe. Genetic Algorithms: A Guide to GA Theory.
Kluwer Academic Publishers, 2003.
R. G. Le Riche, C. Knopf-Lenoir, e R. T. Haftka. A segregated genetic algorithm
for constrained structural optimization. In L.J. Eshelman, editor, Proc.of
the Sixth Int. Conf. on Genetic Algorithms, 1995.
M. A. Robien, G. M. Clore, J. G. Omichinski, R. N. Perham, E. Appella, K. Sak-
aguchi, e A. M. Gronenborn. Three-dimensional solution structure of the E3-
binding domain of the dihydrolipoamide succinyltransferase core from the 2-
oxoglutarate dehydrogenase multienzyme complex of textitEscherichia coli. Bio-
chemistry, 31(13):3463–3471, 1992.
T. P. Runarsson e X. Yao. Stochastic Ranking for Constrained Evolutionary Op-
timization. IEEE Transactions On Evolutionary Computation, 4(3):284–
294, Novembro 2000.
M. Schoenauer e Z. Michalewicz. Evolutionary computation at the edge of feasi-
bility. In Hans-Michael Voigt, Werner Ebeling, Ingo Rechenberg, e Hans-Paul
Schwefel, editors, Parallel Problem Solving from Nature – PPSN IV,
p´aginas 245–254, Berlin, 1996. Springer.
M. Schoenauer e S. Xanthakis. Constrained ga optimization. In S. Forrest,
editor, Proc. of the Fifth Int. Conf. on Genetic Algorithms, 1993.
L. D. Schuler, X. Daura, e W. F. van Gunsteren. An improved GROMOS 96 force
field for aliphatic hydrocarbons in the condensed phase. Journal of Compu-
tational Chemistry, 22(11):1205–1218, 2001.
W.R.P. Scott, P.H. Hunenberger, I.G. Tironi, A.E. Mark, S.R. Billeter, J. Fennen,
A.E. Torda, T. Huber, P. Kruger, e W.F. van Gunsteren. The gromos biomolec-
122
ular simulation program package. Journal of Physical Chemistry A, 103
(19):3596–3607, 1999. ISSN 1089-5639.
K. T. Simons, I. Ruczinski, C. Kooperberg, B. A. Fox, C. Bystroff, e D. Baker.
Improved recognition of native-like protein structures using a combination of
sequence-dependent and sequence-independent features of proteins. Proteins
Structure Function and Genetics, 34(1):82–95, 1999.
K. Sorimachi, A. J. Jacks, M. F. Le Gal-Co
¨
effet, G. Williamson, D. B. Archer,
e M. P. Williamson. Solution Structure of the Granular Starch Binding Do-
main of Glucoamylase from Aspergillus niger by Nuclear Magnetic Resonance
Spectroscopy. Journal of Molecular Biology, 259(5):970–987, 1996.
R. A. Steele e S. J. Opella. Structures of the reduced and mercury-bound forms of
MerP, the periplasmic protein from the bacterial mercury detoxification system.
Biochemistry(Washington), 36(23):6885–6895, 1997.
P. D. Surry e N. J. Radcliffe. The COMOGA Method: Constrained Optimisation
by Multiobjective Genetic Algorithms. Control and Cybernetics, 26(3), 1997.
W. F van Gunsteren e H. J.C. Berendsen. Groningen Molecular Simulation
(GROMOS) Library Manual. Biomos, Groningen, 1987.
W. F. van Gunsteren, S. R. Billeter, A. A. Eising, P. H. Hunenberger, P. Kruger,
A. E. Mark, W. R. Scott, e I. G. Tironi. Biomolecular Simulation: The
GROMOS96 Manual and User Guide. vdf, Hochschulverlag an der ETH;
BIOMOS, 1996.
A. H. C. van Kampen, C. S. Strom, e L. M. C. Buydens. Lethalization, penalty and
repair functions for constraint handling in the genetic algorithm methodology.
Chemometrics and Intelligent Laboratory Systems, 34:55–68, 1996.
A.
ˇ
Sali e TL. Blundell. Comparative protein modelling by satisfaction of spatial
restraints. J Mol Biol, 234(3):779–815, 1993.
123
Y. Zhang. Template-based modeling and free modeling by I-TASSER in CASP7.
Proteins, 2007.
124
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
