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

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. (C) 2002 Elsevier Science Ltd. All rights reserved.