Integer programming-based method for observability of singleton attractors in Boolean networks

Xiaoqing Cheng; Yushan Qiu; Wenpin Hou; Wai-Ki Ching

Integer programming-based method for observability of singleton attractors in Boolean networks

View Fulltext

Author(s): Xiaoqing Cheng ¹¹ ; Yushan Qiu ²² ; Wenpin Hou ³³ ; Wai-Ki Ching ³³
- Affiliations: 1: School of Mathematics and Statistics, Xian Jiaotong Univeristy, Xian, People's Republic of China ;
  2: College of Mathematics and Statistics, Shenzhen University, Shenzhen, Guangdong, People's Republic of China ;
  3: Advanced Modeling and Applied Computing Laboratory, Department of Mathematics, The University of Hong Kong, Pokfulam Road, Hong Kong
Source: Volume 11, Issue 1, February 2017, p. 30 – 35
DOI: 10.1049/iet-syb.2016.0022 , Print ISSN 1751-8849, Online ISSN 1751-8857

Received 06/05/2016, Accepted 18/07/2016, Revised 15/07/2016, Published 01/02/2017

Boolean network (BN) is a popular mathematical model for revealing the behaviour of a genetic regulatory network. Furthermore, observability, an important network feature, plays a significant role in understanding the underlying network. Several studies have been done on analysis of observability of BNs and complex networks. However, the observability of attractor cycles, which can serve as biomarker detection, has not yet been addressed in the literature. This is an important, interesting and challenging problem that deserves a detailed study. In this study, a novel problem was first proposed on attractor observability in BNs. Identification of the minimum set of consecutive nodes can be used to discriminate different attractors. Furthermore, it can serve as a biomarker for different disease types (represented as different attractor cycles). Then a novel integer programming method was developed to identify the desired set of nodes. The proposed approach is demonstrated and verified by numerical examples. The computational results further illustrates that the proposed model is effective and efficient.

References

1. 1)
  - 26. Motwani, R., Xu, Y.: ‘Efficient algorithms for masking and finding quasi-identifiers’, Technical Report, Stanford University, 2007.
2. 2)
  - 21. Cheng, D.: ‘Input-state approach to Boolean networks’, IEEE Trans. Neural Netw., 2009, 20, pp. 512–521 (doi: 10.1109/TNN.2008.2011359).
3. 3)
  - 20. Cheng, D., Qi, H.: ‘Controllability and observability of Boolean control networks’, Automatica, 2009, 45, pp. 1659–1667 (doi: 10.1016/j.automatica.2009.03.006).
4. 4)
  - 19. Li, H., Xie, L., Wang, Y.: ‘On robust control invariance of Boolean control networks’, Automatica, 2016, 68, pp. 392–396 (doi: 10.1016/j.automatica.2016.01.075).
5. 5)
  - 2. Kauffman, S.: ‘Homeostasis and differentiation in random genetic control networks’, Nature, 1969, 224, pp. 177–178 (doi: 10.1038/224177a0).
6. 6)
  - 25. Licchesi, C., Osborn, S.: ‘Candidate keys for relations’, J. Comput. Syst. Sci., 1978, 17, (2), pp. 270–279 (doi: 10.1016/0022-0000(78)90009-0).
7. 7)
  - 10. Zhang, S., Hayashida, M., Akutsu, T., et al: ‘Algorithms for finding small attractors in Boolean networks’, EURASIP J. Bioinf. Syst. Biol., 2007, 20180, http://link.springer.com/article/10.1155/2007/20180.
8. 8)
  - 17. Qiu, Y., Tamura, T., Ching, W., et al: ‘On control of singleton attractors in multiple Boolean networks: integer programming-based method’, BMC Syst. Biol., 2014, 8, (S7), http://bmcsystbiol.biomedcentral.com/articles/10.1186/1752-0509-8-S1-S7.
9. 9)
  - 8. Datta, A., Choudhary, A., Bittner, M.L., et al: ‘External control in Markovian genetic regulatory networks’, Mach. Learn., 2003, 52, (1–2), pp. 169–191 (doi: 10.1023/A:1023909812213).
10. 10)
  - 28. Albert, R., Othmer, H.: ‘The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster’, J. Theor. Biol., 2003, 223, (1), pp. 1–18 (doi: 10.1016/S0022-5193(03)00035-3).
11. 11)
  - 9. Akutsu, T., Kuhara, S., Maruyama, o., et al: ‘A system for identifying genetic networks from gene expression patterns produced by gene disruptions and overexpression’, Genome Inf., 1998, 9, pp. 151–160.
