<p>Given a random sample from a multivariate probability distribution <em>p</em>, the maximum minimum parents and children algorithm locates the skeleton of the directed acyclic graph of a Bayesian network for <em>p</em> provided that there exists a faithful Bayesian network and that the dependence structure derived from data is the same as that of the underlying probability distribution.</p><p>The aim of this thesis is to examine the consequences when one of these conditions is not fulfilled. There are some circumstances where the algorithm works well even if there does not exist a faithful Bayesian network, but there are others where the algorithm fails.</p><p>The MMPC tests for conditional independence between the variables and assumes that if conditional independence is not rejected, then the conditional independence statement holds. There are situations where this procedure leads to conditional independence being accepted that contradict conditional dependence relations in the data. This leads to edges being removed from the skeleton that are necessary for representing the dependence structure of the data.</p>

Given a random sample from a multivariate probability distribution p, the maximum minimum parents and children algorithm locates the skeleton of the directed acyclic graph of a Bayesian network for p provided that there exists a faithful Bayesian network and that the dependence structure derived from data is the same as that of the underlying probability distribution. The aim of this thesis is to examine the consequences when one of these conditions is not fulfilled. There are some circumstances where the algorithm works well even if there does not exist a faithful Bayesian network, but there are others where the algorithm fails. The MMPC tests for conditional independence between the variables and assumes that if conditional independence is not rejected, then the conditional independence statement holds. There are situations where this procedure leads to conditional independence being accepted that contradict conditional dependence relations in the data. This leads to edges being removed from the skeleton that are necessary for representing the dependence structure of the data.

One mechanism for an intelligent agent to adapt to substantial environmental changes is to change its decision making structure. Pervious work in this area has developed a context-dependent behavior selection architecture that uses structure change, i.e., changing the mutual inhibition structures of a behavior network, as the main mechanism to generate different behavior patterns according to different behavioral contexts. Given the important of network structure, this work investigates how the structure of a behavior network can be learned. We developed a structure learning method based on generic algorithm and applied it to a model crayfish that needs to survive in a simulated environment. The model crayfish is controlled by a mutual inhibition behavior network, whose structures are learned using the GA-based algorithm for different environment configurations. The results show that it is possible to learn robust and consistent network structures allowing intelligent agents to behave adaptively in a particular environment.

Oscillations lie at the core of many biological processes, from the cell cycle, to circadian oscillations and developmental processes. They are essential to enable organisms to adapt to varying conditions in environmental cycles, from day/night to seasonal. Transcriptional regulatory networks are one of the mechanisms behind these biological oscillations. One of the main problems of computational systems biology is elucidating the interaction between biological components. A common mathematical abstraction is to represent these interactions as networks whose nodes are the reactive species and the interactions are edges. There is abundant literature dealing with the reconstruction of the network structure from steady-state gene expression measurements; still, there are lots of advancements to be made because of the complex nature of biological systems. Experimental design is another obstacle to overcome; we wish to perform experiments that help us best define the network structure according to our current knowledge of the system. In the first chapters of this thesis we will focus on reconstructing the network structure of biological oscillators by explicitly leveraging the cyclical nature of the transcriptional signals. We present a method for reconstructing network interactions tailored to this special but important class of genetic circuits. The method is based on projecting the signal onto a set of oscillatory basis functions. We build a Bayesian hierarchical model within a frequency domain linear model in order to enforce sparsity and incorporate prior knowledge about the network structure. Experiments on real and simulated data show that the method can lead to substantial improvements over competing approaches if the oscillatory assumption is met, and remains competitive also in cases it is not. Having defined a model for gene expression in oscillatory systems, we also consider the problem of designing informative experiments for elucidating the dynamics and better identify the model. We demonstrate our approach on a benchmark scenario in plant biology, the circadian clock network of Arabidopsis thaliana, and discuss the different value of three types of commonly used experiments in terms of aiding the reconstruction of the network. Finally we provide the architecture and design of a software implementation to plug in statistical methods of gene expression inference and network reconstruction into a biological data integration platform.

Machine learning models such as AlphaFold can generate protein 3D conformation from primary sequence up to experimental accuracy, which gives rise to a bunch of research works to predict protein functions from 3D structures. Almost all of these works attempted to use graph neural networks (GNN) to learn 3D structures of proteins from 2D contact maps/graphs. Most of these works use rich 1D features such as ESM and LSTM embedding in addition to the contact graph. These rich 1D features essentially obfuscate the learning capability of GNNs. In this thesis, we evaluate the learning capabilities of GCNs from contact map graphs in the existing framework, where we attempt to incorporate distance information for better predictive performance. We found that GCNs fall far short with 1D-CNN without language models, even with distance information. Consequently, we further investigate the capabilities of GCNs to distinguish subgraph patterns corresponding to the InterPro domains. We found that GCNs perform better than highly rich sequence embedding with MLP in recognizing the structural patterns. Finally, we investigate the capability of GCNs to predict GO-terms (functions) individually. We found that GCNs perform almost on par in identifying GO-terms in the presence of only hard positive and hard negative examples. We also identified some GO-terms indistinguishable by GCNs and ESM2-based MLP models. This gives rise to new research questions to be investigated by future works.

A Bayesian network is graphical representation of the probabilistic relationships among set of variables and can be used to encode expert knowledge about uncertain domains. The structure of this model represents the set of conditional independencies among the variables in the data. Bayesian networks are widely applicable, having been used to model domains ranging from monitoring patients in an emergency room to predicting the severity of hailstorms. In this thesis, I focus on the problem of learning the structure of Bayesian networks from data. Under certain assumptions, the learned structure of a Bayesian network can represent causal relationships in the data. Constraint-based algorithms for structure learning are designed to accurately identify the structure of the distribution underlying the data and, therefore, the causal relationships. These algorithms use a series of conditional hypothesis tests to learn independence constraints on the structure of the model. When sample size is limited, these hypothesis tests are prone to errors. I present a comprehensive empirical evaluation of constraint-based algorithms and show that existing constraint-based algorithms are prone to many false negative errors in the constraints due to run- ning hypothesis tests with low statistical power. Furthermore, this analysis shows that many statistical solutions fail to reduce the overall errors of constraint-based algorithms. I show that new algorithms inspired by constraint satisfaction are able to produce significant improvements in structural accuracy. These constraint satisfaction algo- rithms exploit the interaction among the constraints to reduce error. First, I introduce an algorithm based on constraint optimization that is sound in the sample limit, like existing algorithms, but is guaranteed to produce a DAG. This new algorithm learns models with structural accuracy equivalent or better to existing algorithms. Second, I introduce an algorithm based constraint relaxation. Constraint relaxation combines different statistical techniques to identify constraints that are likely to be incorrect, and remove those constraints from consideration. I show that an algorithm combining constraint relaxation with constraint optimization produces Bayesian networks with significantly better structural accuracy when compared to existing structure learning algorithms, demonstrating the effectiveness of constraint satisfaction approaches for learning accurate structure of Bayesian networks.

