Algorithms and Complexity Analyses for Control of Singleton Attractors in Boolean Networks |
| |
| Authors: | Morihiro Hayashida Takeyuki Tamura Tatsuya Akutsu Shu-Qin Zhang Wai-Ki Ching |
| |
| Institution: | 1Bioinformatics Center, Laboratory of Biological Information Networks, Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji, Kyoto 611-0011, Japan;2School of Mathematical Sciences, Fudan University, Shanghai 200433, China;3Advanced Modeling and Applied Computing Laboratory, Department of Mathematics, The University of Hong Kong, Pokfulam Road, Hong Kong |
| |
| 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. |
| |
| Keywords: | |
|
|
