Membrane fission: A computational complexity perspective

Membrane fission is a process by which a biological membrane is split into two new ones in the manner that the content of the initial membrane is separated and distributed between the new membranes. Inspired by this biological phenomenon, membrane separation rules were considered in membrane computing. In this work, we investigate cell‐like P systems with symport/antiport rules and membrane separation rules from a computational complexity perspective. Specifically, we establish a limit on the efficiency of such P systems which use communication rules of length at most two, and we prove the computational efficiency of this kind of models when using communication rules of length at most three. Hence, a sharp borderline between tractability and NP –hardness is provided in terms of the length of communication rules. © 2015 Wiley Periodicals, Inc. Complexity 21: 321–334, 2016     

Agent-based grid computing

The grid concept has recently emerged as a vision of future network based computing, by enabling seamless integration of computing systems and clusters, data storage, specialized networks and sophisticated analysis and visualization software. Intelligent agents can play an important role in helping achieve the grid vision. In this paper we propose a model for agent-based grid computing from the implementation point of view. Based on MAGE, a multi-agent framework, we present a reference implementation of this agent-based grid computing model called AGEGC. We believe that AGEGC will be a useful platform for research on agent-based grid computing.     

AN ADAPTIVE MEMBRANE ALGORITHM FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS

Membrane algorithms （MAs）, which inherit from P systems, constitute a new parallel and distribute framework for approximate computation. In the paper, a membrane algorithm is proposed with the improvement that the involved parameters can be adaptively chosen. In the algorithm, some membranes can evolve dynamically during the computing process to specify the values of the requested parameters. The new algorithm is tested on a well-known combinatorial optimization problem, the travelling salesman problem. The em-pirical evidence suggests that the proposed approach is efficient and reliable when dealing with 11 benchmark instances, particularly obtaining the best of the known solutions in eight instances. Compared with the genetic algorithm, simulated annealing algorithm, neural net-work and a fine-tuned non-adaptive membrane algorithm, our algorithm performs better than them. In practice, to design the airline network that minimize the total routing cost on the CAB data with twenty-five US cities, we can quickly obtain high quality solutions using our algorithm.     

An adaptive membrane algorithm for solving combinatorial optimization problems

Membrane algorithms (MAs), which inherit from P systems, constitute a new parallel and distribute framework for approximate computation. In the paper, a membrane algorithm is proposed with the improvement that the involved parameters can be adaptively chosen. In the algorithm, some membranes can evolve dynamically during the computing process to specify the values of the requested parameters. The new algorithm is tested on a well-known combinatorial optimization problem, the travelling salesman problem. The empirical evidence suggests that the proposed approach is efficient and reliable when dealing with 11 benchmark instances, particularly obtaining the best of the known solutions in eight instances. Compared with the genetic algorithm, simulated annealing algorithm, neural network and a fine-tuned non-adaptive membrane algorithm, our algorithm performs better than them. In practice, to design the airline network that minimize the total routing cost on the CAB data with twenty-five US cities, we can quickly obtain high quality solutions using our algorithm.     

Rank-deficient matrices as a computational tool

Rank-deficient matrices arise naturally in many applications. Detecting rank changes and computing parameter values for which a matrix has a prescribed (low) rank deficiency is a fundamental task in computing least squares and minimum norm solutions to systems of linear equations. We describe an approach that originates from numerical continuation and bifurcation theory but has a wider applicability. It uses only linear solves with a bordered extension of the rank-deficient matrix and the transpose of that extension. We discuss the basic methods and their application in fundamental problems such as minimization and in more advanced problems in non-linear analysis. We present extensive numerical evidence in instructive test cases as well as in chemical model (one-dimensional PDE) and a biological model (using the software package CONTENT for dynamical systems). © 1997 by John Wiley & Sons, Ltd.     

Multigrid transfers for nonsymmetric systems based on Schur complements and Galerkin projections

A framework is proposed for constructing algebraic multigrid transfer operators suitable for nonsymmetric positive definite linear systems. This framework follows a Schur complement perspective as this is suitable for both symmetric and nonsymmetric systems. In particular, a connection between algebraic multigrid and approximate block factorizations is explored. This connection demonstrates that the convergence rate of a two‐level model multigrid iteration is completely governed by how well the coarse discretization approximates a Schur complement operator. The new grid transfer algorithm is then based on computing a Schur complement but restricting the solution space of the corresponding grid transfers in a Galerkin‐style so that a far less expensive approximation is obtained. The final algorithm corresponds to a Richardson‐type iteration that is used to improve a simple initial prolongator or a simple initial restrictor. Numerical results are presented illustrating the performance of the resulting algebraic multigrid method on highly nonsymmetric systems. Copyright © 2013 John Wiley & Sons, Ltd.     

Membrane Computing to Enhance Time Efficiency of Minimum Dominating Set

Graph theory is widely used in numerous fields, such as, engineering, physics, social and biological sciences; linguistics etc. The minimum dominating set (MDS) problem is one of the main problems of algorithmic graph theory and has numerous applications especially in graph mining. Since it is NP-hard to solve the MDS problem approximately, much work has been dedicated to central and distributed approximation algorithms for restricted graph classes. In recent research exponential time \(O(k^{n})\) algorithms are used for some graph classes for solving the MDS problem. In the approach of using the algorithmic tile self-assembly model, the MDS problem has been solved in \(O(n^{2})\) steps. On the other hand, in the area of membrane computing, P systems introduce two levels of parallelism: every membrane works concurrently with other membranes,and, rules are applied in parallel in each membrane. This paper introduces an algorithm based on the parallelism feature of the P systems model for solving the MDS problem in linear time O(n).     

Array P systems with permitting features

The biologically inspired model, known as P system, has proved to be a general framework for investigating several problems related to computing in different fields. Two-dimensional picture array languages is one such area in which different kinds of P systems have been constructed for picture array generation. Incorporating the feature of permitting symbols in the rules, a new variety of array P system is constructed here for generating picture languages consisting of picture arrays. The advantage of this approach is that there is a reduction in the number of membranes used in the construction, in comparison to the existing array P system models.     

Transition Manifolds of Complex Metastable Systems

We consider complex dynamical systems showing metastable behavior, but no local separation of fast and slow time scales. The article raises the question of whether such systems exhibit a low-dimensional manifold supporting its effective dynamics. For answering this question, we aim at finding nonlinear coordinates, called reaction coordinates, such that the projection of the dynamics onto these coordinates preserves the dominant time scales of the dynamics. We show that, based on a specific reducibility property, the existence of good low-dimensional reaction coordinates preserving the dominant time scales is guaranteed. Based on this theoretical framework, we develop and test a novel numerical approach for computing good reaction coordinates. The proposed algorithmic approach is fully local and thus not prone to the curse of dimension with respect to the state space of the dynamics. Hence, it is a promising method for data-based model reduction of complex dynamical systems such as molecular dynamics.     

A weighted adaptive least-squares finite element method for the Poisson-Boltzmann equation

The finite element methodology has become a standard framework for approximating the solution to the Poisson-Boltzmann equation in many biological applications. In this article, we examine the numerical efficacy of least-squares finite element methods for the linearized form of the equations. In particular, we highlight the utility of a first-order form, noting optimality, control of the flux variables, and flexibility in the formulation, including the choice of elements. We explore the impact of weighting and the choice of elements on conditioning and adaptive refinement. In a series of numerical experiments, we compare the finite element methods when applied to the problem of computing the solvation free energy for realistic molecules of varying size.     

Dynamics of Poisson-Nernst-Planck Systems and Ionic Flows Through Ion Channels: A Review

Poisson-Nernst-Planck systems are basic models for electrodiffusion process, particularly, for ionic flows through ion channels embedded in cell membranes. In this article, we present a brief review on a geometric singular perturbation framework for analyzing the steady-state of a quasi-one-dimensional Poisson-Nernst-Planck model. The framework is based on the general geometric singular perturbed theory from nonlinear dynamical system theory and, most crucially, on the reveal of two specific structures of Poisson-Nernst-Planck systems. As a result of the geometric framework, one obtains a governing system–an algebraic system of equations that involves all physical quantities such as protein structures of membrane channels as well as boundary conditions, and hence, provides a complete platform for studying the interplay between protein structure and boundary conditions and effects on ionic flow properties. As an illustration, we will present concrete applications of the theory to several topics of biologically significant based on collaboration works with many excellent researchers.     

