This thesis is a detailed examination of the expressive power of valued constraints and related complexity questions. The valued constraint satisfaction problem (VCSP) is a generalisation of the constraint satisfaction problem which allows to describe a variety of combinatorial optimisation problems. Although most results are stated in this framework, they can be interpreted equivalently in the framework of, for instance, pseudo-Boolean polynomials, Gibbs energy minimisation, or Markov Random Fields. We take a result of Cohen, Cooper and Jeavons that characterises the expressive power of valued constraint in terms of certain algebraic properties, and extend this result by showing yet another connection between the expressive power of valued constraints and linear programming. We prove a decidability result for fractional clones. We consider various classes of valued constraints and the associated cost functions with respect to the question of which of these classes can be expressed using only cost functions of bounded arities. We identify the first known example of an infinite chain of classes of constraints with strictly increasing expressive power. We present a full classification of various classes of constraints with respect to this problem. We study submodular constraints and cost functions. Submodular functions play a key role in combinatorial optimisation and are often considered to be a discrete analogue of convex functions. It has previously been an open problem whether all Boolean submodular cost functions can be decomposed into a sum of binary submodular cost functions over a possibly larger set of variables. This problem has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of cost functions, we answer this question negatively. Our results have several corollaries. First, we characterise precisely which submodular polynomials of degree 4 can be expressed by quadratic submodular polynomials. Next, we identify a novel class of submodular functions of arbitrary arities that can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the (s,t)-Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish for the first time that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions.

This work deals with an efficient and robust technique of performing Boolean operations on polygonal models. Full robustness is achieved within an internal representation based on planes and BSP (binary space partitioning) trees, in which operations can be carried out exactly in mere fixed precision arithmetic. Necessary conversions from the usual representation to the inner one and back, including their consequences are analyzed in detail. The performance of the method is optimized by a localization scheme in the form of an adaptive octree. The resulting implementation RazeCSG is experimentally compared with implementations used in practice Carve and Maya, which are not fully robust. For large models, RazeCSG shows only twice lower performance in the worst case than Carve, and is at least 130 times faster than Maya.

Na busca por soluções que maximizem a produção de etanol, o melhoramento genético de diferentes linhagens de levedura tornou-se foco de investigação em diversos centros de pesquisa. Com o recente sequenciamento de uma linhagem selvagem utilizada nas usinas sucroalcooleiras brasileiras, a linhagem PE-2 da espécie Saccharomyces cerevisiae, surgiu o interesse em estudar sua dinâmica durante o processo de fermentação a fim de encontrar aspectos que possam explicar como estas se tornaram mais adaptadas às dornas de fermentação mantendo a alta produtividade de bioetanol. A partir da análise transcricional da linhagem PE-2, Buscamos por métodos de inferência de redes que possam representar a dinâmica dessa levedura. Propomos nesse trabalho a modelagem de dados experimentais temporais das linhagens PE-2 e S288c (utilizada como referência) baseado em um modelo de Redes Booleanas. Trata-se de um modelo onde convertemos dados contínuos em dados discretos (0 or 1) no qual, de acordo com restrições ditadas pelo modelo, são inferidas redes que representem interações gênicas ao longo do tempo baseados nas amostras temporais. Conseguimos modelar, com sucesso, algumas redes utilizando conjuntos com 11 e 12 genes relacionados a genes pertencentes à via da glicólise e fermentação da levedura. / Ethanol production improvements give rise to the breeding of yeast strains, that became the investigation focus in several research centers. Recently, a wild strain used in Brazilian sugarcane industry was sequenced, the PE-2 strain of Saccharomyces cerevisiae, and this event brought an interest in studying the dynamics of the fermentation of this strain in order to understand which aspects this strain become more adapted to the fermentation conditions, maintaining a high capacity to produce bioethanol. From the analysis of transcriptional strain PE-2, we seek for inference networks methods that can represent the dynamics of this yeast.In this work, we model an experimental temporal data of strain PE-2 and strain S288c (used as a reference) based on Boolean networks model. In this model, the data are converted from continuous into discrete data (0 or 1) and, based on constraints rules of Boolean Network model, networks are inferred to represent gene interactions over time based on temporal data. We successfully model networks using a set with 11 and 12 genes related to yeast glycolysis and fermentation pathways.

