Code generation for a DNA computer by integer linear programming

摘要

In this paper, we describe code generation using integer linear programming for a robot called ANP-96 which automatically performs DNA computing experiments. The robot consists of 8 tables for placing plates, a device called IMU to do various operations on a plate, etc., and can execute many experimental operations in parallel according to a given program. Since operations for DNA computing are executed under various constraints and may take a long time, executing many operations automatically and efficiently is essential. On the other hand, the current programming environment of ANP-96 is troublesome since it requires programmers to specify low level details which are not essential to experiments. In particular, programmers have to appropriately allocate a finite number of tables, and also efficiently schedule operations that take a long time. To automate such programming activities, we first designed a framework for specifying the problems of table allocation and operation scheduling, at an abstract level independent from ANP-96, and then implemented a code generator based on the framework. In the code generator, we employed the integer linear programming method developed in the field of compilers, which gives the optimal solution for the problems mentioned above.