Aug 20, 2018

On the Number of Driver Nodes for Controlling a Boolean Network to Attractors

BioRxiv : the Preprint Server for Biology
Wenpin HouT Akutsu


It is known that many driver nodes are required to control complex biological networks. Previous studies imply that O(N) driver nodes are required in both linear complex network and Boolean network models with N nodes if an arbitrary state is specified as the target. In this paper, we mathematically prove under a reasonable assumption that the expected number of driver nodes is only O(log\_2 N +log\_2 M) for controlling Boolean networks if the targets are restricted to attractors, where M is the number of attractors. Since it is expected that M is not very large in many practical networks, this is a significant improvement. This result is based on discovery of novel relationships between control problems on Boolean networks and the coupon collector's problem, a well-known concept in combinatorics. We also provide lower bounds of the number of driver nodes as well as simulation results using artificial and realistic network data, which support our theoretical findings.

  • References
  • Citations


  • We're still populating references for this paper, please check back later.
  • References
  • Citations


  • This paper may not have been cited yet.

Mentioned in this Paper

WOUND collector
Anatomic Node

About this Paper

Related Feeds

BioRxiv & MedRxiv Preprints

BioRxiv and MedRxiv are the preprint servers for biology and health sciences respectively, operated by Cold Spring Harbor Laboratory. Here are the latest preprint articles (which are not peer-reviewed) from BioRxiv and MedRxiv.