The state of the art in machine learning of Boolean functions is to learn a hypothesis h, which is similar to a target hypothesis f, using a training sample of size N and a family of a priori models in a given hypothesis set H, such that h must belong to some model in this family. An important characteristic in learning is that h should also predict outcome values of f for previously unseen data, so the learning algorithm should minimize the generalization error which is the discrepancy measure between outcome values of f and h. The method proposed in this thesis learns family of models compatible with training samples of size N. Taking into account that generalizations are performed through equivalence classes in the Boolean function domain, the search space for finding the correct model is the projection of H in all possible partitions of the domain. This projection can be seen as a model lattice which is anti-isomorphic to the partition lattice and also has the property that for every chain in the lattice there exists a relation order given by the VC dimension of the models. Hence, we propose a model selector that uses the model lattice for selecting the best model with VC dimension compatible to a training sample of size N, which is closely related to the classical sample complexity theorem. Moreover, this model selector generalizes a set of learning methods in the literature (i.e, it unifies methods such as: the feature selection problem, multiresolution representation and decision tree representation) using models generated from a subset of partitions of the partition space. Furthermore, considering as measure associated to the models the estimated error of the learned hypothesis, the chains in the lattice present the so-called U-curve phenomenon. Therefore, we can use U-curve search algorithms in the model lattice to select the best models and, consequently, the corresponding VC dimension. However, this new generation of learning algorithms requires an increment of computational power. In order to face this problem, we introduce a stochastic U-curve algorithm to work on bigger lattices. Stochastic search algorithms do not guarantee finding optimal solutions, but maximize the mean quality of the solution for a given amount of computational power. The contribution of this thesis advances both the state of the art in machine learning theory and in practical problem solutions in learning. / O estado da arte em aprendizado de funções Booleanas é aprender uma hipótese h, que é similar a uma hipótese objetivo f, a partir de uma amostra de tamanho N e uma família de modelos a priori em um dado conjunto de hipóteses H, tal que h deve pertencer a algum modelo nesta família. Uma característica importante no aprendizado é que h deve também predizer resultados de f para elementos que não aparecem no conjunto de treinamento, então o algoritmo de aprendizado deve minimizar o erro de generalização, o qual mede a discrepância entre os resultados de f e h. O método proposto nesta tese aprende uma família de modelos compatíveis com um conjunto de treinamento de tamanho N. Tomando em consideração que as generalizações são realizadas através de classes de equivalência no domínio da função Booleana, o espaço de busca para encontrar um modelo apropriado é a projeção de H em todas as possíveis partições do domínio. Esta projeção pode ser vista como um reticulado de modelos que é anti-isomórfica ao reticulado de partições e também tem a propriedade que para cada cadeia no reticulado existe uma relação de ordem dada pela dimensão VC dos modelos. Portanto, propomos um seletor de modelos que usa o reticulado de modelos para selecionar o melhor modelo com dimensão VC compatível ao conjunto de treinamento de tamanho N, o qual é intimamente relacionado ao teorema clássico de complexidade da amostra. Além disso, este seletor de modelos generaliza um conjunto de métodos de aprendizado na literatura (i.e, ele unifica métodos tais como: o problema de seleção de características, a representação multiresolução e a representação por árvores de decisão) usando modelos gerados por um subconjunto de partições do espaço de partições. Ademais, considerando como medida associada aos modelos o erro de estimação da hipótese aprendida, as cadeias no reticulado apresentam o fenômeno chamado U-curve. Portanto, podemos usar algoritmos de busca $U$-curve no reticulado de modelos para selecionar os melhores modelos, consequentemente, a correspondente dimensão VC. No entanto, esta nova geração de algoritmos de aprendizado requerem um incremento de poder computacional. Para enfrentar este problema, introduzimos o algoritmo Stochastic $U$-curve para trabalhar em reticulados maiores. Algoritmos de busca estocásticos não garantem encontrar soluções ótimas, mas maximizam a qualidade média das soluções para uma determinada quantidade de poder computacional. A contribuição desta tese avança ambos o estado da arte na teoria de aprendizado de máquina e soluções a problemas práticos em aprendizado.

Gene expression is tightly regulated by complex transcriptional regulatory mechanisms to achieve specific expression patterns, which are essential to facilitate important biological processes such as embryonic development. Dysregulation of gene expression can lead to diseases such as cancers. A better understanding of the transcriptional regulation will therefore not only advance the understanding of fundamental biological processes, but also provide mechanistic insights into diseases. The earlier versions of high-throughput expression profiling techniques were limited to measuring average gene expression across large pools of cells. In contrast, recent technological improvements have made it possible to perform expression profiling in single cells. Single-cell expression profiling is able to capture heterogeneity among single cells, which is not possible in conventional bulk expression profiling. In my PhD, I focus on developing new algorithms, as well as benchmarking and utilising existing algorithms to study the transcriptomes of various biological systems using single-cell expression data. I have developed two different single-cell specific network inference algorithms, BTR and SPVAR, which are based on two different formalisms, Boolean and autoregression frameworks respectively. BTR was shown to be useful for improving existing Boolean models with single-cell expression data, while SPVAR was shown to be a conservative predictor of gene interactions using pseudotime-ordered single-cell expression data. In addition, I have obtained novel biological insights by analysing single-cell RNAseq data from the epiblast stem cells reprogramming and the leukaemia systems. Three different driver genes, namely Esrrb, Klf2 and GY118F, were shown to drive reprogramming of epiblast stem cells via different reprogramming routes. As for the leukaemia system, FLT3-ITD and IDH1-R132H mutations were shown to interact with each other and potentially predispose some cells for developing acute myeloid leukaemia.

