On anti-occurrence of subsets of transitions in Petri net-based models of complex biological systems. (December 2022)

• Record Type: Journal Article
• Authors: Gutowska, Kaja; Formanowicz, Piotr
• Is Part Of: Bio systems. Volume 222(2022)
• Publication Date: 2022-12
• Subjects: Petri nets -- Biological systems -- Sets of transitions -- Computational complexity -- Exact algorithm; Biological systems -- Periodicals; Biology -- Periodicals; Biology -- Periodicals; Evolution -- Periodicals; Biologie -- Périodiques; Évolution -- Périodiques; 570
• DOI: 10.1016/j.biosystems.2022.104793
• Languages: English
• ISSNs: 0303-2647

Abstract

Abstract: Background and Objective: In the last two decades there can be observed a rapid development of systems biology. The basis of systems methods is a formal model of an analyzed system. It can be created in a language of some branch of mathematics and recently Petri net-based biological models seem to be especially promising since they have a great expressive power. One of the methods of analysis of such models is based on transition invariants. They correspond to some subprocesses which do not change a state of the modeled biological system. During such analysis, a need arose to study the subsets of transitions, what leads to interesting combinatorial problems — which have been considered in theory and practice. Methods & Results: Two problems of anti-occurrence were considered. These problems concern a set of transitions which is not a subset of any of t-invariant supports or is not a subset of t-invariant supports from some collection of such supports. They are defined in a formal way, their computational complexity is analyzed and an exact algorithm is provided for one of them. Conclusions: A comprehensive analysis of complex biological phenomena is challenging. Finding elementary processes that do not affect subprocesses belonging to the entire studied biological system may be necessary for a complete understanding of such a model and it is possible thanks to the proposed algorithm. Highlights: The computational complexity of anti-occurrence problems in Petri net-based models. Exact algorithm for anti-occurrence sets finding. Relations between t-invariants as a key stage in an analysis of the biological models. Elementary processes not affecting subprocesses belonging to the studied system. A comprehensive analysis of complex biological phenomena based on transitions subsets.