Change search
ReferencesLink to record
Permanent link

Direct link
Finding Attractors in Synchronous Multiple-Valued Networks Using SAT-based Bounded Model Checking
KTH, School of Information and Communication Technology (ICT), Electronic Systems.ORCID iD: 0000-0001-7382-9408
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)
Abstract [en]

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
Keyword [en]
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
URN: urn:nbn:se:kth:diva-32132DOI: 10.1109/ISMVL.2010.35ISI: 000287530100026ScopusID: 2-s2.0-77955333667ISBN: 978-0-7695-4024-5OAI: diva2:409312
40th International Symposium on Multiple-Valued Logic (ISMVL) Barcelona, SPAIN, MAY 26-28, 2010
QC 20110407Available from: 2011-04-07 Created: 2011-04-07 Last updated: 2011-04-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Dubrova, Elena
By organisation
Electronic Systems
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 21 hits
ReferencesLink to record
Permanent link

Direct link