Downloads: 102

Files in This Item:
File Description SizeFormat 
transfun.E98.A.384.pdf1.09 MBAdobe PDFView/Open
Title: A Fixed-Parameter Algorithm for Detecting a Singleton Attractor in an AND/OR Boolean Network with Bounded Treewidth
Authors: CHANG, Chia-Jung
TAMURA, Takeyuki  kyouindb  KAKEN_id  orcid (unconfirmed)
CHAO, Kun-Mao
AKUTSU, Tatsuya  kyouindb  KAKEN_id  orcid (unconfirmed)
Author's alias: 田村, 武幸
Keywords: Boolean network
partial k-tree
fixed-parameter algorithm
Issue Date: 1-Jan-2015
Publisher: IEICE
Journal title: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Volume: E98.A
Issue: 1
Start page: 384
End page: 390
Abstract: The Boolean network can be used as a mathematical model for gene regulatory networks. An attractor, which is a state of a Boolean network repeating itself periodically, can represent a stable stage of a gene regulatory network. It is known that the problem of finding an attractor of the shortest period is NP-hard. In this article, we give a fixed-parameter algorithm for detecting a singleton attractor (SA) for a Boolean network that has only AND and OR Boolean functions of literals and has bounded treewidth k. The algorithm is further extended to detect an SA for a constant-depth nested canalyzing Boolean network with bounded treewidth. We also prove the fixed-parameter intractability of the detection of an SA for a general Boolean network with bounded treewidth.
Rights: © 2015 The Institute of Electronics, Information and Communication Engineers.
DOI(Published Version): 10.1587/transfun.E98.A.384
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks

Export Format: 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.