论文标题
基于DNA的有限自动机的最佳代码字构造
Optimal Codeword Construction for DNA-based Finite Automata
论文作者
论文摘要
由于其高信息密度，巨大的并行机会以及密码学，基因工程和生物信息学的潜在应用，生物分子计算已成为计算机科学研究的重要领域。在文献中已经提出了使用DNA分子的计算框架来完成各种任务，例如模拟逻辑操作，执行矩阵乘法以及编码NP-HARD问题的实例。在其中一项关键应用中，一些研究提出了使用DNA杂交和连接来构建有限自动机。这些有限自动机的状态和符号编码是手动完成的。在此手稿中，我们研究了这种方法的代码字构建问题。我们在有限自动机中的符号和状态的数量上得出了精确的理论界限，并在特定情况下获得了完整的符号集。对于自动编码，提出了基于启发式和整数线性编程（ILP）的两种不同的解决方案。此外，我们提出了对实验室实验的早期基于模拟的验证。我们提出的流量接受有限的自动机，自动编码实际实验的符号并逐步执行模拟。
Biomolecular computation has emerged as an important area of computer science research due to its high information density, immense parallelism opportunity along with potential applications in cryptography, genetic engineering and bioinformatics. Computational frameworks using DNA molecules have been proposed in the literature to accomplish varied tasks such as simulating logical operations, performing matrix multiplication, and encoding instances of NP-hard problems. In one of the key applications, several studies have proposed construction of finite automata using DNA hybridisation and ligation. The state and symbol encoding of these finite automata are done manually. In this manuscript, we study the codeword construction problem for this approach. We derive exact theoretical bounds on the number of symbols and states in the finite automata and also obtain the complete set of symbols in a specific case. For automatic encoding, two different solutions, based on a heuristic and on Integer Linear Programming (ILP), are proposed. Furthermore, we propose an early simulation-based validation of laboratory experiments. Our proposed flow accepts a finite automaton, automatically encodes the symbols for the actual experiments and executes the simulation step-by-step.