Hypothesis-free learning is increasingly popular given the large amounts of data becoming available. Structure learning, a hypothesis-free approach, of graphical models is a field of growing interest due to the power of such models and lack of domain knowledge when applied on complex real-world data. State-of-the-art techniques improve on scalability of structure learning, which is often characterized by a large problem space. Nonetheless, these techniques still suffer computational bottlenecks that are yet to be approached. In this work, we focus on two popular models: dynamical linear systems and Markov random fields. For each case, we investigate major computational bottlenecks of baseline learning techniques. Next, we propose two frameworks that provide higher scalability using appropriate problem reformulation and efficient structure based heuristics. We perform experiments on synthetic and real data to validate our theoretical analysis. Current results show that we obtain a quality similar to expensive baseline techniques but with higher scalability. / Master of Science / Structure learning of graphical models is the process of understanding the interactions and influence between the variables of a given system. A few examples of such systems are road traffic systems, stock markets, and social networks. Learning the structure uncovers the invisible inter-variables relationships that govern their evolution. This process is key to qualitative analysis and forecasting. A classic approach to obtain the structure is through domain experts. For example, a financial expert could draw a graphical structure that encodes the relationships between different software companies based on his knowledge in the field. However, the absence of domain experts in the case of complex and heterogeneous systems has been a great motivation for the field of data driven, hypothesis free structure learning. Current techniques produce good results but unfortunately require a high computational cost and are often slow to execute. In this work, we focus on two popular graphical models that require computationally expensive structure learning methods. We first propose theoretical analysis of the high computational cost of current techniques. Next, we propose a novel approach for each model. Our proposed methods perform structure learning faster than baseline methods and provide a higher scalability to systems of large number of variables and large datasets as shown in our theoretical analysis and experimental results.

This thesis explores the application of Graph Neural Networks (GNNs), a subset of Geometric Deep Learning methods, for medical image analysis and causal structure learning. Tracking the progression of pathologies in chest radiography poses several challenges in anatomical motion estimation and image registration as this task requires spatially aligning the sequential X-rays and modelling temporal dynamics in change detection. The first part of this thesis proposes a novel approach for change detection in sequential Chest X-ray (CXR) scans using GNNs. The proposed model CheXRelNet utilizes local and global information in CXRs by incorporating intra-image and inter-image anatomical information and showcases an increased downstream performance for predicting the change direction for a pair of CXRs. The second part of the thesis focuses on using GNNs for causal structure learning. The proposed method introduces the concept of intervention on graphs and attempts to relate belief propagation in Bayesian Networks (BN) to message passing in GNNs. Specifically, the proposed method leverages the downstream prediction accuracy of a GNN-based model to infer the correctness of Directed Acyclic Graph (DAG) structures given observational data. Our experimental results do not reveal any correlation between the downstream prediction accuracy of GNNs and structural correctness and hence indicate the harms of directly relating message passing in GNNs to belief propagation in BNs. Overall, this thesis demonstrates the potential of GNNs in medical image analysis and highlights the challenges and limitations of applying GNNs to causal structure learning. / Master of Science / Graphs are a powerful way to represent different real-world data such as interactions between patient observations, co-morbidities, treatments, and relationships between different parts of the human anatomy. They are also a simple and intuitive way of representing causeand- effect relationships between related entities. Graph Neural Networks (GNNs) are neural networks that model such graph-structured data. In this thesis, we explore the applicability of GNNs in analyzing chest radiography and in learning causal relationships. In the first part of this thesis, we propose a method for monitoring disease progression over time in sequential chest X-rays (CXRs). This proposed model CheXRelNet focuses on the interactions within different regions of a CXR and temporal interactions between the same region compared in two CXRs taken at different times for a given patient and accurately predicts the disease progression trend. In the second part of the thesis, we explore if GNNs can be used for identifying causal relationships between covariates. We design a method that uses GNNs for ranking different graph structures based on how well the structures explain the observed data.

