File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Algorithms for finding small attractors in boolean networks

TitleAlgorithms for finding small attractors in boolean networks
Authors
Issue Date2007
PublisherHindawi Publishing Corp. The Journal's web site is located at http://www.hindawi.com/journals/bsb/
Citation
Eurasip Journal On Bioinformatics And Systems Biology, 2007, v. 2007, article no. 20180 How to Cite?
AbstractA Boolean network is a model used to study the interactions between different genes in genetic regulatory networks. In this paper, we present several algorithms using gene ordering and feedback vertex sets to identify singleton attractors and small attractors in Boolean networks. We analyze the average case time complexities of some of the proposed algorithms. For instance, it is shown that the outdegree-based ordering algorithm for finding singleton attractors works in O( 1.19 n) time for K=2, which is much faster than the naive O( 2n) time algorithm, where n is the number of genes and K is the maximum indegree. We performed extensive computational experiments on these algorithms, which resulted in good agreement with theoretical results. In contrast, we give a simple and complete proof for showing that finding an attractor with the shortest period is NP-hard.
Persistent Identifierhttp://hdl.handle.net/10722/75285
ISSN
2015 SCImago Journal Rankings: 0.324
References

 

DC FieldValueLanguage
dc.contributor.authorZhang, SQen_HK
dc.contributor.authorHayashida, Men_HK
dc.contributor.authorAkutsu, Ten_HK
dc.contributor.authorChing, WKen_HK
dc.contributor.authorNg, MKen_HK
dc.date.accessioned2010-09-06T07:09:41Z-
dc.date.available2010-09-06T07:09:41Z-
dc.date.issued2007en_HK
dc.identifier.citationEurasip Journal On Bioinformatics And Systems Biology, 2007, v. 2007, article no. 20180en_HK
dc.identifier.issn1687-4145en_HK
dc.identifier.urihttp://hdl.handle.net/10722/75285-
dc.description.abstractA Boolean network is a model used to study the interactions between different genes in genetic regulatory networks. In this paper, we present several algorithms using gene ordering and feedback vertex sets to identify singleton attractors and small attractors in Boolean networks. We analyze the average case time complexities of some of the proposed algorithms. For instance, it is shown that the outdegree-based ordering algorithm for finding singleton attractors works in O( 1.19 n) time for K=2, which is much faster than the naive O( 2n) time algorithm, where n is the number of genes and K is the maximum indegree. We performed extensive computational experiments on these algorithms, which resulted in good agreement with theoretical results. In contrast, we give a simple and complete proof for showing that finding an attractor with the shortest period is NP-hard.en_HK
dc.languageengen_HK
dc.publisherHindawi Publishing Corp. The Journal's web site is located at http://www.hindawi.com/journals/bsb/en_HK
dc.relation.ispartofEurasip Journal on Bioinformatics and Systems Biologyen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.titleAlgorithms for finding small attractors in boolean networksen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1687-4145&volume=2007&spage=20180 (13 pages)&epage=&date=2007&atitle=Algorithms+for+Finding+Small+Attractors+in+Boolean+Networksen_HK
dc.identifier.emailChing, WK:wching@hku.hken_HK
dc.identifier.authorityChing, WK=rp00679en_HK
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1155/2007/20180en_HK
dc.identifier.scopuseid_2-s2.0-34250800265en_HK
dc.identifier.hkuros129378en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-34250800265&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume2007en_HK
dc.identifier.spagearticle no. 20180-
dc.identifier.epagearticle no. 20180-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridZhang, SQ=10143093600en_HK
dc.identifier.scopusauthoridHayashida, M=9275689800en_HK
dc.identifier.scopusauthoridAkutsu, T=7102080520en_HK
dc.identifier.scopusauthoridChing, WK=13310265500en_HK
dc.identifier.scopusauthoridNg, MK=34571761900en_HK
dc.identifier.citeulike5301233-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats