Characterization and computation of ancestors in reaction systems
- PDF / 1,623,486 Bytes
- 16 Pages / 595.276 x 790.866 pts Page_size
- 99 Downloads / 170 Views
FOCUS
Characterization and computation of ancestors in reaction systems Roberto Barbuti1 · Anna Bernasconi1 · Roberta Gori1
· Paolo Milazzo1
© The Author(s) 2020
Abstract In reaction systems, preimages and nth ancestors are sets of reactants leading to the production of a target set of products in either 1 or n steps, respectively. Many computational problems on preimages and ancestors, such as finding all minimumcardinality nth ancestors, computing their size or counting them, are intractable. In this paper, we characterize all nth ancestors using a Boolean formula that can be computed in polynomial time. Once simplified, this formula can be exploited to easily solve all preimage and ancestor problems. This allows us to directly relate the difficulty of ancestor problems to the cost of the simplification so that new insights into computational complexity investigations can be achieved. In particular, we focus on two problems: (i) deciding whether a preimage/nth ancestor exists and (ii) finding a preimage/nth ancestor of minimal size. Our approach is constructive, it aims at finding classes of reactions systems for which the ancestor problems can be solved in polynomial time, in exact or approximate way. Keywords Reaction systems · Ancestor computation · Computational complexity · Causality relations
1 Introduction Inspired by natural phenomena, many new computational formalisms have been introduced to model different aspects of biology. Basic chemical reactions inspired the reaction systems, a qualitative modeling formalism introduced by Brijder et al. (2011), Ehrenfeucht and Rozenberg (2007). It is based on two opposite mechanisms, namely facilitation and inhibition. Facilitation means that a reaction can occur only if all its reactants are present, while inhibition means that the reaction cannot occur if any of its inhibitors is present. A rewrite rule of a reaction system (called reaction) is hence a triple (R, I , P), where R, I and P are sets of objects representing reactants, inhibitors and products, respectively, of the modeled chemical reaction. A reaction system is represented by a set of reactions having such a form, together with a (finite) support set S containing all of the objects that can appear in a reaction. The state of a reaction system consists of a finite set of objects describing the biological entities that are present in the real system being modeled. The presence of an object in the state expresses the fact that the corresponding Communicated by Miguel A. Vega-Rodriguez.
B 1
Roberta Gori [email protected]
biological entity, in the real system being modeled, is present in a number of copies as high as needed. This is the threshold supply assumption and characterizes reaction systems. A reaction system evolves by means of the application of its reactions. The threshold supply assumption ensures that different reactions never compete for their reactants, and hence, all the applicable reactions in a step are always applied. The application of a set of reactions results in the introducti
Data Loading...
