Search

Real-world systems interact with one another via dependency connectivities. Dependency connectivities make systems less robust because failures may spread iteratively among systems via dependency links. Most previous studies have assumed that two nodes connected by a dependency link are strongly dependent on each other; that is, if one node fails, its dependent partner would also immediately fail. However, in many real scenarios, nodes from different networks may be weakly dependent, and links may fail instead of nodes. How interdependent networks with weak dependency react to link failures remains unknown. In this paper, we build a model of fully interdependent networks with weak dependency and define a parameter α in order to describe the node-coupling strength. If a node fails, its dependent partner has a probability of failing of 1−α. Then, we develop an analytical tool for analyzing the robustness of interdependent networks with weak dependency under link failures, with which we can accurately predict the system robustness when 1−p fractions of links are randomly removed. We find that as the node coupling strength increases, interdependent networks show a discontinuous phase transition when α<αc and a continuous phase transition when α>αc. Compared to site percolation with nodes being attacked, the crossover points αc are larger in the bond percolation with links being attacked. This finding can give us some suggestions for designing and protecting systems in which link failures can happen.

Over the last few years, a new methodology to address the P versus NP problem has been developed, based on searching for borderlines between the nonefficiency of computing models (only problems in class P can be solved in polynomial time) and the presumed efficiency (ability to solve NP-complete problems in polynomial time). These borderlines can be seen as frontiers of efficiency, which are crucial in this methodology. “Translating,” in some sense, an efficient solution in a presumably efficient model to an efficient solution in a nonefficient model would give an affirmative answer to problem P versus NP. In the framework of Membrane Computing, the key of this approach is to detect the syntactic or semantic ingredients that are needed to pass from a nonefficient class of membrane systems to a presumably efficient one. This paper deals with tissue P systems with communication rules of type symport/antiport allowing the evolution of the objects triggering the rules. In previous works, frontiers of efficiency were found in these kinds of membrane systems both with division rules and with separation rules. However, since they were not optimal, it is interesting to refine these frontiers. In this work, optimal frontiers of the efficiency are obtained in terms of the total number of objects involved in the communication rules used for that kind of membrane systems. These optimizations could be easier to translate, if possible, to efficient solutions in a nonefficient model.

A word is a finite sequence of symbols. Parikh matrix of a word is an upper triangular matrix with ones in the main diagonal and nonnegative integers above the main diagonal which are counts of certain scattered subwords in the word. On the other hand, a picture array, which is a rectangular arrangement of symbols, is an extension of the notion of a word to two dimensions. Parikh matrices associated with a picture array have been introduced, and their properties have been studied. Here, we obtain certain algebraic properties of Parikh matrices of binary picture arrays based on the notions of power, fairness, and a restricted shuffle operator extending the corresponding notions studied in the case of words. We also obtain properties of Parikh matrices of arrays formed by certain geometric operations.

Tissue P systems with evolutional communication (symport/antiport) rules are computational models inspired by biochemical systems consisting of multiple individuals living and cooperating in a certain environment, where objects can be modified when moving from one region to another region. In this work, cell separation, inspired from membrane fission process, is introduced in the framework of tissue P systems with evolutional communication rules. The computational complexity of this kind of P systems is investigated. It is proved that only problems in class P can be efficiently solved by tissue P systems with cell separation with evolutional communication rules of length at most (n,1), for each natural number n≥1. In the case where that length is upper bounded by (3,2), a polynomial time solution to the SAT problem is provided, hence, assuming that P≠NP a new boundary between tractability and NP-hardness on the basis of the length of evolutional communication rules is provided. Finally, a new simulator for tissue P systems with evolutional communication rules is designed and is used to check the correctness of the solution to the SAT problem.

DNA strand displacement technology performs well in sensing and programming DNA segments. In this work, we construct DNA molecular systems based on DNA strand displacement performing computation of logic gates. Specifically, a class of so-called "DNA neurons" are achieved, in which a "smart" way inspired by biological neurons encoding information is developed to encode and deliver information using DNA molecules. The "DNA neuron" is bistable, that is, it can sense DNA molecules as input signals, and release "negative" or "positive" signals DNA molecules. We design intelligent DNA molecular systems that are constructed by cascading some particularly organized "DNA neurons", which could perform logic computation, including AND, OR, XOR logic gates, automatically. Both simulation results using visual DSD (DNA strand displacement) software and experimental results are obtained, which shows that the proposed systems can detect DNA signals with high sensitivity and accretion; moreover, the systems can process input signals automatically with complex nonlinear logic. The method proposed in this work may provide a new way to construct a sensitive molecular signal detection system with neurons spiking behavior in vitro, and can be used to develop intelligent molecular processing systems in vivo.

Non-small cell lung cancer (NSCLC) has two major subtypes: adenocarcinoma (AC) and squamous cell carcinoma (SCC). The diagnosis and treatment of NSCLC are hindered by the limited knowledge about the pathogenesis mechanisms of subtypes of NSCLC. It is necessary to research the molecular mechanisms related with AC and SCC. In this work, we improved the logic analysis algorithm to mine the sufficient and necessary conditions for the presence states (presence or absence) of phenotypes. We applied our method to AC and SCC specimens, and identified [Formula: see text] lower and [Formula: see text] higher logic relationships between genes and two subtypes of NSCLC. The discovered relationships were independent of specimens selected, and their significance was validated by statistic test. Compared with the two earlier methods (the non-negative matrix factorization method and the relevance analysis method), the current method outperformed these methods in the recall rate and classification accuracy on NSCLC and normal specimens. We obtained [Formula: see text] biomarkers. Among [Formula: see text] biomarkers, [Formula: see text] genes have been used to distinguish AC from SCC in practice, and other six genes were newly discovered biomarkers for distinguishing subtypes. Furthermore, NKX2-1 has been considered as a molecular target for the targeted therapy of AC, and [Formula: see text] other genes may be novel molecular targets. By gene ontology analysis, we found that two biological processes ('epidermis development' and 'cell adhesion') were closely related with the tumorigenesis of subtypes of NSCLC. More generally, the current method could be extended to other complex diseases for distinguishing subtypes and detecting the molecular targets for targeted therapy.

Evolutionary algorithms have been used to solve a variety of many-objective optimization problems, where these problems contain more than three conflicting objectives. Most existing evolutionary algorithms have shown to perform well on many-objective optimization problems with regular Pareto optimal fronts, their performance, however, will often considerably deteriorate on those whose Pareto optimal fronts are irregular, e.g., discontinuous, degenerated and convex. To address this issue, in this paper, we propose a region division based many-objective optimization evolutionary algorithm, termed RdEA, where a region division approach is suggested to maintain diversity of population for many-objective optimization (especially for problems with irregular Pareto fronts). In the proposed region division based diversity maintaining approach, the geometric information of Pareto optimal fronts is taken into account by using the non-dominated solutions found at each generation, which helps to solve the problems with irregular Pareto optimal fronts better. The proposed RdEA is compared with five state-of-the-art many-objective evolutionary algorithms on 16 test problems from two test suites DTLZ and WFG and a real-world optimization problem. Experimental results on these problems demonstrate that the competitiveness of the proposed algorithm in solving many-objective optimization problems, especially for those with irregular Pareto optimal fronts. [ABSTRACT FROM AUTHOR]

Numerical P systems are a class of P systems inspired both from the structure of living cells and from economics. In this work, we further investigate the generative capacity of numerical P systems as language generators. The families of languages generated by non-enzymatic, by enzymatic, and by purely enzymatic (all programs are enzymatic) numerical P systems working in the sequential mode are compared with the language families in the Chomsky hierarchy. Especially, a characterization of recursively enumerable languages is obtained by using purely enzymatic numerical P systems working in the sequential mode. [ABSTRACT FROM AUTHOR]