As reações químicas que resultam da expressão de genes são complexas e ainda não são total- mente compreendidas. Sabe-se que os genes enviam, recebem, e processam informações formando uma complexa rede de comunicação, mas a arquitetura e dinâmica destas redes não são totalmente conhecidas. Dessa forma, um problema importante é determinar como os genes se relacionam dentro da célula. Esse processo de determinar o relacionamento entre os genes é conhecido como inferência de redes gênicas. Uma das formas para representar o relacionamento entre os genes é usar modelos matemáticos e computacionais de Redes Gênicas. Em especial, um dos modelos de grande interesse é o de Redes Booleanas (BN - do inglês Boolean Networks), no qual os genes podem assumir dois estados, ativo ou inativo, se estão, respectivamente, expressos ou não. Estes estados podem variar ao longo do tempo, dependendo de como os genes se relacionam. Nosso interesse está em estudar um caso particular deste modelo, conhecido como Redes Booleanas Limiarizadas, onde apenas uma classe de funções booleanas é utilizada para construir as BNs. Para inferir as Redes Booleanas Limiarizadas, usamos um algoritmo constituído de dois passos. Primeiro, usamos o arcabouço do Problema de Satisfação de Restrições (CSP - do inglês Constraint Satisfaction Problem) para inferir conjuntos de soluções consistentes com uma dada série temporal de um conjunto de genes. Em seguida analisamos o comportamento dinâmico das soluções encon- tradas , filtrando conjuntos de soluções de maior interesse para testes práticos em laboratório. Usando o arcabouço do CSP, construímos um solver, usando a biblioteca Gecode,1 para inferência de redes consistentes, usando como entrada uma série temporal oriunda de dados de microarrays. Em seguida, através da simulação da dinâmica de uma amostra das redes encontradas no passo anterior, fomos capazes de determinar algumas restrições interessantes para filtrar o conjunto de redes. Aplicamos o nosso método para três conjuntos de dados: dois artificiais, e para validação, usamos uma série temporal de uma rede artificial conhecida na literatura. Com isso fomos capazes de inferir conjuntos de redes gênicas de possível interesse para testes em laboratório. / The chemical reactions that result in gene expression are complex and not yet fully understood. It is known that genes send, receive and process information to form a complex network of com- munication, but the architecture and dynamics of these networks are not fully known. Thus, one major problem is to determine how genes are linked within the cell. This process of determining the relationship between genes is known as inference of genetic networks. One way to represent the relationship between genes is to use mathematical and computer models of genetic networks. In particular, one of the models of great interest are Boolean Networks (BN), in which genes can take two states, active or inactive, if they are, respectively, expressed or not. These states may vary over time, depending on how genes are related. Our interest is in studying a case of this particular model, known as thresholded Boolean networks, where only one class of Boolean functions is used to build the GNs. To infer the thresholded Boolean networks, we use an algorithm that consists of two steps. First, we use the framework of Constraint Satisfaction Problem (CSP) to infer sets of solutions consistent with a time series of a given set of genes. Then analyze the dynamic behavior of the solutions, filtering sets of solutions with interest for practical tests in the laboratory. Using the framework of the CSP, we constructed a solver, using the library Gecode, 2 for in- ference of consistent networks, using as input a time series arising from microarrays data. Then, by simulating the dynamics of a sample of networks found in the previous step, we were able to determine some interesting constraints to filter the set of networks. We apply our method to three datasets: two artificial, and for validation, we use a time series of an artificial network known from literature. Thus we were able to infer genetic networks sets of possible interest for laboratory tests.

