Schober Steffen, Kracht David, Heckel Reinhard, Bossert Martin
Institute of Telecommunications and Applied Information Theory, Ulm University, Ulm, Germany.
EURASIP J Bioinform Syst Biol. 2011 Oct 11;2011(1):6. doi: 10.1186/1687-4153-2011-6.
Boolean models of regulatory networks are assumed to be tolerant to perturbations. That qualitatively implies that each function can only depend on a few nodes. Biologically motivated constraints further show that functions found in Boolean regulatory networks belong to certain classes of functions, for example, the unate functions. It turns out that these classes have specific properties in the Fourier domain. That motivates us to study the problem of detecting controlling nodes in classes of Boolean networks using spectral techniques. We consider networks with unbalanced functions and functions of an average sensitivity less than 23k, where k is the number of controlling variables for a function. Further, we consider the class of 1-low networks which include unate networks, linear threshold networks, and networks with nested canalyzing functions. We show that the application of spectral learning algorithms leads to both better time and sample complexity for the detection of controlling nodes compared with algorithms based on exhaustive search. For a particular algorithm, we state analytical upper bounds on the number of samples needed to find the controlling nodes of the Boolean functions. Further, improved algorithms for detecting controlling nodes in large-scale unate networks are given and numerically studied.
调控网络的布尔模型被假定为对扰动具有耐受性。这在定性上意味着每个函数只能依赖于少数节点。生物学动机的约束进一步表明，布尔调控网络中的函数属于某些函数类，例如，单变量函数。事实证明，这些类在傅里叶域具有特定属性。这促使我们研究使用谱技术检测布尔网络类中的控制节点的问题。我们考虑具有不平衡函数和平均敏感度小于23k的函数的网络，其中k是函数的控制变量数量。此外，我们考虑1-低网络类，其中包括单变量网络、线性阈值网络和具有嵌套分析函数的网络。我们表明，与基于穷举搜索的算法相比，谱学习算法的应用在检测控制节点方面具有更好的时间和样本复杂度。对于特定算法，我们给出了找到布尔函数控制节点所需样本数量的解析上界。此外，还给出了用于检测大规模单变量网络中控制节点的改进算法并进行了数值研究。
