Lattice structures that parameterize regulatory network dynamics.

We consider two types of models of regulatory network dynamics: Boolean maps and systems of switching ordinary differential equations. Our goal is to construct all models in each category that are compatible with the directed signed graph that describe the network interactions. This leads to consideration of lattice of monotone Boolean functions (MBF), poset of non-degenerate MBFs, and a lattice of chains in these sets. We describe explicit inductive construction of these posets where the induction is on the number of inputs in MBF. Our results allow enumeration of potential dynamic behavior of the network for both model types, subject to practical limitation imposed by the size of the lattice of MBFs described by the Dedekind number.

Dynamics of ecosystem services along ecological network seascapes

Human societies depend on services provided by ecosystems, from local needs as clean water and pest control to global services like ozone layer and the ocean biological pump. Ecosystem services are intrinsically linked to the states of the ecosystem, which are, in turn, governed by a complex web of ecological interactions. These interactions and, consequently, the services they support, are increasingly under threat from environmental changes driven by human activities. Therefore, safeguarding these vital services require an understanding of how the structure and dynamics of ecological interactions are affected by environmental change. A critical step towards this goal is the development of an integrative theoretical framework that can elucidate how ecosystem services are sustained or impaired by interactions within these complex ecosystems in fluctuating environments. Recent years have seen significant progress in quantitatively characterizing the organization and the dynamics of ecological interactions through the study of ecological networks. However, linking temporally varying network structure in fluctuating environments, the seascapes of ecological networks, and their impact on ecosystem services remains a challenge. We propose an approach based upon merging empirical ecological network analysis with Boolean functions and modeling techniques accounting for fluctuating environments to tackle how ecosystem services are affected by the changing structure and dynamics of ecological networks. The approach aims to contribute to the study of how the organization of ecological interactions affects the persistence of ecosystem services. Specifically, we discuss how this approach can be used provide new insights into how environmental change affect the relationship between ecological networks and ecosystem services. The combination of information on ecosystem services, Boolean networks and fluctuating environments might allow to enhance the research around conservation strategies for preserving biodiversity and ecosystem services in the face of ongoing environmental change.

Solving classification tasks by a receptron based on nonlinear optical speckle fields.

Among several approaches to tackle the problem of energy consumption in modern computing systems, two solutions are currently investigated: one consists of artificial neural networks (ANNs) based on photonic technologies, the other is a different paradigm compared to ANNs and it is based on random networks of non-linear nanoscale junctions resulting from the assembling of nanoparticles or nanowires as substrates for neuromorphic computing. These networks show the presence of emergent complexity and collective phenomena in analogy with biological neural networks characterized by self-organization, redundancy, and non-linearity. Starting from this background, we propose and formalize a generalization of the perceptron model to describe a classification device based on a network of interacting units where the input weights are non-linearly dependent. We show that this model, called "receptron", provides substantial advantages compared to the perceptron as, for example, the solution of non-linearly separable Boolean functions with a single device. The receptron model is used as a starting point for the implementation of an all-optical device that exploits the non-linearity of optical speckle fields produced by a solid scatterer. By encoding these speckle fields we generated a large variety of target Boolean functions. We demonstrate that by properly setting the model parameters, different classes of functions with different multiplicity can be solved efficiently. The optical implementation of the receptron scheme opens the way for the fabrication of a completely new class of optical devices for neuromorphic data processing based on a very simple hardware.

Explaining Cannabis Use by Adolescents: A Comparative Assessment of Fuzzy Set Qualitative Comparative Analysis and Ordered Logistic Regression.

Background: This study assesses the relevance of several factors that the literature on the substance use of adolescents considers relevant. The factors embed individual variables, such as gender or age; factors linked with parental style; and variables that are associated with the teenager's social environment. Methods: The study applies complementarily ordered logistic regression (OLR) and fuzzy set qualitative comparative analysis (fsQCA) in a sample of 1935 teenagers of Tarragona (Spain). Results: The OLR showed that being female (OR = 0.383; p < 0.0001), parental monitoring (OR = 0.587; p = 0.0201), and religiousness (OR = 0.476; p = 0.006) are significant inhibitors of cannabis consumption. On the other hand, parental tolerance to substance use (OR = 42.01; p < 0.0001) and having close peers that consume substances (OR = 5.60; p < 0.0001) act as enablers. The FsQCA allowed for fitting the linkages between the factors from a complementary perspective. (1) The coverage (cov) and consistency (cons) attained by the explanatory solutions of use (cons = 0.808; cov = 0.357) are clearly lower than those obtained by the recipes for nonuse (cons = 0.952; cov = 0.869). (2) The interaction of being male, having a tolerant family to substance use, and peer attitudes toward substances are continuously present in the profiles that are linked to a risk of cannabis smoking. (3) The most important recipe that explains resistance to cannabis is simply parental disagreement with substance consumption. Conclusions: On the one hand, the results of the OLR allow for determining the strength of an evaluated risk or protective factors according to the value of the OR. On the other hand, the fsQCA allows for the identification not only of profiles where there is a high risk of cannabis use, but also profiles where there is a low risk.

Boolean function metrics can assist modelers to check and choose logical rules.

Computational models of biological processes provide one of the most powerful methods for a detailed analysis of the mechanisms that drive the behavior of complex systems. Logic-based modeling has enhanced our understanding and interpretation of those systems. Defining rules that determine how the output activity of biological entities is regulated by their respective inputs has proven to be challenging. Partly this is because of the inherent noise in data that allows multiple model parameterizations to fit the experimental observations, but some of it is also due to the fact that models become increasingly larger, making the use of automated tools to assemble the underlying rules indispensable. We present several Boolean function metrics that provide modelers with the appropriate framework to analyze the impact of a particular model parameterization. We demonstrate the link between a semantic characterization of a Boolean function and its consistency with the model's underlying regulatory structure. We further define the properties that outline such consistency and show that several of the Boolean functions under study violate them, questioning their biological plausibility and subsequent use. We also illustrate that regulatory functions can have major differences with regard to their asymptotic output behavior, with some of them being biased towards specific Boolean outcomes when others are dependent on the ratio between activating and inhibitory regulators. Application results show that in a specific signaling cancer network, the function bias can be used to guide the choice of logical operators for a model that matches data observations. Moreover, graph analysis indicates that commonly used Boolean functions become more biased with increasing numbers of regulators, supporting the idea that rule specification can effectively determine regulatory outcome despite the complex dynamics of biological networks.

On the Fourier transform of a quantitative trait: Implications for compressive sensing.

This paper explores the genotype-phenotype relationship. It outlines conditions under which the dependence of a quantitative trait on the genome might be predictable, based on measurement of a limited subset of genotypes. It uses the theory of real-valued Boolean functions in a systematic way to translate trait data into the Fourier domain. Important trait features, such as the roughness of the trait landscape or the modularity of a trait have a simple Fourier interpretation. Ruggedness at a gene location corresponds to high sensitivity to mutation, while a modular organization of gene activity reduces such sensitivity. Traits where rugged loci are rare will naturally compress gene data in the Fourier domain, leading to a sparse representation of trait data, concentrated in identifiable, low-level coefficients. This Fourier representation of a trait organizes epistasis in a form which is isometric to the trait data. As Fourier matrices are known to be maximally incoherent with the standard basis, this permits employing compressive sensing techniques to work from data sets that are relatively small-sometimes even of polynomial size-compared to the exponentially large sets of possible genomes. This theory provides a theoretical underpinning for systematic use of Boolean function machinery to dissect the dependency of a trait on the genome and environment.

Extracting boolean and probabilistic rules from trained neural networks.

This paper presents two approaches to extracting rules from a trained neural network consisting of linear threshold functions. The first one leads to an algorithm that extracts rules in the form of Boolean functions. Compared with an existing one, this algorithm outputs much more concise rules if the threshold functions correspond to 1-decision lists, majority functions, or certain combinations of these. The second one extracts probabilistic rules representing relations between some of the input variables and the output using a dynamic programming algorithm. The algorithm runs in pseudo-polynomial time if each hidden layer has a constant number of neurons. We demonstrate the effectiveness of these two approaches by computational experiments.