Redes Bayesianas (RB) são ferramentas probabilísticas amplamente aceitas para modelar e fazer inferências em domínios sob incertezas. Uma das maiores dificuldades na construção de uma RB é determinar a sua estrutura de modelo, a qual representa a estrutura de interdependências entre as variáveis modeladas. A estimativa exata da estrutura de modelo a partir de dados observados é, de forma geral, impraticável já que o número de estruturas possíveis cresce de forma super-exponencial com o número de variáveis. Métodos eficientes de aprendizagem aproximada tornam-se, portanto, essenciais para a construção de RBs verossímeis. O presente trabalho apresenta o Sistema Evolutivo Eficiente para Aprendizagem Estrutural de RBs, ou abreviadamente, EES-BN. Duas etapas de aprendizagem compõem EES-BN. A primeira etapa é encarregada de reduzir o espaço de busca mediante a aprendizagem de uma superestrutura. Para tal fim foram desenvolvidos dois métodos efetivos: Opt01SS e OptHPC, ambos baseados em testes de independência. A segunda etapa de EES-BN é um esquema de busca evolutiva que aproxima a estrutura do modelo respeitando as restrições estruturais aprendidas na superestrutura. Três blocos principais integram esta etapa: recombinação, mutação e injeção de diversidade. Para recombinação foi desenvolvido um novo operador (MergePop) visando ganhar eficiência de busca, o qual melhora o operador Merge de Wong e Leung (2004). Os operadores nos blocos de mutação e injeção de diversidade foram também escolhidos procurando um adequado equilíbrio entre exploração e utilização de soluções. Todos os blocos de EES-BN foram estruturados para operar colaborativamente e de forma auto-ajustável. Em uma serie de avaliações experimentais em RBs conhecidas de variado tamanho foi encontrado que EES-BN consegue aprender estruturas de RBs significativamente mais próximas às estruturas verdadeiras do que vários outros métodos representativos estudados (dois evolutivos: CCGA e GAK2, e dois não evolutivos: GS e MMHC). EES-BN tem mostrado também tempos computacionais competitivos, melhorando marcadamente os tempos dos outros métodos evolutivos e superando também ao GS nas redes de grande porte. A efetividade de EES-BN foi também comprovada em dois problemas relevantes em Bioinformática: i) reconstrução da rede deinterações intergênicas a partir de dados de expressão gênica, e ii) modelagem do chamado desequilíbrio de ligação a partir de dados genotipados de marcadores genéticos de populações humanas. Em ambas as aplicações, EES-BN mostrou-se capaz de capturar relações interessantes de significância biológica estabelecida. / Bayesian networks (BN) are probabilistic tools widely accepted for modeling and reasoning in domains under uncertainty. One of the most difficult tasks in the construction of a BN is the determination of its model structure, which is the inter-dependence structure of the problem variables. The exact estimation of the model structure from observed data is generally infeasible, since the number of possible structures grows super-exponentially with the number of variables. Efficient approximate methods are therefore essential for the construction of credible BN. In this work we present the Efficient Evolutionary System for learning BN structures (EES-BN). This system is composed by two learning phases. The first phase is responsible for the reduction of the search space by estimating a superstructure. For this task were developed two methods (Opt01SS and OptHPC), both based in independence tests. The second phase of EES-BN is an evolutionary design for finding the optimal model structure using the superstructure as the search space. Three main blocks compose this phase: recombination, mutation and diversity injection. With the aim to gain search efficiency was developed a new recombination operator (MergePop), which improves the Merge operator of Wong e Leung (2004). The operators for mutation and recombination blocks were also selected aiming to have an appropriate balance between exploitation and exploration of the solutions. All blocks in EES-BN were structured to operate in a collaborative and self-regulated fashion. Through a series of experiments and comparisons on benchmark BNs of varied dimensionality was found that EES-BN is able to learn BN structures markedly closer to the gold standard networks than various other representative methods (two evolutionary: CCGA and GAK2, and two non-evolutionary methods: GS and MMHC). The computational times of EES-BN were also found competitive, improving notably the times of the evolutionary methods and also the GS in the larger networks. The effectiveness of EES-BN was also verified in two real problems in bioinformatics: i) the reconstruction of a gene regulatory network from gene-expression data, and ii) the modeling of the linkage disequilibrium structures from genetic marker genotyped data of human populations. In both applications EES-BN proved to be able to recover interesting relationships with proven biological meaning.

