title: Algorithms and complexity analyses for control of singleton attractors in Boolean networks.
abstract: A Boolean network (BN) is a mathematical model of genetic networks. We propose several algorithms for control of singleton attractors in BN. We theoretically estimate the average-case time complexities of the proposed algorithms, and confirm them by computer experiments. The results suggest the importance of gene ordering. Especially, setting internal nodes ahead yields shorter computational time than setting external nodes ahead in various types of algorithms. We also present a heuristic algorithm which does not look for the optimal solution but for the solution whose computational time is shorter than that of the exact algorithms.
authors.affiliation: Bioinformatics Center, Laboratory of Biological Information Networks, Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji, Kyoto, Japan.
authors.forename: Morihiro
authors.initials: M
authors.lastname: Hayashida
authors.forename: Takeyuki
authors.initials: T
authors.lastname: Tamura
authors.forename: Tatsuya
authors.initials: T
authors.lastname: Akutsu
authors.forename: Shu-Qin
authors.initials: SQ
authors.lastname: Zhang
authors.forename: Wai-Ki
authors.initials: WK
authors.lastname: Ching
references.citation: J Comput Biol. 2002;9(1):67-103
references.pmid: 11911796
references.citation: J Theor Biol. 2005 Oct 7;236(3):291-310
references.pmid: 15885706
references.citation: Bioinformatics. 2005 Nov 1;21(21):4021-5
references.pmid: 16150807
references.citation: J Theor Biol. 2007 Feb 21;244(4):670-9
references.pmid: 17069859
references.citation: Phys Rev Lett. 2003 Mar 7;90(9):098701
references.pmid: 12689263
references.citation: Nat Rev Cancer. 2004 Mar;4(3):227-35
references.pmid: 14993904
references.citation: EURASIP J Bioinform Syst Biol. 2007;:20180
references.pmid: 18253467
references.citation: Cell. 2007 Nov 30;131(5):861-72
references.pmid: 18035408
references.citation: Genome Inform Ser Workshop Genome Inform. 1998;9:151-160
references.pmid: 11072331
references.citation: Nature. 2002 Nov 14;420(6912):206-10
references.pmid: 12432404
references.citation: Nat Genet. 2002 May;31(1):60-3
references.pmid: 11967534
references.citation: Cell. 2006 Aug 25;126(4):663-76
references.pmid: 16904174
references.citation: Phys Rev Lett. 2005 Mar 4;94(8):088701
references.pmid: 15783941
references.citation: Science. 1999 Oct 15;286(5439):509-12
references.pmid: 10521342
references.citation: Bioinformatics. 2005 Apr 1;21(7):1211-8
references.pmid: 15531600
references.citation: Bioinformatics. 2002 Feb;18(2):261-74
references.pmid: 11847074
references.citation: J Mol Med (Berl). 1999 Jun;77(6):469-80
references.pmid: 10475062
references.citation: IET Syst Biol. 2007 Nov;1(6):361-8
references.pmid: 18203582
references.citation: In Silico Biol. 2003;3(3):389-404
references.pmid: 12954096
references.citation: Int J Neural Syst. 2005 Aug;15(4):297-310
references.pmid: 16187405
references.citation: Bioessays. 1998 May;20(5):433-40
references.pmid: 9670816
references.citation: Bioinformatics. 2004 Apr 12;20(6):924-30
references.pmid: 14751971
references.citation: Neuron. 2000 Jun;26(3):567-80
references.pmid: 10896154
references.citation: Nature. 1969 Oct 11;224(5215):177-8
references.pmid: 5343519
references.citation: J Theor Biol. 1969 Mar;22(3):437-67
references.pmid: 5803332
references.citation: Science. 2007 Dec 21;318(5858):1917-20
references.pmid: 18029452
references.citation: Bull Math Biol. 2003 Nov;65(6):1025-51
references.pmid: 14607287