Search

Graphical abstract, We present a method for efficiently and effectively assessing whether and where two proteins can interact with each other to form a complex. This is still largely an open problem, even for those relatively few cases where the 3D structure of both proteins is known. In fact, even if much of the information about the interaction is encoded in the chemical and geometric features of the structures, the set of possible contact patches and of their relative orientations are too large to be computationally affordable in a reasonable time, thus preventing the compilation of reliable interactome. Our method is able to rapidly and quantitatively measure the geometrical shape complementarity between interacting proteins, comparing their molecular iso-electron density surfaces expanding the surface patches in term of 2D Zernike polynomials. We first test the method against the real binding region of a large dataset of known protein complexes, reaching a success rate of 0.72. We then apply the method for the blind recognition of binding sites, identifying the real region of interaction in about 60% of the analyzed cases. Finally, we investigate how the efficiency in finding the right binding region depends on the surface roughness as a function of the expansion order.

We propose a novel numerical method able to determine efficiently and effectively the relationship of complementarity between portions of proteins surfaces. This innovative and general procedure, based on the representation of the molecular iso-electron density surface in terms of 2D Zernike polynomials, allows the rapid and quantitative assessment of the geometrical shape complementarity between interacting proteins, that was unfeasible with previous methods. We first tested the method with a large dataset of known protein complexes obtaining an overall area under the ROC curve of 0.76 in the blind recognition of binding sites and then applied it to investigate the features of the interaction between the Spike protein of SARS-Cov-2 and human cellular receptors. Our results indicate that SARS-CoV-2 uses a dual strategy: its spike protein could also interact with sialic acid receptors of the cells in the upper airways, in addition to the known interaction with Angiotensin-converting enzyme 2., Comment: 10 pages, 4 figures

Although the synaptic connections of the C. elegans connectome have been precisely mapped with detailed electron microscopy studies of nematode slices, their excitatory or inhibitory character is mostly unknown. This makes the C. elegans neural dynamics unpredictable, and limits our understanding of how specific sub-circuits work. The present study proposes a recurrent neural network model that reproduces known escape behaviours of C. elegans. To do this, our model uses the known information about the connectome, and makes guesses on the excitatory or inhibitory character of the synapses, which are iteratively updated until the model is able to reproduce the known behaviours. Specifically, we apply this model-based approach to study the neuronal sub-circuits involved in the association of aversive stimuli with escape responses. To form an escape response dataset that allows us to adjust our model parameters, we performed a meta-study on the C. elegans stimulus–response behaviours reported in literature, focusing on robust escape reactions triggered by aversive stimuli. Given a wide sample of all possible parameter sets that satisfy the behavioural constraints of the dataset, we find that more than 75% of the synaptic connections reach a univocal optimal assignment of the inhibitory or excitatory character. To validate our model, we show that in the few cases where the excitatory/inhibitory character is already known, our retrieved optimum in synaptic characters matches the results reported in literature. Finally, we assess the accuracy of this approach by applying it on recurrent neural networks that have the same connectivity structure of C. elegans but random inhibitory or excitatory character. These findings confirm the predictive power of the proposed method.

Many models explain the evolution of signalling in repeated stage games on social networks, differently in this study each signalling game evolves a communication strategy to transmit information a...

In a neural network, an autapse is a particular kind of synapse that links a neuron onto itself. Autapses are almost always not allowed neither in artificial nor in biological neural networks. Moreover, redundant or similar stored states tend to interact destructively. This paper shows how autapses together with stable state redundancy can improve the storage capacity of a recurrent neural network. Recent research shows how, in an N-node Hopfield neural network with autapses, the number of stored patterns (P) is not limited to the well known bound 0.14 N , as it is for networks without autapses. More precisely, it describes how, as the number of stored patterns increases well over the 0.14 N threshold, for P much greater than N, the retrieval error asymptotically approaches a value below the unit. Consequently, the reduction of retrieval errors allows a number of stored memories, which largely exceeds what was previously considered possible. Unfortunately, soon after, new results showed that, in the thermodynamic limit, given a network with autapses in this high-storage regime, the basin of attraction of the stored memories shrinks to a single state. This means that, for each stable state associated with a stored memory, even a single bit error in the initial pattern would lead the system to a stationary state associated with a different memory state. This thus limits the potential use of this kind of Hopfield network as an associative memory. This paper presents a strategy to overcome this limitation by improving the error correcting characteristics of the Hopfield neural network. The proposed strategy allows us to form what we call an absorbing-neighborhood of state surrounding each stored memory. An absorbing-neighborhood is a set defined by a Hamming distance surrounding a network state, which is an absorbing because, in the long-time limit, states inside it are absorbed by stable states in the set. We show that this strategy allows the network to store an exponential number of memory patterns, each surrounded with an absorbing-neighborhood with an exponentially growing size.

A heuristic algorithm for partitioning of VLSI circuits which attempts to minimize the number of branches cut between partitions is presented in this thesis. The algorithm uses a reduced connectivity matrix and the concept of cut index. The first phase of the algorithm, which is called the partitioning phase, finds the cut lines of the graph, and the second phase of the algorithm, which is called the optimization phase, optimize the branches cut by the partitions. The required computation time is shown to be bounded by O( n2 ), where n is the number of nodes in a graph. The proposed algorithm is currently implemented using X ·Window System. The program is called Reduced Connectivity Matrix Partitioning, abbreviated as rcmp. A universal netlist format used in the Tcmp allows it to interface to most existing VLSI CAD tools. Experimental results show that the proposed algorithm yields optimal solutions in most cases and near optimal solutions in some cases.

