CONSTRUÇÃO DE ALGORITMO GENÉTICO PARA SELEÇÃO DE VARIÁVEIS EM QSAR

Leonardo Ribeiro da Costa (IC) e Anderson Coser Gaudio (PQ)

Departamento de Física - Centro de Ciências Exatas – Universidade Federal do Espírito Santo


palavras-chave: algoritmo genético, seleção de variáveis, qsar


Introdução. A evolução da vida na Terra é baseada em três processos básicos: mutação genética, que é o método que a natureza utiliza para produzir novas espécies; seleção natural, em que apenas as espécies mais adaptadas ao meio conseguem sobreviver e; cruzamento entre indivíduos da mesma espécie, para perpetuar a espécie e aprimorar a qualidade dos indivíduos da mesma espécie. A evolução da vida é um processo lento, porém muito eficiente. Tão eficiente que na década de 1960 inspirou Holland a aplicar os princípios da evolução à solução de problemas matemáticos diversos, criando os chamados algoritmos genéticos (AG) ou evolucionários.1

Como o nome indica, AGs são algoritmos baseados no processo de evolução da vida e que podem ser utilizados para procedimentos gerais de busca e otimização. Em QSAR, a utilização de AGs tem-se mostrado promissora na busca de combinações de variáveis que resultam em modelos lineares de melhor qualidade.2 Ou seja, dispondo-se de um conjunto de dados com n compostos e m variáveis, o problema consiste em construir os melhores modelos lineares com k variáveis capazes de acomodar os n compostos. Quando n e m são números pequenos, a busca sistemática dos modelos, que é a construção e avaliação de todas as possíveis combinações de m variáveis em grupos de k variáveis, é a melhor solução. Porém, à medida em que m torna-se grande, a busca sistemática pode não ser viável.

Como exemplo, pode-se considerar a matriz de Selwood,3 que apresenta n = 31 e m = 53. Sabendo-se que o número total de combinações de k variáveis que podem ser feitas a partir de um grupo de m variáveis é dado pela fórmula m!/(k!(m-k)!), o total de modelos distintos que podem ser construídos com até 10 variáveis é de cerca de 25 bilhões, enquanto que o número total de modelos que podem ser construídos através do método dos mínimos quadrados (k £ 29) é aproximadamente 7,16 ´ 1015. Neste caso, um computador que fosse capaz de analisar um milhão de combinações de variáveis por segundo levaria cerca de 227 anos para concluir a análise! Considerando-se que a utilização de índices de conectividade, índices de similaridade e índices eletrônicos derivados de cálculos de química quântica podem elevar o número de variáveis disponíveis para além da centena, fica clara a necessidade de métodos alternativos de seleção de variáveis mais eficientes.

Objetivo. O objetivo do presente trabalho é desenvolver um AG para executar seleção de variáveis em QSAR para ser utilizado em grandes conjuntos de dados. Deseja-se que este algoritmo seja mais eficiente que a busca sistemática e também mais eficiente que os algoritmos evolucionários que não utilizam o procedimento denominado crossover.4-6

Metodologia. A construção do algoritmo proposto foi feita a partir da análise de AGs já disponíveis na literatura, sendo que alguns deles já foram adaptados para executar seleção de variáveis em modelos lineares.2 Apesar de todos os AGs apresentarem a mesma estrutura básica, o presente algoritmo apresenta características particulares relativas à forma com que as etapas evolutivas são implementadas. O algoritmo inclui as três etapas evolucionárias mencionadas na introdução deste trabalho, na seguinte ordem: seleção, crossover e mutação. O algoritmo é estruturado e de arquitetura top-down. Na verdade, o presente algoritmo está sendo codificado em linguagem Delphi como uma subrotina a ser incorporada ao programa QSAR.7

Resultados. A estrutura geral do algoritmo proposto pode se vista no fluxograma ao lado.

Os resultados dos testes preliminares realizados com a matriz de Selwood indicam que o presente algoritmo apresenta grande potencialidade como método de seleção de variáveis. O tempo de busca pelo melhor modelo varia de acordo com os valores dos parâmetros do AG escolhidos pelo operador, como o número de modelos em cada geração (NPop) e o número total de gerações a serem construídas (NGerTot). Porém, os primeiros testes mostram que à medida em que m aumenta a razão entre o tempo gasto por AG e o tempo de busca sistemática diminui quase que geometricamente. Embora os melhores modelos com um, dois e três variáveis tenham sido localizados em todas as tentativas realizadas, o algoritmo ainda apresenta alguma dificuldade para localizar os melhores modelos com quatro e cinco variáveis. Isso indica que algum ajuste fino nos parâmetros que controlam a evolução dos modelos ainda precisa ser feito. No presente momento, dedicam-se os maiores esforços nesse sentido.

Conclusões. AGs apresentam enormes potencialidades de uso na seleção de variáveis em modelos de QSAR, especialmente na busca por modelos com número elevado de variáveis em que o tempo de busca sistemática pode ser proibitivo.

Bibliografia. 1. Sutton, P.; S. Boyden; Am. J. Phys. 1994, 62, 549. 2. Maddalena, D. J.; G. M. Snowdon; Exp. Opin. Ther. Patents 1997, 7, 247. 3. Selwood, D. L., et al.; J. Med. Chem. 1990, 33, 136. 4. Kubinyi, H.; Quant. Struct.-Act. Relat. 1994, 13, 285. 5. Kubinyi, H.; Quant. Struct.-Act. Relat. 1994, 13, 393. 6. Waller, C. L.; M. P. Bradley; J. Chem. Inf. Comp. Sci. 1999, 39, 345. 7. Oliveira, D. B.; A. C. Gaudio; QSAR, Beta 1, Vitória, 2000.

(PRPPG-UFES e CNPq)