Related Experiment Video
Updated: Jul 19, 2026
05:55
Modeling the Functional Network for Spatial Navigation in the Human Brain
Published on: October 13, 2023
Control of Boolean networks: hardness results and algorithms for tree structured networks
Tatsuya Akutsu1, Morihiro Hayashida, Wai-Ki Ching
1Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto 611-0011, Japan. takutsu@kuicr.kyoto-u.ac.jp
Journal of Theoretical Biology
|October 31, 2006
Summary
Controlling cell states via Boolean networks (BNs) is generally NP-hard. However, polynomial-time solutions exist for tree-structured networks, offering insights for genetic control strategies.
Area of Science:
- Computational Biology
- Systems Biology
- Control Theory
Background:
- Cellular control strategies are crucial in the post-genomic era.
- Boolean networks (BNs) offer a simplified model for genetic regulatory networks.
Purpose of the Study:
- To investigate the theoretical complexity of finding control strategies for Boolean networks.
- To explore conditions under which the control problem is computationally tractable.
Main Methods:
- Theoretical analysis of control strategies using Boolean network models.
- Complexity analysis, including NP-hardness proofs.
- Algorithm development for specific network structures (e.g., tree structures).
Main Results:
- The general problem of finding a desired global state in BNs is NP-hard.
- This hardness extends to restricted BN structures, justifying exponential algorithms for PBNs.
- A polynomial-time algorithm is presented for tree-structured BNs, extendable to networks with few loops and short time steps.
Conclusions:
- The computational complexity of cellular control varies significantly with network topology.
- Theoretical findings provide a foundation for developing efficient algorithms for specific genetic network architectures.
- Biological implications of these theoretical results are discussed.
Related Concept Videos
01:25Network Function of a Circuit
Frequency response analysis in electrical circuits provides vital insights into a circuit's behavior as the frequency of the input signal changes. The transfer function, a mathematical tool, is instrumental in understanding this behavior. It defines the relationship between phasor output and input and comes in four types: voltage gain, current gain, transfer impedance, and transfer admittance. The critical components of the transfer function are the poles and zeros.
01:12Theorems of Pappus and Guldinus: Problem Solving
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a cylinder...
01:22Block Diagram Reduction
The process of deriving the transfer function of a control system often involves reducing its block diagram to a single block. This simplification can be achieved through a series of strategic operations, including relocating branch points and comparators. These operations preserve the overall function of the system while allowing for easier manipulation and combination of blocks.
The first step in this process is the identification and relocation of a branch point. A branch point, where a...
The first step in this process is the identification and relocation of a branch point. A branch point, where a...
01:14Castigliano's Theorem: Problem Solving
The deflection of a simply supported beam that carries a central point load can be analyzed using structural mechanics principles, particularly by applying Castigliano's theorem. This theorem relates the displacement at the load application point to the partial derivatives of the strain energy in the structure. The simply supported beam with a point load at its center has symmetric reaction forces at the supports, each bearing half of the load. The bending moment at any point along the beam is...
01:34Woodward–Hoffmann Selection Rules and Microscopic Reversibility
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
01:19Survival Tree
Survival trees are a non-parametric method used in survival analysis to model the relationship between a set of covariates and the time until an event of interest occurs, often referred to as the "time-to-event" or "survival time." This method is particularly useful when dealing with censored data, where the event has not occurred for some individuals by the end of the study period, or when the exact time of the event is unknown.
Building a Survival Tree
Constructing a survival tree begins...
Building a Survival Tree
Constructing a survival tree begins...