The Optimal One-bit Perturbation Algorithm Based On The Basin Of Attractor Of Boolean Networks

Boolean network has been a simple but very effective mathematical model to study gene regulatory networks.In this model,gene expressions being quantized as 0s and 1s to represent not expressed and expressed states.The Boolean network model is simple but can reflect the regulation relationships between genes and dynamic behavior of the system.In Boolean network model,attractors represent different cell states,the size of BOA reflects the stability of the corresponding attractor.The ultimate objective of network modeling is to design appropriate intervention strategies to influence its dynamic behavior,which can make the system evolve in the desirable direction.It established theoretical foundation for the treatment of diseases and drug targets.In this paper,we mainly investigate the problem of structural intervention based on the one-bit Boolean function.In order to avoid perturbations that cause the attractor change unpredictable,we restrict all perturbations to maintain the original attractor of the system.First,we propose an algorithm to determine the appropriate perturbation.Second,since any one intervention only changes the transformation of 2n-ki states,we propose a fast updating algorithm based on the state space of the network.It can quickly determine the change of BOA for each attractor in the system before and after the intervention.Results from both synthetic and real biological networks reveal that: the time complexity of our proposed algorithm is obviously better than the existing algorithm based on the steady-state distribution(SSD).And it can extend the network size of current structure intervention from 15 genes to 25 genes.