Boolean Functions with Multiplicative Complexity 3 and 4.

Multiplicative complexity (MC) is defined as the minimum number of AND gates required to implement a function with a circuit over the basis (AND, XOR, NOT). Boolean functions with MC 1 and 2 have been characterized in Fischer and Peralta (2002), and Find et al. (2017), respectively. In this work, we identify the affine equivalence classes for functions with MC 3 and 4. In order to achieve this, we utilize the notion of the dimension dim(f) of a Boolean function in relation to its linearity dimension, and provide a new lower bound suggesting that the multiplicative complexity of f is at least [dim(f)/2]. For MC 3, this implies that there are no equivalence classes other than those 24 identified in Çalik et al. (2018). Using the techniques from Çalik et al. and the new relation between the dimension and MC, we identify all 1277 equivalence classes having MC 4. We also provide a closed formula for the number of n-variable functions with MC 3 and 4. These results allow us to construct AND-optimal circuits for Boolean functions that have MC 4 or less, independent of the number of variables they are defined on.

Learning and Searching Pseudo-Boolean Surrogate Functions from Small Samples.

When searching for input configurations that optimise the output of a system, it can be useful to build a statistical model of the system being optimised. This is done in approaches such as surrogate model-based optimisation, estimation of distribution algorithms, and linkage learning algorithms. This article presents a method for modelling pseudo-Boolean fitness functions using Walsh bases and an algorithm designed to discover the non-zero coefficients while attempting to minimise the number of fitness function evaluations required. The resulting models reveal linkage structure that can be used to guide a search of the model efficiently. It presents experimental results solving benchmark problems in fewer fitness function evaluations than those reported in the literature for other search methods such as EDAs and linkage learners.

Revision of Boolean Models of Regulatory Networks Using Stable State Observations.

Models of biological regulatory networks are essential to understand cellular processes. However, the definition of such models is still mostly manually performed, and consequently prone to error. Moreover, as new experimental data are acquired, models need to be revised and updated. Here, we propose a model revision procedure and associated tool, capable of providing the set of minimal repairs to render a model consistent with a set of experimental observations. We consider four possible repair operations, using a lexicographic optimization criterion, giving preference to function repairs over topological ones. Also, we consider observations at stable state discarding the model dynamics. In this article, we extend our previous work to tackle the problem of repairing nodes with multiple reasons of inconsistency. We evaluate our tool on five publicly available logical models. We perform random changes considering several parameter configurations to assess the tool repairing capabilities. Whenever a model is repaired under the time limit, the tool successfully produces the optimal solutions to repair the model. Instances were generated without the previous limitation to validate this extended approach.

Layered patterns in nature, medicine, and materials: quantifying anisotropic structures and cyclicity.

Various natural patterns-such as terrestrial sand dune ripples, lamellae in vertebrate bones, growth increments in fish scales and corals, aortas and lamellar corpuscles in humans and animals-comprise layers of different thicknesses and lengths. Microstructures in manmade materials-such as alloys, perlite steels, polymers, ceramics, and ripples induced by laser on the surface of graphen-also exhibit layered structures. These layered patterns form a record of internal and external factors regulating pattern formation in their various systems, making it potentially possible to recognize and identify in their incremental sequences trends, periodicities, and events in the formation history of these systems. The morphology of layered systems plays a vital role in developing new materials and in biomimetic research. The structures and sizes of these two-dimensional (2D) patterns are characteristically anisotropic: That is, the number of layers and their absolute thicknesses vary significantly in different directions. The present work develops a method to quantify the morphological characteristics of 2D layered patterns that accounts for anisotropy in the object of study. To reach this goal, we use Boolean functions and an N-partite graph to formalize layer structure and thickness across a 2D plane and to construct charts of (1) "layer thickness vs. layer number" and (2) "layer area vs. layer number." We present a parameter disorder of layer structure (DStr) to describe the deviation of a study object's anisotropic structure from an isotropic analog and illustrate that charts and DStr could be used as local and global morphological characteristics describing various layered systems such as images of, for example, geological, atmospheric, medical, materials, forensic, plants, and animals. Suggested future experiments could lead to new insights into layered pattern formation.