Na busca por soluções que maximizem a produção de etanol, o melhoramento genético de diferentes linhagens de levedura tornou-se foco de investigação em diversos centros de pesquisa. Com o recente sequenciamento de uma linhagem selvagem utilizada nas usinas sucroalcooleiras brasileiras, a linhagem PE-2 da espécie Saccharomyces cerevisiae, surgiu o interesse em estudar sua dinâmica durante o processo de fermentação a fim de encontrar aspectos que possam explicar como estas se tornaram mais adaptadas às dornas de fermentação mantendo a alta produtividade de bioetanol. A partir da análise transcricional da linhagem PE-2, Buscamos por métodos de inferência de redes que possam representar a dinâmica dessa levedura. Propomos nesse trabalho a modelagem de dados experimentais temporais das linhagens PE-2 e S288c (utilizada como referência) baseado em um modelo de Redes Booleanas. Trata-se de um modelo onde convertemos dados contínuos em dados discretos (0 or 1) no qual, de acordo com restrições ditadas pelo modelo, são inferidas redes que representem interações gênicas ao longo do tempo baseados nas amostras temporais. Conseguimos modelar, com sucesso, algumas redes utilizando conjuntos com 11 e 12 genes relacionados a genes pertencentes à via da glicólise e fermentação da levedura. / Ethanol production improvements give rise to the breeding of yeast strains, that became the investigation focus in several research centers. Recently, a wild strain used in Brazilian sugarcane industry was sequenced, the PE-2 strain of Saccharomyces cerevisiae, and this event brought an interest in studying the dynamics of the fermentation of this strain in order to understand which aspects this strain become more adapted to the fermentation conditions, maintaining a high capacity to produce bioethanol. From the analysis of transcriptional strain PE-2, we seek for inference networks methods that can represent the dynamics of this yeast.In this work, we model an experimental temporal data of strain PE-2 and strain S288c (used as a reference) based on Boolean networks model. In this model, the data are converted from continuous into discrete data (0 or 1) and, based on constraints rules of Boolean Network model, networks are inferred to represent gene interactions over time based on temporal data. We successfully model networks using a set with 11 and 12 genes related to yeast glycolysis and fermentation pathways.

Vectorial Boolean functions are used as S-boxes in cryptosystems. To design inequivalent vectorial Boolean functions resistant to known attacks is one of the challenges in cryptography. Verifying whether two vectorial Boolean functions are equivalent or not is the final step in this challenge. Hence, finding a fast technique for determining whether two given vectorial Boolean functions are equivalent is an important problem. A special class of the equivalence called restricted extended affine (REA) equivalence is studied in this thesis. We study the verification complexity of REA-equivalence of two vectorial Boolean functions for some types, namely types I to VI. We first review the verification of the REA-equivalence types I to IV given in the recent work of Budaghyan and Kazymyrov (2012). Furthermore, we present the complexities of the verification of REA-equivalence types I and IV in the case basic simultaneous Gaussian elimination method is used. Next, we present two new REA-equivalence types V and VI with their complexities. Finally, we give the algorithms of each type I to VI with their MAGMA codes.

Functional decomposition aims at finding efficient representations for Boolean functions. It is used in many applications, including multi-level logic synthesis, formal verification, and testing. This dissertation presents novel heuristic algorithms for functional decomposition. These algorithms take advantage of suitable representations of the Boolean functions in order to be efficient. The first two algorithms compute simple-disjoint and disjoint-support decompositions. They are based on representing the target function by a Reduced Ordered Binary Decision Diagram (BDD). Unlike other BDD-based algorithms, the presented ones can deal with larger target functions and produce more decompositions without requiring expensive manipulations of the representation, particularly BDD reordering. The third algorithm also finds disjoint-support decompositions, but it is based on a technique which integrates circuit graph analysis and BDD-based decomposition. The combination of the two approaches results in an algorithm which is more robust than a purely BDD-based one, and that improves both the quality of the results and the running time. The fourth algorithm uses circuit graph analysis to obtain non-disjoint decompositions. We show that the problem of computing non-disjoint decompositions can be reduced to the problem of computing multiple-vertex dominators. We also prove that multiple-vertex dominators can be found in polynomial time. This result is important because there is no known polynomial time algorithm for computing all non-disjoint decompositions of a Boolean function. The fifth algorithm provides an efficient means to decompose a function at the circuit graph level, by using information derived from a BDD representation. This is done without the expensive circuit re-synthesis normally associated with BDD-based decomposition approaches. Finally we present two publications that resulted from the many detours we have taken along the winding path of our research. / QC 20100909

In this thesis, the geometric margin is used for the first time as the robustness indicator of an uncoupled cellular neural network implementing a given Boolean function. First, robust template design for uncoupled cellular neural networks implementing linearly separable Boolean functions by support vector machines is proposed. A fast sequential minimal optimization algorithm is presented to find maximal margin classifiers, which in turn determine the robust templates. Some general properties of robust templates are investigated. An improved CFC algorithm implementing an arbitrarily given Boolean function is proposed. Two illustrative examples are provided to demonstrate the validity of the proposed method.