From sequences to structures : mathematical optimization applied to protein structure prediction

Abstract

Resumo: As proteínas são componentes fundamentais da vida, atuando como blocos de cons trução em diversos processos biológicos. Consequentemente, compreender a sua formação é um campo de amplo alcance e relevância. O problema de previsão da estrutura de proteínas (PSP) se baseia no uso da sequência linear dos aminoácidos e em funções matemáticas baseadas em física e biologia para determinar sua estrutura nativa, possuindo esta o mínimo de energia livre para garantir a estabilidade da confor mação. À vista disso, a principal contribuição dessa tese de doutorado é a execução de uma abordagem pioneira para PSP baseada em otimização matemática que utiliza o modelo de representação de proteínas AB off-lattice, o qual faz uso das características hidrofílicas dos aminoácidos para classificá-los e calcular suas posições. A formulação quebra o cenário energético de dobramento de proteínas, transformando a questão do PSP convencionalmente não linear em um problema de otimização bilinear (BL), uma vez que a natureza intrinsecamente não convexa do PSP continua sendo uma limitação que desafia a eficácia dos métodos de otimização global. Essa formulação foi obtida através da introdução de variáveis e restrições auxiliares que descrevem a relação complexa entre o espaço conformacional da proteína e seu cenário energético, introduzindo uma decomposição matematicamente estruturada que ainda não havia sido explorada neste contexto. Essa reformulação oferece um novo caminho para codificar padrões de interação, dependências geométricas e contribuições energéticas dentro de uma preposição algébrica tratável, permitindo a aplicação de ferramentas avançadas de programação matemática a um problema biofísico classicamente intra tável. Múltiplas abordagens usando heurísticas aparecem na literatura com sucesso variado em relação ao PSP; assim, o problema de otimização BL é comparado às metaheurísticas mais utilizadas para validar o método sugerido. O modelo BL proposto demonstrou notável precisão na identificação das conformações de energia mínima global em um conjunto de dados de referência fornecido pelo Protein Data Bank (PDB). Comparada aos métodos heurísticos tradicionais, a abordagem BL viabilizou soluções exatas, reduzindo a probabilidade de aprisionamento em mínimos locais, com melhor acurácia, especialmente quando testada em proteínas grandes e com custo compu tacional até cinco vezes menor do que o das metaheurísticas tradicionais. Essa tese destaca o potencial de reformular o problema tradicionalmente não linear de PSP; a transformação bilinear oferece um caminho para metodologias que podem determinar a solução global, desafiando os paradigmas atuais de PSP

Abstract: Proteins are fundamental components of life and act as building blocks in various bio logical processes. Consequently, understanding their formation is a field of broad scope and relevance. The protein structure prediction (PSP) problem is based on the use of the linear amino acid sequence that constitutes a protein and on mathematical functions based on physics and biology to determine its native structure, which holds the minimum free energy to guarantee the stability of the conformation. This process is essential to clarify the functions and actions of a protein. In light of this, the main contribution of this Doctoral thesis is the implementation of a pioneering approach to PSP based on mathematical optimization that uses the AB off-lattice protein representation model, which exploits the hydrophilic characteristics of amino acids to classify them and calcu late their positions. The formulation breaks the intricate energetic scenario of protein folding, reformulating the traditionally nonlinear PSP problem as a bilinear optimization problem, although the inherently highly non-convex nature of PSP continues to pose challenges for global optimization. The BL design was obtained through the estab lishment of auxiliary variables and constraints that describe the complex relationship between the protein’s conformational space and its energy landscape, introducing a mathematically structured decomposition that had not yet been explored in this context. This reformulation provides a novel pathway to encode interaction patterns, geomet ric dependencies, and energetic contributions within a tractable algebraic preposition, enabling the application of advanced mathematical programming tools to a classically intractable biophysical problem. Multiple approaches using heuristics appear in the literature with varying success in relation to the PSP; thus, the bilinear (BL) optimization problem is compared to the most widely used metaheuristics with the best results in the studied application to validate the suggested method. The proposed BL model demonstrated remarkable accuracy in identifying global minimum energy conformations in a reference dataset provided by the Protein Data Bank (PDB). Compared to traditional heuristic methods, the BL approach provided exact solutions, reducing the likelihood of local minima blockage, with satisfactory performance metrics, i.e., better accuracy, especially when tested on larger proteins (composed of more than 100 amino acids) and with a computational runtime cost up to five times lower than traditional metaheuris tics. This thesis highlights the potential to reformulate the traditionally non-linear PSP problem, as bilinear transformation offers a path to methodologies that can determine the global solution, challenging current PSP paradigms