Process-driven inference of biological network structure: feasibility, minimality, and multiplicity

Area of Science:

• Molecular Biology
• Systems Biology
• Computational Biology

Background:

• Inferring molecular interaction networks from experimental data is crucial in cell biology.
• Boolean analysis offers a simplified approach by treating molecular states as on/off.
• The process-driven approach is promising for identifying network structures, stability, and modularity.

Purpose of the Study:

• To formally analyze the computational complexity of molecular network inference using the process-driven boolean approach.
• To investigate the complexity of feasibility, minimality, and multiplicity problems under the dominant inhibition assumption.
• To develop and evaluate efficient heuristics for network inference.

Main Methods:

• Formal examination of the process-driven boolean approach.
• Computational complexity analysis, including proofs for polynomial-time solvability and NP-hardness.
• Development and simulation of a polynomial-time heuristic for near-minimal network solutions.
• Theoretical framework for estimating network solution multiplicity.

Main Results:

• The feasibility problem (existence of a network) is solvable in polynomial time.
• The minimality problem (smallest network) is NP-hard, indicating computational difficulty.
• A polynomial-time heuristic yields near-minimal network solutions.
• A fast heuristic accurately estimates network solution multiplicity, avoiding exponential computation.

Conclusions:

• Boolean network inference is computationally tractable for feasibility but challenging for minimality.
• Heuristics provide efficient and accurate solutions for complex network inference problems.
• This work advances computational methods for understanding cellular molecular interactions.