Evaluation and development of algorithms and computational tools for metabolic pathway optimization

Abstract

Metabolic engineering exploits microorganisms to build cell factories, allowing to produce valuable compounds from their enzymatic machinery. It involves the selection of an organism, along with a set of genetic modifications to optimize the process. Information regarding biological mechanisms are scattered among the literature. Metabolic databases provide a centralized platform compiling existing biological data to build a catalog of all known enzymatic transformations across all domains of life. The development of genome-scale metabolic models allows to expose all possible biochemical transformations that an organism can offer. Computer algorithms use these models to exploit the capabilities and limitations of the organisms. Constraint-based modeling approaches allow to predict phenotype given modifications in the network. In recent years, there has been a significant increase in the number of available models, and for certain organisms several models were built. The accuracy of these methods is in many cases dependent on the quality of these models, that is limited to the available information in the literature (or databases). This thesis improves the existing methods by developing better data management strategies for the metabolic modeling community. Metabolic databases are usually the input data for many modeling tools, and the quality of solutions depends on the quality of the databases. Currently, several metabolic databases exist, most of them sharing a common set of information, and there is a need for a centralized system to take the most advantage of their content. However, each database adopts its own naming system to catalog its instances, being in many cases, diffcult to compare with others. An integration pipeline is here designed to fuse metabolic databases into a common namespace allowing better analysis of the entire metabolic catalog across several databases, and exploring different methods to reconcile the metabolites and reactions included in these databases. In a second part of this work, the Systems Biology Markup Language which is the most common medium to store and represent genome-scale metabolic models is analyzed. Like databases, models also adopt unique nomenclatures for reactions and compounds. Here, methods to annotate metabolites and reactions in models are developed allowing to connect models with database instances, thus allowing to adopt a single naming system for their entities. The purpose of the methods is to standardize the entire model, therefore, other entities such as, genes, compartments, simulation media, are also considered to unify these models. The standardization methods were implemented in the KBase platform, which allows to improve the compatibility of this system with models built from external tools. In the last part of this thesis, the pathway enumeration problem is revisited. Synthetic biology explores cellular modi cations to produce valuable products by inserting enzymatic capabilities of other organisms. The selection of suitable set of genes is highly combinatorial, since in many cases there are several alternatives to reach the target product. A common limitation of most of the existing methods is the inability to fully explore this combinatorial space. In this work, the (hyper)graph methods are analyzed and improved to fully enumerate biological pathways. As result, two existing algorithms were improved regarding to scalability, allowing to fully enumerate larger solution sets.

Um dos objetivos da Engenharia Metabólica é a síntese de compostos de valor acrescentado através de microrganismos. Uma das etapas deste processo envolve a seleção de organismos em combinação com alterações genéticas que permitem otimizar este processo. As bases de dados metabólicas centralizam os dados biológicos disponibilizando um catalogo de todo o conhecimento existente relacionado ao contexto enzimático. A reconstrução de modelos metabólicos à escala genómica permite estudar os processos metabólicos dos diversos organismos. Com o recurso a métodos computacionais, estes modelos permitem expor as capacidades e limitações dos diversos organismos. Abordagens como a modelação baseada em restrições permitem prever fenótipos dadas alterações nas vias metabólicas. Nas últimas décadas, houve um aumento significativo do número de modelos publicados, e para alguns organismos existem várias versões disponíveis. A capacidade de previsão destes modelos está dependente da informação disponível nas bases de dados e na literatura. Esta tese visa melhorar os métodos anteriores abordando questões relacionadas com a integração de dados. As bases de dados metabólicas são geralmente a principal fonte de informação para os métodos existentes, implicando diretamente na capacidade de resolução destes problemas. Atualmente, existem várias bases de dados biológicas, havendo uma necessidade de desenvolver sistemas centralizados. No entanto, é comum estes adotaram identificares próprios, não sendo possível executar uma comparação direta. Neste trabalho, foram desenvolvidas estratégias para reconciliar bases de dados no contexto metabólico, permitindo integrar compostos e reações. Na segunda parte deste trabalho, este processo de integração foi expandido para incluir modelos metabólicos à escala genómica. De forma semelhante às bases de dados, os modelos adotam também identificadores próprios para representar compostos e reações. Para unificar modelos, foram desenvolvidos métodos de anotação que permitem relacionar as instâncias dos modelos com as bases de dados. Foram, também, implementadas estratégias para identificar genes, compartimentos e as restrições da simulação. Neste trabalho, os métodos forma implementados na plataforma KBase, permitindo melhorar a compatibilidade do sistema com os modelos externos. Por fim, vários métodos de enumeração de vias metabólicas foram abordados. A biologia sintética visa manipular o metabolismo celular para produção de compostos através da inserção de genes. A seleção destes genes é um problema combinatório, que, dado um composto alvo, identifica vários conjuntos de genes capazes de concretizar a via sintética. Neste trabalho, pretende-se melhorar a capacidade de enumerar todas as vias possíveis, dado um conjunto limitado de reações e o tamanho das vias. Como resultado, foram melhorados dois métodos existentes baseados em hipergrafos, melhorando a escalabilidade destes métodos permitindo enumerar problemas ou vias de maior dimensão.