Enumeration and extension of non-equivalent deterministic update schedules in Boolean networks

Area of Science:

• Computational Biology
• Systems Biology
• Bioinformatics

Background:

• Boolean networks (BNs) are widely used for modeling genetic regulatory networks (GRNs).
• The dynamical behavior of BNs is sensitive to the updating scheme, necessitating diverse rules for realistic GRN modeling.
• Previous work defined equivalence classes of deterministic update schedules using labeled interaction digraphs.

Purpose of the Study:

• To address the problem of enumerating all non-equivalent deterministic update schedules for a given BN.
• To develop a method for constructing update digraphs and associated schemes.
• To handle cases with partial knowledge of node update order.

Main Methods:

• Constructing an algorithm to determine the set of update digraphs for a BN.
• Employing a divide and conquer methodology based on interaction digraph structure.
• Associating schemes with each determined update digraph.

Main Results:

• Demonstrated that enumerating non-equivalent schedules is generally intractable.
• Developed an algorithm to determine update digraphs and associated schemes.
• The algorithm accommodates partial knowledge of update order.

Conclusions:

• The developed algorithm provides a method for enumerating non-equivalent deterministic update schedules in BNs.
• This approach enhances the realism and accuracy of GRN models.
• The algorithm is applicable even with incomplete information on update sequences.