Distribution and enumeration of attractors in probabilistic Boolean networks

Area of Science:

• Computational Biology
• Systems Biology
• Network Science

Background:

• Gene regulatory networks are often modeled using mathematical approaches.
• Probabilistic Boolean networks (PBNs) offer a framework for modeling these complex systems.
• Understanding network attractors is crucial for predicting system behavior.

Purpose of the Study:

• To investigate the expected number of singleton attractors in PBNs.
• To develop and analyze algorithms for identifying singleton and small attractors in PBNs.
• To compare the efficiency of new algorithms against existing methods.

Main Methods:

• Mathematical modeling of probabilistic Boolean networks.
• Derivation of formulas for expected numbers of attractors.
• Development of algorithms for attractor identification.
• Theoretical and computational complexity analysis of algorithms.

Main Results:

• The expected number of singleton attractors in a PBN is (2 - (1/2)(L-1))(n), simplifying to 1.5(n) for L=2.
• This contrasts with the expected number of singleton attractors in Boolean networks (BNs), which is 1.
• Average case time complexities for identifying singleton attractors in PBNs with L=2 and L=3 are O(1.601(n)) and O(1.763(n)), respectively.
• Developed algorithms demonstrate significantly higher efficiency compared to naive state-space examination.

Conclusions:

• The study provides a quantitative measure for singleton attractors in PBNs.
• Novel algorithms offer efficient solutions for attractor identification in PBNs.
• These findings contribute to a better understanding of gene regulatory network dynamics and computational analysis.