12. 12)
  - 14. Akutsu, T., Hayashida, M., Ching, W., et al: ‘Control of Boolean networks: hardness results and algorithms for tree-structured networks’, J. Theor. Biol., 2007, 244, (4), pp. 670–679 (doi: 10.1016/j.jtbi.2006.09.023).
13. 13)
  - 1. Kauffman, S.: ‘Metabolic stability and epigenesis in randomly constructed genetic nets’, J. Theor. Biol., 1969, 22, (3), pp. 437–467 (doi: 10.1016/0022-5193(69)90015-0).
14. 14)
  - 11. Melkman, A., Tamura, T., Akutsu, T.: ‘Determining a singleton attractor of an AND/OR Boolean network in O(1.587n) time’, Inf. Process. Lett., 2010, 110, pp. 565–569 (doi: 10.1016/j.ipl.2010.05.001).
15. 15)
  - 24. Akutsu, T., Bao, F.: ‘Approximating minimum keys and optimal substructure screens’. Proc. COCOON, 1996, (LNCS, 1090), pp. 290–299.
16. 16)
  - 3. Kauffman, S., ‘The origins of order: Self-organization and selection in evolution’ (Oxford University Press, New York, 1993).
17. 17)
  - 27. Williams, P.: ‘Model building in mathematical programming’ (Wiley, Chichester, 1988).
18. 18)
  - 22. Liu, Y., Slotine, J., Barabasi, A.: ‘Observability of complex systems’, Proc. Natl. Acad. Sci. USA, 2013, 110, (7), pp. 2460–2465 (doi: 10.1073/pnas.1215508110).
19. 19)
  - 15. Hayashida, M., Tamura, T., Akutsu, T., et al: ‘Algorithms and complexity analyses for control of singleton attractors in Boolean networks’, EURASIP J. Bioinf. Syst. Biol., 2008, 2008, (1), p. 521407.
20. 20)
  - 5. Langmead, C., Jha, S.: ‘Symbolic approaches for finding control strategies in Boolean networks’, J. Bioinf. Comput. Biol., 2009, 7, pp. 323–338 (doi: 10.1142/S0219720009004084).
21. 21)
  - 7. Samuelsson, B., Troein, C.: ‘Superpolynomial growth in the number of attractors in Kauffman networks’, Phys. Rev. Lett., 2003, 90, (9), p. 098701 (doi: 10.1103/PhysRevLett.90.098701).
22. 22)
  - 16. Akutsu, T., Zhao, Y., Hayashida, M., et al: ‘Integer programming-based approach to attractor detection and control of Boolean networks’, IEICE Trans. Inf. Syst., 2012, E95-D, p. 2960 (doi: 10.1587/transinf.E95.D.2960).
23. 23)
  - 8. Dubrova, E., Tesienko, M.: ‘A SAT-based algorithm for finding attractors in synchronous Boolean networks’, IEEE/ACM Trans. Comput. Biol. Bioinf., 2011, 8, (5), pp. 1393–1399 (doi: 10.1109/TCBB.2010.20).
24. 24)
  - 23. Fornasini, E., Valcher, M.: ‘Observability, reconstructibility and state observers of Boolean control networks’, IEEE Trans. Autom. Control, 2013, 58 (doi: 10.1109/TAC.2012.2231592).
25. 25)
  - 18. Li, H., Wang, Y., Xie, L.: ‘Output tracking control of Boolean networks via state feedback: constant reference signal case’, Automatica, 2015, 59, pp. 54–59 (doi: 10.1016/j.automatica.2015.06.004).
26. 26)
  - 4. Balleza, E., Alvarez-Buylla, E., Chaos, A., et al: ‘Critical dynamic in genetic regulatory networks: examples from four kingdoms’, PLoS ONE, 2008, 3, p. e2456 (doi: 10.1371/journal.pone.0002456).
27. 27)
  - 3. Huang, S.: ‘Gene expression profiling, genetic networks, and cellular states: an integrating concept for tumorigenesis and drug discovery’, J. Mol. Med., 1999, 77, (6), pp. 469–480 (doi: 10.1007/s001099900023).
28. 28)
  - 12. Luque, B., Solé, R.: ‘Controlling chaos in random Boolean networks’, Europhys. Lett., 1997, 37, pp. 597–602 (doi: 10.1209/epl/i1997-00196-9).

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

Integer programming-based method for observability of singleton attractors in Boolean networks

References

Related content