A general framework on the simulation-based optimization under fixed computing budget

In many real world problems, the design space is huge and the estimation of performance measure has to rely on simulation which is time-consuming. Hence, to find the optimal design in the design space based on the simulation output is not trivial. It is important to have a computing time allocation rule to decide how much effort to spend in sampling the design space, how many designs to sample, and how long to run for each design alternative within a given computing budget. In this paper, we propose a framework for making these allocation decisions. We use the problem of assemble-to-order (ATO) systems to demonstrate how this framework can be applied. The sample average approximation (SAA) method is chosen as the sampling method used in this application example. The numerical results show that this framework provides a good basis for allocation decisions.     

Random and stochastic disturbances on the input flow in chemostat models with wall growth

In this paper, we analyze a chemostat model with wall growth where the input flow is perturbed by two different stochastic processes: the well-known standard Wiener process, which leads into several drawbacks from the biological point of view, and a suitable Ornstein-Uhlenbeck process depending on some parameters which allow us to control the noise to be bounded inside some interval that can be fixed previously by practitioners. Thanks to this last approach, which has already proved to be very realistic when modeling other simplest chemostat models, it will be possible to prove the persistence and coexistence of the species in the model without needing the theory of random dynamical systems and pullback attractors needed when dealing with the Wiener process. This is an advantage since the theoretical framework in this paper is much less complicated and provides us much more information than the other.     

�����������Ĵ������г�����ϵͳ����վ�㳵����ƽ���о�

??Recently, big data, could computing and internet of things provide some new information technologies for organization and management of complex systems, and they have caused multifaceted changes on organization framework and operations mechanism of enterprises. Based on this, we first construct a new stochastic model for a big data driven large-scale bike-sharing system, which expresses the important role played by big data, and describes the operations mechanism of the large-scale bike-sharing system, and specifically, the rebalancing of bikes in various stations in terms of trucks. Then, we present a mean-field limit theory, which is applied to analyzing the big data driven large-scale bike-sharing system, including establishing a time-inhomogeneous queueing system by means of the mean field theory, and setting up the mean-field equations through the time-inhomogeneous queueing system; providing an empirical measure process by means of a nonlinear birth-death process, giving algorithms for computing the fixed point in terms of a segmented structural birth-death processes, and computing the average number of bikes in each station; and providing numerical examples to analyze how the steady average number of bikes in each station depends on some key parameters of the bike-sharing system. Using these results, this paper analyzes physical effect of big data on performance of the large-scale bike-sharing. Therefore, this paper gives a promising research direction of stochastic model in the study of large-scale bike-sharing systems.     

Accelerating the coarse time-stepper for a lattice Boltzmann model

The equation-free framework for multiscale computing is built around the central idea of a coarse time-stepper, which is an approximate time integrator for the macroscopic variables when only a microscopic simulator is available. In a previous paper, we studied the accuracy and stability of the coarse time-stepper when the microscopic simulator is a lattice Boltzmann model for one-dimensional diffusion. In this paper, we rely on these results to show how the coarse time-stepper can be accelerated using the recently proposed teleprojective method or the multistep state extrapolation method. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Numerical recovery strategies for parallel resilient Krylov linear solvers

As the computational power of high‐performance computing systems continues to increase by using a huge number of cores or specialized processing units, high‐performance computing applications are increasingly prone to faults. In this paper, we present a new class of numerical fault tolerance algorithms to cope with node crashes in parallel distributed environments. This new resilient scheme is designed at application level and does not require extra resources, that is, computational unit or computing time, when no fault occurs. In the framework of iterative methods for the solution of sparse linear systems, we present numerical algorithms to extract relevant information from available data after a fault, assuming a separate mechanism ensures the fault detection. After data extraction, a well‐chosen part of missing data is regenerated through interpolation strategies to constitute meaningful inputs to restart the iterative scheme. We have developed these methods, referred to as interpolation–restart techniques, for Krylov subspace linear solvers. After a fault, lost entries of the current iterate computed by the solver are interpolated to define a new initial guess to restart the Krylov method. A well‐suited initial guess is computed by using the entries of the faulty iterate available on surviving nodes. We present two interpolation policies that preserve key numerical properties of well‐known linear solvers, namely, the monotonic decrease of the A‐norm of the error of the conjugate gradient or the residual norm decrease of generalized minimal residual algorithm for solving. The qualitative numerical behavior of the resulting scheme has been validated with sequential simulations, when the number of faults and the amount of data losses are varied. Finally, the computational costs associated with the recovery mechanism have been evaluated through parallel experiments. Copyright © 2016 John Wiley & Sons, Ltd.     

