×

SAT-based algorithm for finding cycles in a Boolean network. (Chinese. English summary) Zbl 1349.68101

Summary: A cycle which is a steady state in Boolean network state transition is important in model checking, genetic regulatory networks and reachability analysis. Obtaining all the cycles in Boolean network state transition is an NP complete problem. In this paper, we propose an algorithm for solving all the cycles less than or equal to the assigned step length based on all-solution Boolean satisfiability (SAT) algorithm. By extending the state transition function of a Boolean network and the property of cycles, this algorithm creates a problem set in conjunctive normal form (CNF) and incorporates techniques such as conflict-driven clause learning (CDCL), non-chronological backtracking, blocking clause and variable classification to decrease computational complexity. Experiment result shows that this algorithm is efficient for solving the cycles. For large scale complex network that is hard to get all the cycles, this algorithm delivers more practical value.

MSC:

68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI