Affordable Access

On the number of experiments required to find the causal structure of complex systems.

Authors
  • Krupa, Boris
Type
Published Article
Journal
Journal of theoretical biology
Publication Date
Nov 21, 2002
Volume
219
Issue
2
Pages
257–267
Identifiers
PMID: 12413879
Source
Medline
License
Unknown

Abstract

The need to capture the complexity of biological systems in a simpler formalism is the underlying impetus of biological sciences. Understanding the function of many biological complex systems, such as genetic networks or molecular signalling pathways, requires precise identification of the interactions between their individual components. A number of questions in the study of complex systems are then important-in particular, what can be inferred about the interactions in a complex system from an arbitrary set of experiments, and, what is the minimum number of experiments required to characterize the system? This paper shows that the problem of finding the minimal causal structure of a system based on a set of observations is computationally intractable for even moderately sized systems (it is NP-hard), but a reasonable approximation can be found in a relatively short (polynomial) time. Next, it is shown that the number of experiments required to characterize a complex system grows exponentially with the upper bound on the number of immediate upstream influences of each element, but only logarithmically with the number of elements in the system. This makes it possible to study biological systems with extremely large number of interacting elements and relatively sparse interconnections, such as gene regulatory and cell signalling networks. Finally, the construction of a randomized experimental sequence which achieves this bound is discussed.

Report this publication

Statistics

Seen <100 times