Repairing Boolean logical models from time-series data using Answer Set Programming.

BACKGROUND: Boolean models of biological signalling-regulatory networks are increasingly used to formally describe and understand complex biological processes. These models may become inconsistent as new data become available and need to be repaired. In the past, the focus has been shed on the inference of (classes of) models given an interaction network and time-series data sets. However, repair of existing models against new data is still in its infancy, where the process is still manually performed and therefore slow and prone to errors. RESULTS: In this work, we propose a method with an associated tool to suggest repairs over inconsistent Boolean models, based on a set of atomic repair operations. Answer Set Programming is used to encode the minimal repair problem as a combinatorial optimization problem. In particular, given an inconsistent model, the tool provides the minimal repairs that render the model capable of generating dynamics coherent with a (set of) time-series data set(s), considering either a synchronous or an asynchronous updating scheme. CONCLUSIONS: The method was validated using known biological models from different species, as well as synthetic models obtained from randomly generated networks. We discuss the method's limitations regarding each of the updating schemes and the considered minimization algorithm.

Small Low-Depth Circuits for Cryptographic Applications.

We present techniques to obtain small circuits which also have low depth. The techniques apply to typical cryptographic functions, as these are often specified over the field GF (2), and they produce circuits containing only AND, XOR and XNOR gates. The emphasis is on the linear components (those portions containing no AND gates). A new heuristic, DCLO (for depth-constrained linear optimization), is used to create small linear circuits given depth constraints. DCLO is repeatedly used in a See-Saw method, alternating between optimizing the upper linear component and the lower linear component. The depth constraints specify both the depth at which each input arrives and restrictions on the depth for each output. We apply our techniques to cryptographic functions, obtaining new results for the S-Box of the Advanced Encryption Standard, for multiplication of binary polynomials, and for multiplication in finite fields. Additionally, we constructed a 16-bit S-Box using inversion in GF (216) which may be significantly smaller than alternatives.

Guessing with a Bit of Help.

What is the value of just a few bits to a guesser? We study this problem in a setup where Alice wishes to guess an independent and identically distributed (i.i.d.) random vector and can procure a fixed number of k information bits from Bob, who has observed this vector through a memoryless channel. We are interested in the guessing ratio, which we define as the ratio of Alice's guessing-moments with and without observing Bob's bits. For the case of a uniform binary vector observed through a binary symmetric channel, we provide two upper bounds on the guessing ratio by analyzing the performance of the dictator (for general k ≥ 1 ) and majority functions (for k = 1 ). We further provide a lower bound via maximum entropy (for general k ≥ 1 ) and a lower bound based on Fourier-analytic/hypercontractivity arguments (for k = 1 ). We then extend our maximum entropy argument to give a lower bound on the guessing ratio for a general channel with a binary uniform input that is expressed using the strong data-processing inequality constant of the reverse channel. We compute this bound for the binary erasure channel and conjecture that greedy dictator functions achieve the optimal guessing ratio.

Upper Bounds on the Multiplicative Complexity of Symmetric Boolean Functions.

A special metric of interest about Boolean functions is multiplicative complexity (MC): the minimum number of AND gates sufficient to implement a function with a Boolean circuit over the basis {XOR, AND, NOT}. In this paper we study the MC of symmetric Boolean functions, whose output is invariant upon reordering of the input variables. Based on the Hamming weight method from Muller and Preparata (1975), we introduce new techniques that yield circuits with fewer AND gates than upper bounded by Boyar et al. in 2000 and by Boyar and Peralta in 2008. We generate circuits for all such functions with up to 25 variables. As a special focus, we report concrete upper bounds for the MC of elementary symmetric functions ∑ k n and counting functions ∑ k n with up to n = 25 input variables. In particular, this allows us to answer two questions posed in 2008: both the elementary symmetric ∑ 4 8 and the counting ∑ 4 8 functions have MC 6. Furthermore, we show upper bounds for the maximum MC in the class of n-variable symmetric Boolean functions, for each n up to 132.

The Multiplicative Complexity of 6-variable Boolean Functions.

