2024/07/26 by Liangjie Sun, Sun, Liangjie, Wai‐Ki Ching +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #FOS: Electrical engineering #Formal Methods in Verification #Gene Regulatory Network Analysis #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2407.18560
openalex publication_date 2024/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A Boolean network (BN) is called observable if any initial state can be uniquely determined from the output sequence. In the existing literature on observability of BNs, there is almost no research on the relationship between the number of observation nodes and the observability of BNs, which is an important and practical issue. In this paper, we mainly focus on three types of BNs with n nodes (i.e., K-AND-OR-BNs, K-XOR-BNs, and K-NC-BNs, where K is the number of input nodes for each node and NC means nested canalyzing) and study the upper and lower bounds of the number of observation nodes for these BNs. First, we develop a novel technique using information entropy to derive a general lower bound of the number of observation nodes, and conclude that the number of observation nodes cannot be smaller than [(1-K)+\frac2K-12Klog2(2K-1)]n to ensure that any K-AND-OR-BN is observable, and similarly, some lower bound is also obtained for K-NC-BNs. Then for any type of BN, we also develop two new techniques to infer the general lower bounds, using counting identical states at time 1 and counting the number of fixed points, respectively. On the other hand, we derive nontrivial upper bounds of the number of observation nodes by combinatorial analysis of several types of BNs. Specifically, we indicate that (\frac2K-K-12K-1)n,~1, and \lceil (n)/(K)\rceil are the best case upper bounds for K-AND-OR-BNs, K-XOR-BNs, and K-NC-BN, respectively.