Algorithms and complexity analyses for control of singleton attractors in Boolean networks.
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.
Hayashida
Morihiro
M
Bioinformatics Center, Laboratory of Biological Information Networks, Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji, Kyoto, Japan.
Tamura
Takeyuki
T
Akutsu
Tatsuya
T
Zhang
Shu-Qin
SQ
Ching
Wai-Ki
WK
J Comput Biol. 2002;9(1):67-103
11911796
J Theor Biol. 2005 Oct 7;236(3):291-310
15885706
Bioinformatics. 2005 Nov 1;21(21):4021-5
16150807
J Theor Biol. 2007 Feb 21;244(4):670-9
17069859
Phys Rev Lett. 2003 Mar 7;90(9):098701
12689263
Nat Rev Cancer. 2004 Mar;4(3):227-35
14993904
EURASIP J Bioinform Syst Biol. 2007;:20180
18253467
Cell. 2007 Nov 30;131(5):861-72
18035408
Genome Inform Ser Workshop Genome Inform. 1998;9:151-160
11072331
Nature. 2002 Nov 14;420(6912):206-10
12432404
Nat Genet. 2002 May;31(1):60-3
11967534
Cell. 2006 Aug 25;126(4):663-76
16904174
Phys Rev Lett. 2005 Mar 4;94(8):088701
15783941
Science. 1999 Oct 15;286(5439):509-12
10521342
Bioinformatics. 2005 Apr 1;21(7):1211-8
15531600
Bioinformatics. 2002 Feb;18(2):261-74
11847074
J Mol Med (Berl). 1999 Jun;77(6):469-80
10475062
IET Syst Biol. 2007 Nov;1(6):361-8
18203582
In Silico Biol. 2003;3(3):389-404
12954096
Int J Neural Syst. 2005 Aug;15(4):297-310
16187405
Bioessays. 1998 May;20(5):433-40
9670816
Bioinformatics. 2004 Apr 12;20(6):924-30
14751971
Neuron. 2000 Jun;26(3):567-80
10896154
Nature. 1969 Oct 11;224(5215):177-8
5343519
J Theor Biol. 1969 Mar;22(3):437-67
5803332
Science. 2007 Dec 21;318(5858):1917-20
18029452
Bull Math Biol. 2003 Nov;65(6):1025-51
14607287