A control strategy on the computations in a one-catalyst P system is provided: the rules are assumed "colored" and in each step only rules of the same "color" are used. Such control leads to Turing universality for one-catalyst P systems with one membrane. Turing universality is also reached for purely catalytic P systems with two catalysts, and for purely catalytic P systems with only one catalyst and cooperating rules working in the so-called terminal mode. [ABSTRACT FROM AUTHOR]

Tissue P systems are a class of distributed parallel computing devices inspired by biochemical interactions between cells in a tissue-like arrangement, where objects can be exchanged by means of communication channels. In this work, inspired by the biological facts that the movement of most objects through communication channels is controlled by proteins and proteins can move through lipid bilayers between cells (if these cells are fused), we present a new class of variant tissue P systems, called tissue P systems with protein on cells, where multisets of objects (maybe empty), together with proteins between cells are exchanged. The computational power of such P systems is studied. Specifically, an efficient (uniform) solution to the SAT problem by using such P systems with cell division is presented. We also prove that any Turing computable set of numbers can be generated by a tissue P system with protein on cells. Both of these two results are obtained by such P systems with communication rules of length at most 4 (the length of a communication rule is the total number of objects and proteins involved in that rule). [ABSTRACT FROM AUTHOR]

Inspired by mitosis process and membrane fission processes, cell-like P systems with symport/antiport rules and membrane division rules or membrane separation rules have been introduced, respectively. These computation systems have two key features: the ability to have infinite copies of some objects (within an active environment) and to generate an exponential workspace in polynomial time. In this work, we extend the P-Lingua framework for simulating that kind of P systems taking into account these two features. Consequently, a new simulator has been developed and included in pLinguaCore library. The functioning of the simulator has been checked by simulating efficient solutions to SAT problem using a family of cell-like P systems with symport/antiport rules and membrane division rules or membrane separation rules. The corresponding MeCoSim based application is also provided. [ABSTRACT FROM AUTHOR]

P systems are a class of computational models inspired by the structure and the functioning of a living cell. In the semantics of P systems, there exists a global clock, which marks the time for the system, and the execution time of each rule takes exactly one time unit. However, in living cells, the execution time of different biochemical reactions is dependent on many uncontrollable factors, and it is hard to know precisely the specific execution time of a reaction. In this work, with this biological inspiration, we consider the class of P systems with active membranes that are "robust" against the execution time of rules. Specifically, we give a time-free uniform solution to the SAT problem using P systems with active membranes, where the constructed P system can solve a family of instances with an arbitrarily given size, and the execution time of the involved rules has no influence on the correctness of the solution. We also prove that any Turing computable set of numbers can be generated by a time-free P system with active membranes in the sense that the set of numbers generated by the given P system with active membranes does not depend on the execution time of rules. [ABSTRACT FROM AUTHOR]

Spiking neural P systems (SN P systems) are a class of distributed parallel computing devices inspired by spiking neurons, where the spiking rules are usually used in a sequential way (an applicable rule is applied one time at a step) or an exhaustive way (an applicable rule is applied as many times as possible at a step). In this letter, we consider a generalized way of using spiking rules by "combining" the sequential way and the exhaustive way: if a rule is used at some step, then at that step, it can be applied any possible number of times, nondeterministically chosen. The computational power of SN P systems with a generalized use of rules is investigated. Specifically, we prove that SN P systems with a generalized use of rules consisting of one neuron can characterize finite sets of numbers. If the systems consist of two neurons, then the computational power of such systems can be greatly improved, but not beyond generating semilinear sets of numbers. SN P systems with a generalized use of rules consisting of three neurons are proved to generate at least a nonsemilinear set of numbers. In the case of allowing enough neurons, SN P systems with a generalized use of rules are computationally complete. These results show that the number of neurons is crucial forSNP systems with a generalized use of rules to achieve a desired computational power. [ABSTRACT FROM AUTHOR]