Finding Attractors in Synchronous Multiple-Valued Networks Using SAT-based Bounded Model Checking
2010 (English)In: 40TH IEEE INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC ISMVL 2010, Los Alamitos: IEEE COMPUTER SOC , 2010, 144-149 p.Conference paper (Refereed)
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
Los Alamitos: IEEE COMPUTER SOC , 2010. 144-149 p.
, International Symposium on Multiple-Valued Logic, ISSN 0195-623X
GENETIC REGULATORY NETWORKS; CELL-CYCLE; VALIDATION
Electrical Engineering, Electronic Engineering, Information Engineering
IdentifiersURN: urn:nbn:se:kth:diva-32132DOI: 10.1109/ISMVL.2010.35ISI: 000287530100026ScopusID: 2-s2.0-77955333667ISBN: 978-0-7695-4024-5OAI: oai:DiVA.org:kth-32132DiVA: diva2:409312
40th International Symposium on Multiple-Valued Logic (ISMVL) Barcelona, SPAIN, MAY 26-28, 2010
QC 201104072011-04-072011-04-072011-04-07Bibliographically approved