Vários problemas do mundo real podem ser analisados como problemas de otimização. Na bioinformática, em especial, como exemplos podem ser citados o alinhamento múltiplo de sequências, a filogenia, a predição de estruturas de proteínas e RNA, entre outros. As Meta-heurísticas Populacionais (MhP) são técnicas baseadas em interações de conjuntos de soluções candidatas, como elementos de uma população, utilizadas na otimização de funções. Seu uso é especialmente interessante na otimização de problemas onde há conhecimento parcial ou nenhum do espaço de busca. O objetivo deste trabalho é investigar o uso de auto-organização da população de um sistema imunológico artificial (AIS) a fim de aplicá-lo no problema de docking, que pode ser visto como um problema de otimização multimodal complexo. O AIS é um tipo de MhP inspirado na microevolução do sistema imunológico adaptativo de organismos complexos. Neste, as soluções candidatas representam células do sistema imunológico que busca se adaptar para a eliminação de um patógeno. O desenvolvimento do algoritmo foi baseado no opt-aiNet, que utiliza dos princípios das teorias de seleção clonal e maturação de afinidade para realizar a otimização de funções. Adicionalmente, o opt-aiNet, inspirado na teoria de redes imunológicas, realiza uma etapa de supressão, que busca eliminar soluções semelhantes, aumentando assim a diversidade populacional. Esta etapa é computacionalmente custosa, dado que é feito o cálculo da distância entre todos os possíveis pares de células (soluções) afim de eliminar aquelas próximas de acordo com um dado critério. A proposta deste trabalho é o desenvolvimento de um algoritmo de supressão auto-organizável, inspirado no fenômeno da criticalidade auto-organizada, buscando diminuir a influência da seleção de parâmetros e a complexidade da etapa de supressão. O algoritmo proposto foi testado em um conjunto de funções contínuas conhecidas e comumente utilizadas pela comunidade de computação evolutiva. Os resultados obtidos foram comparados com aqueles de uma implementação do opt-aiNet. Em adição, foi proposta a utilização de operadores de mutação com distribuição q-gaussiana nos AISs desenvolvidos. O algoritmo foi também aplicado no problema de docking rígido baseado em complementaridade de superfícies e minimização de colisões, especificamente no docking de proteínas. Os resultados foram comparados com aqueles de um algoritmo genético, resultando em um melhor desempenho obtido pelo algoritmo proposto. / Many real world problems can be described as optimization problems. In bioinformatics in special, there is multiple sequence alignment, filogeny and RNA and Protein structure prediction, among others. Population based metaheuristics are techniques based in the interaction of a set of candidate solutions as elements of a population. Its use is specially interesting in optimization problems where there is little or no knowledge of the search space. The objective of this work is to study the use of self-organization of population in an artificial imune system for use in the docking problem, considered a complex multimodal optimization problem. The artificial imunme system is a type of population based methaheuristics inspired in the microevolution of the adaptive immune system of complex organisms. Candidate solutions represent cells of the immune system adapting its antibodies to eliminate a pathogen. The development of the algorithm was based in the opt-aiNet, based in the principles of clonal selection and affinity maturation for function optimization. Additionally, the opt-aiNet, inspired in theories of immune network, makes a suppression stage to eliminate similiar solutions and control diversity. This stage is computationally expensive as it calculates the distance between every possible pair of cells (solutions) eliminating those closer than a threshold. This work proposes a self-organized suppression algorithm inspired in the self-organized criticality, looking to minimize the influence of parameter selection and complexity of the suppression stage in opt-aiNet. The proposed algorithm was tested in a set of well-known functions in the evolutionary computation community. The results were compared to those of an implementation of the opt-aiNet. In addition, we proposed a mutation operator with q-Gaussian distribution for the artificial immune systems. The algorithm was then applied in the rigid protein docking problem based in surface complementarity and colision avoidance. The results were compared with a genetic algorithm and achieved a better performance.
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-30082012-161501 |
| Date | 17 July 2012 |
| Creators | Helder Ken Shimo |
| Contributors | Renato Tinós, Paulo Sérgio Lopes de Oliveira, Fernando José von Zuben |
| Publisher | Universidade de São Paulo, Bioinformática, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0025 seconds