The multiplicative complexity of a Boolean function is the minimum number of two-input AND gates that are necessary and sufficient to implement the function over the basis (AND, XOR, NOT). Finding the multiplicative complexity of a given function is computationally intractable, even for functions with small number of inputs. Turan et al. [1] showed that n-variable Boolean functions can be implemented with at most n-1 AND gates for n ≤ 5. A counting argument can be used to show that, for n ≥ 7, there exist n-variable Boolean functions with multiplicative complexity of at least n. In this work, we propose a method to find the multiplicative complexity of Boolean functions by analyzing circuits with a particular number of AND gates and utilizing the affine equivalence of functions. We use this method to study the multiplicative complexity of 6-variable Boolean functions, and calculate the multiplicative complexities of all 150357 affine equivalence classes. We show that any 6-variable Boolean function can be implemented using at most 6 AND gates. Additionally, we exhibit specific 6-variable Boolean functions which have multiplicative complexity 6.

Algorithm to identify the optimal perturbation based on the net basin-of-state of perturbed states in Boolean network.

Boolean networks are widely used to model gene regulatory networks and to design therapeutic intervention strategies to affect the long-term behavior of systems. Here, the authors investigate the 1 bit perturbation, which falls under the category of structural intervention. The authors' idea is that, if and only if a perturbed state evolves from a desirable attractor to an undesirable attractor or from an undesirable attractor to a desirable attractor, then the size of basin of attractor of a desirable attractor may decrease or increase. In this case, if the authors obtain the net BOS of the perturbed states, they can quickly obtain the optimal 1 bit perturbation by finding the maximum value of perturbation gain. Results from both synthetic and real biological networks show that the proposed algorithm is not only simpler and but also performs better than the previous basin-of-states (BOS)-based algorithm by Hu et al..

An algorithm for judging and generating multivariate quadratic quasigroups over Galois fields.

As the basic cryptographic structure for multivariate quadratic quasigroup (MQQ) scheme, MQQ has been one of the latest tools in designing MQ cryptosystem. There have been several construction methods for MQQs in the literature, however, the algorithm for judging whether quasigroups of any order are MQQs over Galois fields is still lacking. To this end, the objective of this paper is to establish a necessary and sufficient condition for a given quasigroup of order pkd to be an MQQ over [Formula: see text]. Based on this condition, we then propose an algorithm to justify whether or not a given quasigroup in the form of multiplication table of any order pkd is an MQQ over [Formula: see text], and generate the d Boolean functions of the MQQ if the quasigroup is an MQQ. As a result, we can obtain all the MQQs over [Formula: see text] in theory using the proposed algorithm. Two examples are provided to illustrate the validity of our method.

Evolutionary Algorithms for Boolean Functions in Diverse Domains of Cryptography.

The role of Boolean functions is prominent in several areas including cryptography, sequences, and coding theory. Therefore, various methods for the construction of Boolean functions with desired properties are of direct interest. New motivations on the role of Boolean functions in cryptography with attendant new properties have emerged over the years. There are still many combinations of design criteria left unexplored and in this matter evolutionary computation can play a distinct role. This article concentrates on two scenarios for the use of Boolean functions in cryptography. The first uses Boolean functions as the source of the nonlinearity in filter and combiner generators. Although relatively well explored using evolutionary algorithms, it still presents an interesting goal in terms of the practical sizes of Boolean functions. The second scenario appeared rather recently where the objective is to find Boolean functions that have various orders of the correlation immunity and minimal Hamming weight. In both these scenarios we see that evolutionary algorithms are able to find high-quality solutions where genetic programming performs the best.

A universal symmetry detection algorithm.

Research on symmetry detection focuses on identifying and detecting new types of symmetry. The paper presents an algorithm that is capable of detecting any type of permutation-based symmetry, including many types for which there are no existing algorithms. General symmetry detection is library-based, but symmetries that can be parameterized, (i.e. total, partial, rotational, and dihedral symmetry), can be detected without using libraries. In many cases it is faster than existing techniques. Furthermore, it is simpler than most existing techniques, and can easily be incorporated into existing software. The algorithm can also be used with virtually any type of matrix-based symmetry, including conjugate symmetry.