A tissue P system and a DNA microfluidic device for solving the shortest common superstring problem

This paper describes a tissue P system for solving the Shortest Common Superstring Problem in linear time. This tissue P system is well suited for parallel and distributed implementation using a microfluidic device working with DNA strands. The approach is not based on the usual brute force generate/test technique applied in DNA computing, but it builds the space solution gradually. The possible solutions/superstrings are build step by step through the parallel distributed combination of strings using the overlapping concatenation operation. Moreover, the DNA microfluidic device solves the problem autonomously, without the need of external control or manipulation.An erratum to this article can be found at