Bio-molecular algorithms for NP complete problems

Starting date
February 21, 2003
Duration (months)
Computer Science
Managers or local contacts
Manca Vincenzo
DNA Computing, Molecular computing, NP complete problems, Unconventional computation models, Bioinformatics, Complex systems

The unit will develop the following points:
  1. directing the biolab activity for implementing protocols and methods of DNA Computing relative to an algorithm based on [Manca, Di Gregorio, Lizzari, Vallini, Zandron, 2001] on given instances of SAT. These protocols should be defined at a level of analysis such that they could be viewed as autonomous 'tools' suitable for application and integration in the solution of a wide class of combinatorial algorithms. The experimental activity until May 2002 will be presented at the '8th Internationa Meeting on DNA Based Computers' in Sapporo, Japan;
  2. elaborating instruments of analysis for evaluating the most important computational parameters of SAT instances (size of the space of the solutions, number of separations) and for analyzing their relationship in the different methods for solving SAT;
  3. determining operations, and related biological realizations, for executing separation steps. Studying their reliability and their efficiency;
  4. individuating computational and mathematical criteria of pre-analysis of instances of SAT, in such a way that the "real" DNA complexity of a given instance could be established. In fact, very often the number of variables and equations is only a superficial parameter, because if we apply simple transformations, we can reduce an instance with high numbers of variables and equations into an equivalent one with smaller values of these numbers. Moreover, frequently a big instance can be decomposed in many smaller instances that are easily solvable. Finally, several times, the solution space has a smaller subspace that is significant for the search of solutions;
  5. considering DNA algorithms in the wider perspective of 'problem solvers' that could be implemented with other computational structures inspired by biology, such as P-systems (developed by the unit of Milan) or other systems based on membranes and their physical models;
  6. analyzing the dynamic nature of systems indicated in the previous point, from the perspective of 'symbolic dynamic'. Along this way, it is interesting to model in a discrete way not only combinatorial solvability, but also dynamical features related to stability, interactivity, learnability and reproduction;
  7. finding connections between the analyses developed in the previous two points with the interesting results about the statistical distribution of solutions of SAT and the formalization of cellular dynamics by means of boolean networks after Derrida and Kauffman.


Ministero dell'Istruzione dell'Università e della Ricerca
Funds: assigned and managed by an external body
Syllabus: FIRB

Project participants

Luca Bianco
Federico Fontana
Giuditta Franco
Assistant Professor
Cinzia Giagulli
Vincenzo Manca
Full Professor


Research facilities