Redes Bayesianas (RB) são ferramentas probabilísticas amplamente aceitas para modelar e fazer inferências em domínios sob incertezas. Uma das maiores dificuldades na construção de uma RB é determinar a sua estrutura de modelo, a qual representa a estrutura de interdependências entre as variáveis modeladas. A estimativa exata da estrutura de modelo a partir de dados observados é, de forma geral, impraticável já que o número de estruturas possíveis cresce de forma super-exponencial com o número de variáveis. Métodos eficientes de aprendizagem aproximada tornam-se, portanto, essenciais para a construção de RBs verossímeis. O presente trabalho apresenta o Sistema Evolutivo Eficiente para Aprendizagem Estrutural de RBs, ou abreviadamente, EES-BN. Duas etapas de aprendizagem compõem EES-BN. A primeira etapa é encarregada de reduzir o espaço de busca mediante a aprendizagem de uma superestrutura. Para tal fim foram desenvolvidos dois métodos efetivos: Opt01SS e OptHPC, ambos baseados em testes de independência. A segunda etapa de EES-BN é um esquema de busca evolutiva que aproxima a estrutura do modelo respeitando as restrições estruturais aprendidas na superestrutura. Três blocos principais integram esta etapa: recombinação, mutação e injeção de diversidade. Para recombinação foi desenvolvido um novo operador (MergePop) visando ganhar eficiência de busca, o qual melhora o operador Merge de Wong e Leung (2004). Os operadores nos blocos de mutação e injeção de diversidade foram também escolhidos procurando um adequado equilíbrio entre exploração e utilização de soluções. Todos os blocos de EES-BN foram estruturados para operar colaborativamente e de forma auto-ajustável. Em uma serie de avaliações experimentais em RBs conhecidas de variado tamanho foi encontrado que EES-BN consegue aprender estruturas de RBs significativamente mais próximas às estruturas verdadeiras do que vários outros métodos representativos estudados (dois evolutivos: CCGA e GAK2, e dois não evolutivos: GS e MMHC). EES-BN tem mostrado também tempos computacionais competitivos, melhorando marcadamente os tempos dos outros métodos evolutivos e superando também ao GS nas redes de grande porte. A efetividade de EES-BN foi também comprovada em dois problemas relevantes em Bioinformática: i) reconstrução da rede deinterações intergênicas a partir de dados de expressão gênica, e ii) modelagem do chamado desequilíbrio de ligação a partir de dados genotipados de marcadores genéticos de populações humanas. Em ambas as aplicações, EES-BN mostrou-se capaz de capturar relações interessantes de significância biológica estabelecida. / Bayesian networks (BN) are probabilistic tools widely accepted for modeling and reasoning in domains under uncertainty. One of the most difficult tasks in the construction of a BN is the determination of its model structure, which is the inter-dependence structure of the problem variables. The exact estimation of the model structure from observed data is generally infeasible, since the number of possible structures grows super-exponentially with the number of variables. Efficient approximate methods are therefore essential for the construction of credible BN. In this work we present the Efficient Evolutionary System for learning BN structures (EES-BN). This system is composed by two learning phases. The first phase is responsible for the reduction of the search space by estimating a superstructure. For this task were developed two methods (Opt01SS and OptHPC), both based in independence tests. The second phase of EES-BN is an evolutionary design for finding the optimal model structure using the superstructure as the search space. Three main blocks compose this phase: recombination, mutation and diversity injection. With the aim to gain search efficiency was developed a new recombination operator (MergePop), which improves the Merge operator of Wong e Leung (2004). The operators for mutation and recombination blocks were also selected aiming to have an appropriate balance between exploitation and exploration of the solutions. All blocks in EES-BN were structured to operate in a collaborative and self-regulated fashion. Through a series of experiments and comparisons on benchmark BNs of varied dimensionality was found that EES-BN is able to learn BN structures markedly closer to the gold standard networks than various other representative methods (two evolutionary: CCGA and GAK2, and two non-evolutionary methods: GS and MMHC). The computational times of EES-BN were also found competitive, improving notably the times of the evolutionary methods and also the GS in the larger networks. The effectiveness of EES-BN was also verified in two real problems in bioinformatics: i) the reconstruction of a gene regulatory network from gene-expression data, and ii) the modeling of the linkage disequilibrium structures from genetic marker genotyped data of human populations. In both applications EES-BN proved to be able to recover interesting relationships with proven biological meaning.