论文标题
从正面反馈顶点集找到布尔网络的固定点
Finding the fixed points of a Boolean network from a positive feedback vertex set
论文作者
论文摘要
在布尔网络对生物系统的建模中，一个关键问题是找到给定网络的固定点集。一些构造的算法考虑了相互作用图的某些结构特性，如Akutsu等人所提出的结构特性。在\ cite {akutsu1998system，zhang2007algorithms}中，考虑图形的反馈顶点集。但是，这些方法没有考虑其组件之间的作用类型（激活，抑制）。 在本文中，我们提出了一种新算法，用于根据积极的反馈顶点集$ p $的相互作用图，并通过应用顺序更新时间表，在时间$ o（2^{| p | p |} \ cdot n^2）$中，其中$ n是$ n $ n是组合数的数量。该算法的理论基础是一个很好的表征，我们给出了布尔网络的动态行为，而没有正循环，并且具有固定点。 可以在Java中制作的\ afp的可执行文件和一些输入文件的示例，网址为：\ href {http://www.inf.udec.cl/~lilian/fpcollector/} {\ url} {\ url
In the modeling of biological systems by Boolean networks a key problem is finding the set of fixed points of a given network. Some constructed algorithms consider certain structural properties of the interaction graph like those proposed by Akutsu et al. in \cite{akutsu1998system,zhang2007algorithms} which consider a feedback vertex set of the graph. However, these methods do not take into account the type of action (activation, inhibition) between its components. In this paper we propose a new algorithm for finding the set of fixed points of a Boolean network, based on a positive feedback vertex set $P$ of its interaction graph and which works, by applying a sequential update schedule, in time $O(2^{|P|} \cdot n^2)$, where $n$ is the number of components. The theoretical foundation of this algorithm is due a nice characterization, that we give, of the dynamical behavior of the Boolean networks without positive cycles and with a fixed point. An executable file of \Afp made in Java and some examples of input files are available at: \href{http://www.inf.udec.cl/~lilian/FPCollector/}{\url{www.inf.udec.cl/~lilian/FPCollector/}}
