On the Minimum Number of Genes Required for Discriminating Steady States under a Boolean Model
On the Minimum Number of Genes Required for Discriminating Steady States under a Boolean Model
复制标题
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Xiaoqing Cheng;Takeyuki Tamura;W. Ching;T. Akutsu
中科院分区：
文献类型：
--
作者：
Xiaoqing Cheng;Takeyuki Tamura;W. Ching;T. Akutsu
通过观察一些基因的基因表达模式来识别每个细胞的类型是一个重要的研究课题。由于吸引子通常被认为与细胞类型相对应，因此我们研究了在布尔网络模型下找到用于区分给定吸引子的最小节点集的问题。我们提出组合算法并分析其时间复杂度。特别是，我们证明一个节点不一定足够，但两个节点总是足以区分两个周期性吸引子。
Identifying the type of each cell by observing gene expression patterns of a few genes is an important research topic. Since attractors are often regarded to correspond to cell types, we study the problem of finding a minimum set of nodes for discriminating given attractors, under the Boolean network model. We present combinatorial algorithms and analyze their time complexities. In particular, we prove that one node is not necessarily enough but two nodes are always enough to discriminate two periodic attractors.