A tissue P system and a DNA microfluidic device for solving the shortest common superstring problem |
| |
Authors: | Lucas Ledesma Daniel Manrique Alfonso Rodríguez-Patón |
| |
Affiliation: | (1) Universidad Politécnica de Madrid, Facultad de Informática, Campus de Montegancedo s/n, Boadilla del Monte, 28660 Madrid, Spain |
| |
Abstract: | 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 |
| |
Keywords: | Membrane computing DNA computing Microflow reactor Shortest common superstring problem |
本文献已被 SpringerLink 等数据库收录! |