基于DNA链置换与荧光标记的0-1规划问题的计算模型

DNA链置换技术和荧光标记是近年生物计算领域的新兴的方法,并且因为它们都有着操作简单的优势而成为DNA计算的常用方法.DNA自组装算法是以DNA分子作为数据存储和运算的一种新型计算模式.为了提高算法的特异性和检测的灵敏度,在自组装算法的基础上,首次将DNA链置换技术和荧光标记结合引入到自组装模型中,提出了一个解决0-1规划问题的DNA计算新模型.与以往DNA计算模型相比,该模型提高了运算的可靠性和准确性,而且可以逐步缩小解空间,降低运算的复杂度,同时也使检测的方法更加灵活,易于引入到其他自组装算法模型中.     

Computing approximate solutions for convex conic systems of constraints

We propose a way to reformulate a conic system of constraints as an optimization problem. When an appropriate interior-point method (ipm) is applied to the reformulation, the ipm iterates yield backward-approximate solutions, that is, solutions for nearby conic systems. In addition, once the number of ipm iterations passes a certain threshold, the ipm iterates yield forward-approximate solutions, that is, points close to an exact solution of the original conic system. The threshold is proportional to the reciprocal of distance to ill-posedness of the original conic system.?The condition numbers of the linear equations encountered when applying an ipm influence the computational cost at each iteration. We show that for the reformulation, the condition numbers of the linear equations are uniformly bounded both when computing reasonably-accurate backward-approximate solutions to arbitrary conic systems and when computing forward-approximate solutions to well-conditioned conic systems. Received: July 11, 1997 / Accepted: August 18, 1999?Published online March 15, 2000     

Set-based granular computing: A lattice model

Set-based granular computing plays an important role in human reasoning and problem solving. Its three key issues constitute information granulation, information granularity and granular operation. To address these issues, several methods have been developed in the literature, but no unified framework has been formulated for them, which could be inefficient to some extent. To facilitate further research on the topic, through consistently representing granular structures induced by information granulation, we introduce a concept of knowledge distance to differentiate any two granular structures. Based on the knowledge distance, we propose a unified framework for set-based granular computing, which is named a lattice model. Its application leads to desired answers to two key questions: (1) what is the essence of information granularity, and (2) how to perform granular operation. Through using the knowledge distance, a new axiomatic definition to information granularity, called generalized information granularity is developed and its corresponding lattice model is established, which reveal the essence of information granularity in set-based granular computing. Moreover, four operators are defined on granular structures, under which the algebraic structure of granular structures forms a complementary lattice. These operators can effectively accomplish composition, decomposition and transformation of granular structures. These results show that the knowledge distance and the lattice model are powerful mechanisms for studying set-based granular computing.     

A CSP Versus a Zonotope-Based Method for Solving Guard Set Intersection in Nonlinear Hybrid Reachability

Computing the reachable set of hybrid dynamical systems in a reliable and verified way is an important step when addressing verification or synthesis tasks. This issue is still challenging for uncertain nonlinear hybrid dynamical systems. We show in this paper how to combine a method for computing continuous transitions via interval Taylor methods and a method for computing the geometrical intersection of a flowpipe with guard sets, to build an interval method for reachability computation that can be used with truly nonlinear hybrid systems. Our method for flowpipe guard set intersection has two variants. The first one relies on interval constraint propagation for solving a constraint satisfaction problem and applies in the general case. The second one computes the intersection of a zonotope and a hyperplane and applies only when the guard sets are linear. The performance of our method is illustrated on examples involving typical hybrid systems.