Finding Attractors in Synchronous Multiple-Valued Networks Using SAT-based Bounded Model Checking
2012 (English)In: Journal of Multiple-Valued Logic and Soft Computing, ISSN 1542-3980, E-ISSN 1542-3999, Vol. 19, no 1-3, 109-131 p.Article in journal (Refereed) Published
Synchronous multiple-valued networks are a discrete-space discrete-time model of the gene regulatory network of living cells. In this model, cell types are represented by the cycles in the state transition graph of a network, called attractors. When the effect of a disease or a mutation on a cell is studied, attractors have to be re-computed each time a fault is injected in the model. This motivates research on algorithms for finding attractors. Existing decision diagram-based approaches have limited capacity due to the excessive memory requirements of decision diagrams. Simulation-based approaches can be applied to larger networks, however, they are incomplete. We present an algorithm for finding attractors which uses a SAT-based bounded model checking. Our model checking approach exploits the deterministic nature of the network model to reduce runtime. Although the idea of applying model checking to the analysis of gene regulatory networks is not new, to our best knowledge, we are the first to use it for computing all attractors in a model. The efficiency of the presented algorithm is evaluated by analyzing 7 networks models of real biological processes as well as 35.000 randomly generated 4-valued networks. The results show that our approach has a potential to handle an order of magnitude larger models than currently possible.
Place, publisher, year, edition, pages
Old City Publishing, 2012. Vol. 19, no 1-3, 109-131 p.
Multiple-Valued Network, SAT, Model Checking, attractor
Research subject SRA - ICT
IdentifiersURN: urn:nbn:se:kth:diva-107495ISI: 000305440000009ScopusID: 2-s2.0-84864069529OAI: oai:DiVA.org:kth-107495DiVA: diva2:576302
QC 201301092013-01-102012-12-122015-11-20Bibliographically approved