Designing biochemical systems that can be effectively used in diverse fields, including diagnostics, molecular computing and nanomachines, has long been recognized as an important goal of molecular programming and DNA nanotechnology. A key issue in the development of such practical devices on the nanoscale lies in the development of biochemical components with information-processing capacity. In this article, we propose a molecular device that utilizes DNA strand displacement networks and allows interactive inhibition between two input signals; thus, it is termed a cross-inhibitor. More specifically, the device supplies each input signal with a processor such that the processing of one input signal will interdict the signal of the other. Biochemical experiments are conducted to analyze the interdiction performance with regard to effectiveness, stability and controllability. To illustrate its feasibility, a biochemical framework grounded in this mechanism is presented to determine the winner of a tic-tac-toe game. Our results highlight the potential for DNA strand displacement cascades to act as signal controllers and event triggers to endow molecular systems with the capability of controlling and detecting events and signals.

Given a graph whose vertex set is partitioned, the partition coloring problem (PCP) requires the selection of one vertex from each partite set, such that the subgraph induced by the set of the selected vertices has the minimum chromatic number. Motivated by the routing and wavelength assignment problem for optical networks, PCP has been used to model many other real-world applications, such as dichotomy-based constraint encoding and scheduling problems. Solving PCP for large graphs is still a challenge since it is NP-complete. In this article, we first propose a key concept called a partition independent set (PIS) and design an efficient algorithm called FastPIS to find a maximum PIS. By applying FastPIS with a simple coloring procedure, we can obtain a high-quality initial solution for PCP. Moreover, we propose a reduction rule based on another novel concept called an ℓ-clustering-degree bound ordered set (ℓ-CDBOS), by which the scale of the working graph can be iteratively reduced. Based on these techniques, we develop an efficient method called HotPGC for solving PCP. The proposed algorithm is evaluated on benchmark graphs, and computational results show that HotPGC achieves highly competitive performance, compared with the state-of-the-art algorithms. The influence of the proposed reduction rule on the efficiency of HotPGC is also analyzed.

The minimum vertex cover (MVC) problem is a canonical NP-hard combinatorial optimization problem aiming to find the smallest set of vertices such that every edge has at least one endpoint in the set. This problem has extensive applications in cybersecurity, scheduling, and monitoring link failures in wireless sensor networks (WSNs). Numerous local search algorithms have been proposed to obtain “good” vertex coverage. However, due to the NP-hard nature, it is challenging to efficiently solve the MVC problem, especially on large graphs. In this paper, we propose an efficient local search algorithm for MVC called TIVC, which is based on two main ideas: a 3-improvements (TI) framework with a tiny perturbation and edge selection strategy. We conducted experiments on real-world large instances of a massive graph benchmark. Compared with three state-of-the-art MVC algorithms, TIVC shows superior performance in accuracy and possesses a remarkable ability to identify significantly smaller vertex covers on many graphs.

DeoxyriboNucleic Acid (DNA) encryption is a new encryption method that appeared along with the research of DNA nanotechnology in recent years. Due to the complexity of biology in DNA nanotechnology, DNA encryption brings in an additional difficulty in deciphering and, thus, can enhance information security. As a new approach in DNA nanotechnology, DNA strand displacement has particular advantages such as being enzyme free and self-assembly. However, the existing research on DNA-strand-displacement-based encryption has mostly stayed at a theoretical or simulation stage. To this end, this paper proposes a new DNA-strand-displacement-based encryption framework. This encryption framework involves three main strategies. The first strategy was a tri-phase conversion from plaintext to DNA sequences according to a Huffman-coding-based transformation rule, which enhances the concealment of the information. The second strategy was the development of DNA strand displacement molecular modules, which produce the initial key for information encryption. The third strategy was a cyclic-shift-based operation to extend the initial key long enough, and thus increase the deciphering difficulty. The results of simulation and biological experiments demonstrated the feasibility of our scheme for encryption. The approach was further validated in terms of the key sensitivity, key space, and statistic characteristic. Our encryption framework provides a potential way to realize DNA-strand-displacement-based encryption via biological experiments and promotes the research on DNA-strand-displacement-based encryption.

The concept of a metric dimension was proposed to model robot navigation where the places of navigating agents can change among nodes. The metric dimension $md\left(G\right)$ of a graph G is the smallest number k for which G contains a vertex set W, such that $\left|W\right|=k$ and every pair of vertices of G possess different distances to at least one vertex in W. In this paper, we demonstrate that $md\left(HDN1\right(n\left)\right)=4$ for $n\ge 2$ . This indicates that in these types of hex derived sensor networks, the least number of nodes needed for locating any other node is four.