Multi-Vdd is an effective method to reduce both leakage and dynamic power. A key challenge in a multi-Vdd design is to control the complexity of the power-supply system and limit the demand for level shifters. This can be tackled by grouping cells of different supply voltages into a small number of voltage islands. Recently, an elegant algorithm was proposed for generating voltage islands that balance the power-versus-design-cost tradeoff under performance requirement, according to the placement proximity of the critical cells. One prerequisite of this algorithm is an initial voltage assignment at the standard-cell level that meets timing. In this article, we present a novel method to produce quality voltage assignment which not only meets timing but also forms good proximity of the critical cells to provide a smooth input to the aforementioned voltage island generation. Our algorithm is based on effective delay budgeting and efficient computation of physical proximity by Voronoi diagram. Our extensive experiments on real industrial designs show that our algorithm leads to 25%--75% improvement in the voltage island generation in terms of the number of voltage islands generated, with computation time only linear to design size.

Constraint Satisfaction Problems (CSPs) are the formalization of a large range of problems that emerge from computer science. The solving methodology described here is based on Naming Games (NGs). NGs were introduced to represent N agents that have to bootstrap an agreement on a name to give to an object (i.e., a word). In this paper we focus on solving both Fuzzy NGs and Fuzzy Distributed CSPs (Fuzzy DCSPs) with an algorithm inspired by NGs. In this framework, each proposed solution is associated with a preference represented as a fuzzy score. We want the agents to find the solution, which is associated with the highest preference value among all solutions. The two main features that distinguish this methodology from classical Fuzzy DCSPs algorithms are that i) the system can react to small instance changes, and ii) the fact the algorithm does not require a pre-agreed agent/variable ordering.

We address how the structure of a social communication system affects language coordination. The naming game is an abstraction of lexical acquisition dynamics, in which N agents try to find an agreement on the names to give to objects. Most results on naming games are specific to certain communication network topologies. We present two important results that are general to any graph topology: the first proves that under certain topologies the system always converges to a name-object agreement; the second proves that if these conditions are not met the system may end up in a state in which sub-networks with different competing object-name associations coexist.

In this paper we focus on solving Fuzzy Distributes Constraint Satisfaction Problems (Fuzzy DCSPs) with an algorithm for Naming Games (NGs): each word on which the agents have to agree on is associated with a preference represented as a fuzzy score. The solution is the agreed word associated with the highest preference value. The two main features that distinguish this methodology from Fuzzy DCSPs methods are that the system can react to small instance changes and and it does not require pre-agreed agent/variable ordering.

In constraint satisfaction problems (CSP) we consider N variables x 1 ,x 2 , ...x N , their definition domains D 1 ,D 2 , ...,D N and a set of constraints on the values of these variables; solving the CSP means finding a particular value for the variables that satisfies the constraints. In the distributed CSP (DCSP) as defined by Makoto Yokoo [1], the variables of the CSP are distributed among the agents. These agents are able to communicate between themselves and know all the constraint predicates relevant to their variable. The agents through interaction find the appropriate values to solve the CSP. The naming game describes a set of problems in which a number N of agents bootstrap a commonly agreed name for an object. Each naming game is defined by an interaction protocol/algorithm. An important aspect of the naming game is the hierarchy-free agent architecture. For other references on the naming game see the work of Steels [3] and Baronchelli et al. [2].

The authors present a new algorithm for partitioning VLSI circuits. The algorithm is based on the formulation of a reduced connectivity matrix. The partitioning is performed on this matrix using the concept of cut index. The algorithm heuristically minimizes the number of branches cut between partitions with user control over the size of and the number of partitions. The time complexity of the algorithm has been analytically and experimentally shown to be of order O(n/sup 2/). The algorithm was implemented using the C programming language and the X-windows environment, and has graphical and netlist input/output interfaces. >

The breadth-first manipulation technique has proven effective in dealing with very large sized BDDs. However, until now the lack of dynamic variable reordering has remained an obstacle in its acceptance. The goal of the work is to provide efficient techniques to address this issue. After identifying the problems with implementing variable swapping (the core operation in dynamic reordering) in breadth-first based packages, the authors propose techniques to handle the computational and memory overheads. They feel that combining dynamic reordering with the powerful manipulation algorithms of a breadth-first based scheme can significantly enhance the performance of BDD based algorithms. The efficiency of the proposed techniques is demonstrated on a range of examples.

This paper is concerned with approximate delay computation algorithms for combinational circuits. As a result of intensive research in the early 90's efficient tools exist which can analyze circuits of thousands of gates in a few minutes or even in seconds for many cases. However, the computation time of these tools is not so predictable since the internal engine of the analysis is either a SAT solver or a modified ATPG algorithm, both of which are just heuristic algorithms for an NP-complete problem. Although they are highly tuned for CAD applications, there exists a class of problem instances which exhibits the worst-case exponential CPU time behavior. In the context of timing analysis, circuits with a high amount of reconvergence, e.g. C6288 of the ISCAS benchmark suite, are known to be difficult to analyze under sophisticated delay models even with state-of-the-art techniques. To make timing analysis of such corner case circuits feasible we propose an approximate computation scheme to the timing analysis problem as an extension to the exact analysis method proposed previously. Sensitization conditions are conservatively approximated in a selective fashion so that the size of SAT problems solved during analysis is controlled. Experimental results show that the approximation technique is effective in reducing the total analysis time without losing accuracy for the case where the exact approach takes much time or cannot complete.