Multi objective and diversity guided success history based adaptive differential Evolution approaches for the Tertiary Protein Structure Prediction Problem

Abstract

Tertiary protein structure prediction is one of the most challenging problems in Struc tural Bioinformatics, and it is an NP-Hard problem in computational complexity theory. The complexity is related to the significant number of possible conformations a single protein can assume. As the experimental determination of protein structures is costly and time-consuming, computational methods became an interesting way to predict pro teins’ shape based on their amino acid sequence. As the problem is considered NP-Hard, no known algorithm can find the global optimum solution. In this regard, Metaheuris tics became an option for the protein structure prediction problem in recent years. Al though the popularity of such methods, each one of them has different characteristics and knowledge sources. As metaheuristics are heavily dependent on parameter tuning, wrong parameters might cause poor performance. Moreover, the force fields used for evaluating the protein’s energy might have conflicting terms in their composition, lead ing to a possible multi-objective version of the problem. With this in mind, this thesis presents a multi-objective formulation of the Success-History based Adaptive Differen tial Evolution for the protein structure prediction problem, maintaining the characteristics of the remarkable CEC’2014 winner (SHADE). A second approach is also proposed, us ing the SHADE single-objective algorithm with diversity-guided adaptation mechanisms for diversity maintenance. In the diversity-guided approach, structural knowledge from two sources are used, the Angle Probability List during the population’s initialization and Rosetta fragments during the diversity generation phase. With the results obtained in this thesis from different Differential Evolution applications in the Protein Structure Prediction Problem, we verified that our proposal improves the metaheuristics’ capabili ties of predicting relevant results for one of the most challenging problems in structural bioinformatics. Besides, the novel adaptation mechanism based on populational diversity improved significantly compared to DEs that do not use the diversity-guided adaptation mechanism. Thus, our work contains relevant contributions to the Differential Evolution algorithm and its applications. Although our approaches are applied to the PSP problem, they can be generalized for other NP-hard problems with similar characteristics, such as the Molecular Docking problem.

A predição de estrutura terciária das proteínas é um dos problemas mais desafiadores na Bioinformática Estrutural, e é considerado um problema NP-Hard na teoria da com plexidade computacional. A complexidade do problema está relacionada com o número significativo de conformações possíveis que uma única proteína pode assumir. Como a determinação experimental das estruturas proteicas é cara e demorada, os métodos com putacionais tornaram-se uma forma interessante de predizer a forma das proteínas com base em sua sequência de aminoácidos. Como o problema é considerado NP-Hard, ne nhum algoritmo conhecido pode encontrar a solução ótima global. A este respeito, as meta heurísticas tornaram-se uma opção para o problema de predição da estrutura da proteína nos últimos anos. Apesar da popularidade de tais métodos, cada um deles tem características e fontes de conhecimento diferentes. Como as meta heurísticas dependem muito do ajuste dos parâmetros, um ajuste errôneo dos parâmetros pode impactar direta mente no desempenho dos métodos. Além disso, os campos de força usados para avaliar a energia da proteína podem ter termos conflitantes em sua composição, levando a uma possível versão multiobjetivo do problema Com isto em mente, esta tese apresenta uma formulação multi-objetiva da Evolução Diferencial Adaptativa baseada na História de Su cesso para o problema de predição da estrutura da proteína, mantendo as características do notável vencedor do CEC’2014 (SHADE). Uma segunda abordagem também é proposta, utilizando o algoritmo SHADE mono-objetivo com mecanismos de adaptação guiados por diversidade para a manutenção da diversidade. Na abordagem orientada pela diver sidade, são utilizados conhecimentos estruturais de duas fontes, a Lista de Probabilidade Angular durante a inicialização da população e fragmentos de Rosetta durante a fase de geração da diversidade. Com os resultados obtidos nesta tese de diferentes aplicações da Evolução Diferencial no Problema de Predição da Estrutura da Proteína, verificamos que nossa proposta melhora a capacidade da meta heurística de alcançar resultados relevantes para um dos problemas mais desafiadores da bioinformática estrutural. Além disso, o novo mecanismo de adaptação baseado na diversidade populacional melhorou significati vamente em comparação com os DEs que não utilizam o mecanismo de adaptação guiado pela diversidade. Assim, nosso trabalho contém contribuições relevantes para o algoritmo de Evolução Diferencial e suas aplicações. Embora nossas abordagens sejam aplicadas ao problema de PSP, elas podem ser generalizadas para outros problemas NP-Hard com características similares, como o problema de Atracamento Molecular.