File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Control of Boolean networks: Hardness results and algorithms for tree structured networks

TitleControl of Boolean networks: Hardness results and algorithms for tree structured networks
Authors
KeywordsBoolean network
Control
Genetic network
NP-hard
Systems biology
Issue Date2007
PublisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/yjtbi
Citation
Journal Of Theoretical Biology, 2007, v. 244 n. 4, p. 670-679 How to Cite?
AbstractFinding control strategies of cells is a challenging and important problem in the post-genomic era. This paper considers theoretical aspects of the control problem using the Boolean network (BN), which is a simplified model of genetic networks. It is shown that finding a control strategy leading to the desired global state is computationally intractable (NP-hard) in general. Furthermore, this hardness result is extended for BNs with considerably restricted network structures. These results justify existing exponential time algorithms for finding control strategies for probabilistic Boolean networks (PBNs). On the other hand, this paper shows that the control problem can be solved in polynomial time if the network has a tree structure. Then, this algorithm is extended for the case where the network has a few loops and the number of time steps is small. Though this paper focuses on theoretical aspects, biological implications of the theoretical results are also discussed. © 2006 Elsevier Ltd. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/75321
ISSN
2023 Impact Factor: 1.9
2023 SCImago Journal Rankings: 0.553
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorAkutsu, Ten_HK
dc.contributor.authorHayashida, Men_HK
dc.contributor.authorChing, WKen_HK
dc.contributor.authorNg, MKen_HK
dc.date.accessioned2010-09-06T07:10:01Z-
dc.date.available2010-09-06T07:10:01Z-
dc.date.issued2007en_HK
dc.identifier.citationJournal Of Theoretical Biology, 2007, v. 244 n. 4, p. 670-679en_HK
dc.identifier.issn0022-5193en_HK
dc.identifier.urihttp://hdl.handle.net/10722/75321-
dc.description.abstractFinding control strategies of cells is a challenging and important problem in the post-genomic era. This paper considers theoretical aspects of the control problem using the Boolean network (BN), which is a simplified model of genetic networks. It is shown that finding a control strategy leading to the desired global state is computationally intractable (NP-hard) in general. Furthermore, this hardness result is extended for BNs with considerably restricted network structures. These results justify existing exponential time algorithms for finding control strategies for probabilistic Boolean networks (PBNs). On the other hand, this paper shows that the control problem can be solved in polynomial time if the network has a tree structure. Then, this algorithm is extended for the case where the network has a few loops and the number of time steps is small. Though this paper focuses on theoretical aspects, biological implications of the theoretical results are also discussed. © 2006 Elsevier Ltd. All rights reserved.en_HK
dc.languageengen_HK
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/yjtbien_HK
dc.relation.ispartofJournal of Theoretical Biologyen_HK
dc.subjectBoolean network-
dc.subjectControl-
dc.subjectGenetic network-
dc.subjectNP-hard-
dc.subjectSystems biology-
dc.subject.meshAlgorithmsen_HK
dc.subject.meshAnimalsen_HK
dc.subject.meshCell Physiological Phenomenaen_HK
dc.subject.meshGene Expression Regulationen_HK
dc.subject.meshLogicen_HK
dc.subject.meshModels, Geneticen_HK
dc.subject.meshProbabilityen_HK
dc.subject.meshSystems Biologyen_HK
dc.subject.meshSystems Theoryen_HK
dc.titleControl of Boolean networks: Hardness results and algorithms for tree structured networksen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0022-5193&volume=244&spage=670&epage=679&date=2007&atitle=Control+of+Boolean+Networks:+Hardness+Results+and+Algorithms+for+Tree+Structured+Networksen_HK
dc.identifier.emailChing, WK:wching@hku.hken_HK
dc.identifier.authorityChing, WK=rp00679en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.jtbi.2006.09.023en_HK
dc.identifier.pmid17069859-
dc.identifier.scopuseid_2-s2.0-33846424927en_HK
dc.identifier.hkuros125840en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33846424927&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume244en_HK
dc.identifier.issue4en_HK
dc.identifier.spage670en_HK
dc.identifier.epage679en_HK
dc.identifier.eissn1095-8541-
dc.identifier.isiWOS:000244584300010-
dc.publisher.placeUnited Kingdomen_HK
dc.identifier.scopusauthoridAkutsu, T=7102080520en_HK
dc.identifier.scopusauthoridHayashida, M=9275689800en_HK
dc.identifier.scopusauthoridChing, WK=13310265500en_HK
dc.identifier.scopusauthoridNg, MK=34571761900en_HK
dc.identifier.issnl0022-5193-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats