UNIVERSIDADEFEDERALDORIOGRANDEDOSUL INSTITUTODEINFORMÁTICA PROGRAMADEPÓS-GRADUAÇÃOEMCOMPUTAÇÃO EDUARDOSPIELERDEOLIVEIRA Um Algoritmo Genético de Chaves Aleatórias Viciadas para o problema de Atracamento Molecular Dissertação apresentada como requisito parcial para a obtenção do grau de Mestre em Ciência da Computação Orientador:Prof.Dr.MárcioDorn PortoAlegre 2016 CIP—CATALOGAÇÃONAPUBLICAÇÃO SpielerdeOliveira,Eduardo Um Algoritmo Genético de Chaves Aleatórias Viciadas para o problema de Atracamento Molecular / Eduardo Spieler de Oli- veira.–PortoAlegre: PPGCdaUFRGS,2016. 98f.: il. Dissertação(mestrado)–UniversidadeFederaldoRioGrande do Sul. Programa de Pós-Graduação em Computação, Porto Ale- gre,BR–RS,2016. Orientador: MárcioDorn. 1. Atracamento Molecular. 2. Otimização. 3. Algoritmo Ge- nético. 4.Docking. I.Dorn,Márcio. II.Título. UNIVERSIDADEFEDERALDORIOGRANDEDOSUL Reitor: Prof.RuiVicenteOppermann Vice-Reitor: Prof.JaneFragaTutikian Pró-ReitordePós-Graduação: Prof.VladimirPinheirodoNascimento DiretordoInstitutodeInformática: Profa.CarlaMariaDalSassoFreitas CoordenadordoPPGC:Prof.LuigiCarro Bibliotecária-chefedoInstitutodeInformática: BeatrizReginaBastosHaro AGRADECIMENTOS Agradeçoaosmeuspaiseaomeuorientador. UmAlgoritmoGenéticodeChavesAleatóriasViciadasparaoproblemade AtracamentoMolecular RESUMO O Atracamento Molecular é uma importante ferramenta utilizada no descobrimento de novos fármacos. O atracamento com ligante flexível é um processo computacionalmente custoso devido ao número alto de graus de liberdade do ligante e da rugosidade do es- paço de busca conformacional representando a afinidade entre o receptor e uma molé- cula ligante. O problema é definido como a busca pela solução de menor energia de ligação proteína-ligante. Considerando uma função suficientemente acurada, a solução ótimacoincidecomamelhororientaçãoeafinidadeentreasmoléculas. Assim,ométodo de busca e a função de energia são partes fundamentais para a resolução do problema. Muitos desafios são enfrentados para a resolução do problema, o tratamento da flexibili- dade, algoritmo de amostragem, a exploração do espaço de busca, o cálculo da energia livre entre os átomos, são alguns dos focos estudados. Esta dissertação apresenta uma técnica baseada em um Algoritmo Genético de Chaves Aleatórias Viciadas, incluindo a discretização do espaço de busca e métodos de agrupamento para a multimodalidade do problema de atracamento molecular. A metodologia desenvolvida explora o espaço de busca gerando soluções diversificadas. O método proposto foi testado em uma seleção de complexos proteína-ligante e foi comparado com softwares existentes: AutodockVina e Dockthor. Os resultados foram estatisticamente analisados em termos estruturais. O métodosemostroueficientequandocomparadocomoutrasferramentaseumaalternativa paraoproblemadeAtracamentoMolecular. Palavras-chave: AtracamentoMolecular. Otimização. AlgoritmoGenético. Docking. ABiasedRandomKeyGeneticAlgorithmfortheMolecularDockingproblem ABSTRACT Molecular Docking is a valuable tool for drug discovery. Receptor and flexible Ligand docking is a very computationally expensive process due to a large number of degrees of freedom of the ligand and the roughness of the molecular binding search space. A Molecular Docking simulation starts with a receptor and ligand unbounded structures and the algorithm tests hundreds of thousands of ligands conformations and orientations to find the best receptor-ligand binding affinity by assigning and optimizing an energy function. Despite the advances in the conception of methods and computational strate- giesforsearchthebestprotein-ligandbindingaffinity,thedevelopmentofnewstrategies, the adaptation, and investigation of new approaches and the combination of existing and state-of-the-artcomputationalmethodsandtechniquestotheMolecularDockingproblem areclearlyneeded. WedevelopedaBiasedRandom-KeyGeneticAlgorithmasasampling strategy to search the protein-ligand conformational space. The proposed method has been tested on a selection of protein-ligand complexes and compared with existing tools AutodockVinaandDockthor. Comparedwithothertraditionaldockingsoftware,thepro- posed method has the best average Root-Mean-Square Deviation. Structural results were statistically analyzed. The proposed method proved to be efficient and a good alternative tothemoleculardockingproblem. Keywords: MolecularDocking. Optimization. GeneticAlgorithm. LISTADEFIGURAS Figura1.1 Desenhoracionaldefármacos.......................................................................11 Figura2.1 MoléculaHIV-protease..................................................................................19 Figura2.2 MoléculaHIV-proteasecomoligante...........................................................19 Figura2.3 TriagemVirtual..............................................................................................28 Figura2.4 Ângulosdiedrais............................................................................................29 Figura4.1 Codificaçãodasolução..................................................................................46 Figura4.2 Espaçodebusca.............................................................................................49 Figura4.3 Céluladagrade..............................................................................................50 Figura4.4 Espaçodebuscadiscretizado.........................................................................53 Figura4.5 DinâmicadeevoluçãoemumBRKGA.........................................................56 Figura4.6 Cruzamento....................................................................................................57 Figura4.7 Discretizaçãodoespaço,representaçãoemelhoressoluções.......................59 Figura4.8 DiagramaBRKGA........................................................................................61 Figura5.1 Diagramadecaixa1......................................................................................77 Figura5.2 Diagramadecaixa2......................................................................................80 Figura5.3 Diagramadecaixa: 2UPJ..............................................................................82 Figura5.4 Análiseestrutural: 1AJV,1AJX,1BV9e1D4K...........................................83 Figura5.5 Análiseestrutural: 1AJV,1AJX,1BV9e1D4K...........................................84 Figura5.6 Infográficoconjunto1...................................................................................86 Figura5.7 Infográficoconjunto2...................................................................................86 Figura5.8 Infográficoconjunto3...................................................................................87 Figura5.9 Infográficoconjunto4...................................................................................87 LISTADETABELAS Tabela4.1 ValoresrecomedadosparaBRKGA..............................................................57 Tabela5.1 Seleçãodecomplexos1.................................................................................65 Tabela5.2 Seleçãodecomplexos2.................................................................................65 Tabela5.3 Seleçãodecomplexos3.................................................................................66 Tabela5.4 Seleçãodecomplexos4.................................................................................66 Tabela5.5 Resultadosparametrização............................................................................68 Tabela5.6 ResultadosdeAtracamentoRígido...............................................................69 Tabela5.7 ResultadosdeAtracamentoflexível-conjunto2..........................................71 Tabela5.8 ResultadosdeAtracamentoflexível-conjunto3..........................................73 Tabela5.9 ResultadosdeAtracamentoflexível-conjunto4..........................................74 Tabela5.10 Resultadoscomparação...............................................................................75 Tabela5.11 TestedeTukey: 1AJV.................................................................................78 Tabela5.12 TestedeTukey: 1AJX.................................................................................78 Tabela5.13 TestedeTukey: 1BV9.................................................................................78 Tabela5.14 TestedeTukey: 1D4K.................................................................................78 Tabela5.15 TestedeTukey: 1G2K.................................................................................81 Tabela5.16 TestedeTukey: 1HIV..................................................................................81 Tabela5.17 TestedeTukey: 1HPX.................................................................................81 Tabela5.18 TestedeTukey: 1HTF.................................................................................81 Tabela5.19 TestedeTukey: 2UPJ..................................................................................82 LISTADEABREVIATURASESIGLAS DRFBE DesenhoRacionaldeFármacosBaseadoemEstrutura BRKGA BiasedRandom-KeyGeneticAlgorithms AM AtracamentoMolecular VS VirtualScreening CAPRI CriticalAssessmentofPredictionofInteractions EBI EuropeanBioinformaticsInstitute PDB ProteinDataBank AG AlgoritmoGenético AGL AlgoritmoGenéticoLamarckiano SSGA SteadyStateGeneticAlgorithm EG EvoluçãoDiferencial AM AlgoritmosMeméticos SA SimulatedAnnealing OEP OtimizaçãoporEnxamedePartículas RMSD Root-mean-squaredeviation GPU GraphicsProcessingUnit ILS IteratedLocalSearchalgorithm DMRTS DynamicModifiedRestrictedTournamentSelection RMN RessonânciaMagnéticaNuclear SUMÁRIO 1INTRODUÇÃO...........................................................................................................10 1.1 Motivação.................................................................................................................14 1.2 Objetivosgerais.......................................................................................................15 1.3 Estrutura..................................................................................................................16 2FUNDAMENTAÇÃOBIOLÓGICA.........................................................................18 2.1 EstruturasMoleculares: LiganteseReceptores..................................................18 2.2 InteraçõesLigante-Receptor..................................................................................20 2.3 Cálculodaenergialivre..........................................................................................22 2.3.1 Funçõesbaseadasemcampodeforça...................................................................22 2.3.2 Funçõesempíricasousemi-empíricas...................................................................23 2.3.3 Funçõesbaseadasemconhecimento......................................................................24 2.4 Bancosdedados......................................................................................................25 2.5 Funçãobiológicarelacionadaaestrutura.............................................................26 2.6 TriagemVirtual.......................................................................................................27 2.7 AtracamentoRígidoeFlexível...............................................................................29 2.8 Conclusão.................................................................................................................30 3TÉCNICASEALGORITMOSDEATRACAMENTOMOLECULAR...............31 3.1 Representaçãodeestruturasmoleculares.............................................................31 3.2 Categoriasdemétodosdebusca............................................................................34 3.3 CAPRI......................................................................................................................36 3.4 MetaheurísticasutilizadasemAtracamentoMolecular......................................37 3.4.1 AutodockVina.......................................................................................................39 3.4.2 Dockthor................................................................................................................40 3.5 DesafiosemAtracamentoMolecular....................................................................41 3.6 Conclusão.................................................................................................................43 4MÉTODOPROPOSTO..............................................................................................44 4.1 Preparaçãoerepresentaçãodasestruturasmoleculares....................................44 4.2 Funçãodeenergiautilizada...................................................................................47 4.3 Propostadedescriçãodoespaçodebusca............................................................49 4.4 AlgoritmoGenéticodeChavesAleatóriasViciadas............................................54 4.5 Agrupamentoecompetiçõesglobalelocal...........................................................57 4.6 Algoritmo BRKGA com agrupamento de soluções e competições global e local........................................................................................................................59 4.7 Conclusão.................................................................................................................62 5EXPERIMENTOSERESULTADOS.......................................................................63 5.1 Métodosdeavaliação..............................................................................................63 5.2 Dadosparaostestes................................................................................................64 5.3 Resultadosdeparametrização...............................................................................67 5.4 ResultadosdeAtracamentoRígido.......................................................................69 5.5 ResultadosdeAtracamentoFlexível.....................................................................70 5.6 Comparaçãocomoutrasferramentas...................................................................74 5.7 Avaliaçãogeraldosresultados...............................................................................85 6CONCLUSÃOETRABALHOSFUTUROS...........................................................88 REFERÊNCIAS.............................................................................................................91 10 1INTRODUÇÃO Luscombe et al. (2001) descreve os principais objetivos da Bioinformática como sendo: a organização dos dados de uma maneira que permita que pesquisadores tenham um fácil acesso a estes dados e possam submeter novas entradas produzidas; o desen- volvimento de ferramentas e recursos que auxiliem os pesquisadores na análise destes dados;eainda,ousodestasferramentascomputacionaisparaanalisardadoseinterpretar osresultados. ABioinformáticaEstruturalpodeserapresentadacomoaáreadeestudoda estrutura de moléculas, tais como: DNA, RNA, proteínas, entre outros compostos, e tem foco na representação, armazenamento, recuperação, análises e exibição de informações estruturaisdemacromoléculasbiológicas(ALTMAN;DUGAN,2003). UmdosprincipaisdesafiosdaBioinformáticaEstruturaléconhecidocomoopro- blema de Atracamento Molecular. O problema consiste em encontrar a orientação entre uma molécula ligante e uma molécula receptora que apresente a menor energia de in- teração (CAMACHO et al., 2014). Ferramentas de Atracamento Molecular objetivam a busca de um modelo que descreva a interação entre duas estruturas moleculares. O grau de dificuldade do problema está associado as estruturas moleculares, considerando o grande número de ângulos internos e mínimos locais no espaço (KUNTZ, 1992). O desenvolvimento de métodos e estratégias computacionais para o atracamento guiam o uso dessa técnica como uma ferramenta para o descobrimento de novos compostos quí- micos (fármacos) (BROOIJMANS; KUNTZ, 2003a). As principais estruturas utilizadas como receptor são proteínas. Proteínas ou polipeptídios são polímeros formados por 20 diferentestiposderesíduosdeaminoácidosquesãoligadosatravésdeumaligaçãopeptí- dica(LESK,2005). Cadaproteínaédefinidaporsuasequênciaúnicaderesíduosdeami- noácidos que em condições fisiológicas se enovelam em uma forma específica conhecida como estado nativo (ANFINSEN, 1973). São estruturas fundamentais para o organismo, suas funções variam desde construção de novos tecidos do corpo humano, transporte de substâncias,atuaçãonosistemadedefesadoorganismo,catalizaçãodereaçõesquímicas, regulaçãodehormônios,entreoutros. Ferramentas de Atracamento proteína-ligante são atualmente importantes meto- dologias para o descobrimento de novos fármacos (SOUSA et al., 2013). Conhecer a forma 3D da proteína e do ligante implica na inferência de sua função. Todos esses fa- tores, aliados a necessidade de uma metodologia mais sistemática que objetive o estudo dos mecanismos envolvidos no processo de reconhecimento molecular, impulsionaram o