On the number of experiments required to find the causal structure of complex systems
On the number of experiments required to find the causal structure of complex systems
复制标题
DOI：
10.1006/jtbi.2002.3119
复制
发表时间：
2002-11-21
影响因子：
2
通讯作者：
Krupa, B
中科院分区：
文献类型：
--
作者：
Krupa, B
用更简单的形式主义来捕捉生物系统的复杂性的需要是生物科学的潜在动力。了解许多生物复杂系统的功能，如遗传网络或分子信号通路。需要精确识别其各个组件之间的相互作用。在复杂系统的研究中，一些问题是很重要的，特别是，从一组任意的实验中可以推断出复杂系统中的相互作用，以及，描述系统特征所需的最少实验次数是多少？本文表明，基于一组观测值找到系统的最小因果结构的问题对于即使是中等大小的系统也是计算上难以处理的（它是NP-难的），但是可以在相对较短的（多项式）时间内找到合理的近似。接下来，它示出，表征一个复杂的系统所需的实验的数量呈指数增长的上限上的每个元素的直接上游的影响的数量，但仅与系统中的元素的数量呈几何关系。这使得研究具有大量相互作用元件和相对稀疏的互连的生物系统成为可能，例如基因调控和细胞信号网络。终于来了讨论了达到这个界的随机实验序列的构造。(C)2002爱思唯尔科技有限公司。保留所有权利。
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.