Polynomial-time algorithm for controllability test of a class of boolean biological networks

Area of Science:

• Systems Biology
• Computational Biology
• Control Theory

Background:

• Boolean network models are widely used for analyzing complex biological networks, particularly gene regulatory networks.
• A key challenge in control theory for these networks is the controllability problem: determining if one substance can arbitrarily control others.

Purpose of the Study:

• To propose a polynomial-time algorithm for solving the controllability problem in Boolean networks.
• To develop a computationally efficient method applicable to large-scale biological networks.

Main Methods:

• The algorithm is based on a sufficient condition for controllability.
• It avoids rigorous Boolean operations, instead utilizing the adjacency matrix of the directed graph induced by the Boolean network.
• The approach is validated on a neurotransmitter signaling pathway.

Main Results:

• A polynomial-time algorithm for assessing controllability in Boolean networks is presented.
• The method is easily computable for a broader range of large-scale biological networks compared to existing approaches.
• The effectiveness of the proposed approach is demonstrated through application to a neurotransmitter signaling pathway.

Conclusions:

• The developed algorithm provides an efficient solution to the controllability problem in Boolean networks.
• The novel method, leveraging graph adjacency matrices, offers practical advantages for analyzing complex biological systems.
• This approach enhances the dynamical analysis of gene regulatory and signaling pathways.