On the Complexity of Inference and Completion of Boolean Networks from Given Singleton Attractors

Hao JIANG  Takeyuki TAMURA  Wai-Ki CHING  Tatsuya AKUTSU  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E96-A   No.11   pp.2265-2274
Publication Date: 2013/11/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E96.A.2265
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: General Fundamentals and Boundaries
Boolean network,  singleton attractor,  network completion,  another solution problem,  

Full Text: PDF(1MB)>>
Buy this Article

In this paper, we consider the problem of inferring a Boolean network (BN) from a given set of singleton attractors, where it is required that the resulting BN has the same set of singleton attractors as the given one. We show that the problem can be solved in linear time if the number of singleton attractors is at most two and each Boolean function is restricted to be a conjunction or disjunction of literals. We also show that the problem can be solved in polynomial time if more general Boolean functions can be used. In addition to the inference problem, we study two network completion problems from a given set of singleton attractors: adding the minimum number of edges to a given network, and determining Boolean functions to all nodes when only network structure of a BN is given. In particular, we show that the latter problem cannot be solved in polynomial time unless P=NP, by means of a polynomial-time Turing reduction from the complement of the another solution problem for the Boolean satisfiability problem.