Contribution to Bioinfomatics

Bioinformatics is a challenging research area where every major contribution can have significant impact on medicine, agriculture, and industry. Among various problems tackled in this area we are mainly interested in the problem of the prediction of the spatial shape of a polymer, given the sequence of monomers constituting it. This problem can be naturally formalized using constraints over finite domains or intervals of real numbers.

The PSP problem

A protein can be seen as a linked list of aminoacids. There are 20 kinds of aminoacids. Each spatial, 3D, conformation of the linked list is associated to a given potential.

The protein structure prediction (PSP) problem is that of predicting the spatial conformation that will be reached by the protein that is (should be) the one minimizing the potential.

Two main aproaches investigated: working within a discrete lattice, and working off-lattice.


  1. A. Dovier, M. Burato, and F. Fogolari.
    Using Secondary Structure Information for Protein Folding in CLP(FD).
    In Proc. of Workshop on Functional and Constraint Logic Programming, ENTCS vol. 76, 2002.
    ( SICStus Prolog code, computational results on a PC Pentium 3, 500 MHz, and Some input Data, Sept. 5th, 2002)
  2. A. Dovier. Constraint Approach to the Protein Folding Problem.
    AI*IA Notizie, Volume 2, pp. 17-22, Giugno 2003.
  3. A. Dal Palù, A. Dovier, F. Fogolari.
    Protein Folding in CLP(FD) with Empirical Contact Energies.
    In Joint Annual Workshop of the ERCIM Working Group on Constraints and the CoLogNET area on Constraint and Logic Programming MTA SZTAKI, Budapest, Hungary 30 June – 2 July, 2003. LNCS Volume 3010, pages 250–265.
    ( SICStus Prolog code of the above paper, Potential Table, and Input Data, May, 5th, 2003)
  4. A. Dal Palu’, S. Will, R. Backofen, and A. Dovier.
    Constraint Based Protein Structure Prediction Exploiting Secondary Structure Information (paper). In Proc. of CILC’04.
  5. A. Dal Palù, A. Dovier, and F. Fogolari.
    Constraint Logic Programming approach to protein structure prediction.
    BMC Bioinformatics 2004, 5:186, 30 November 2004.
    (Code and related files, June 2004)
  6. A. Dal Palù, A. Dovier, and E. Pontelli.
    Heuristics, Optimizations, and Parallelism for Protein Structure Prediction in CLP(FD).
    In Proc. of PPDP’05, Lisbon, 11-13 July 2005. ACM press, pp. 230-241 (also presented at CILC’05). (Code)
  7. A. Dal Palù, A.Dovier, and E. Pontelli.
    A New Constraint Solver for 3-D Lattices and its Application to the Protein Folding Problem.
    In proceedings of LPAR 2005, 2-6 Dec 2005, Montego Bay, Jamaica. (for the code, please email (dovier|dalpalu) at )
  8. A. Dal Palu’, A. Dovier, and E. Pontelli.
    A constraint solver for discrete lattices, its parallelization, and application to protein structure prediction. (draft)
  9. A. Dovier, A. Dal Palù, E. Pontelli.
    Enhancing the Computation of Approximate Solutions of the Protein Structure Determination
    In Proceedings of the IEEE international conference on Bioinformatics and biomedicine workshops, 2-4 november 2007, fremont california, IEEE isbn 978-1-4244-1604-2 pp. 38-44.
  10. A. Dal Palù, A. Dovier, and E. Pontelli.
    Computing Approximate Solutions of the Protein Structure Determination Problem using Global Constraints on Discrete Crystal Lattices.
    Int’l Journal of Data Mining and Bioinformatics. 4(1):1-20. (draft and proofs as NMSU research report


  1. A. Dal Palù, A. Dovier, F. Fogolari.
    Protein Folding Simulation in CCP. (DRAFT).
    In Proc. of ICLP 2004, LNCS 3132 pp. 452-453, Saint Malo, France.
  2. L. Bortolussi, A. Dal Palu’, A. Dovier.
    Protein Folding Simulation in Concurrent Constraint Programming..
    In BioConcur 2004 Workshop on Concurrent Models in Molecular Biology London, 30 August 2004.
    • Mozart Code of the above paper. (updated May 28th, 2004).
  3. L. Bortolussi, A. Dal Palu’, A. Dovier, F. Fogolari.
    Agent-based Protein Folding Simulation .
    In Intelligenza Artificiale January 2005.
    • Linda + C code Code of the above paper.
  4. L. Bortolussi, A. Dovier, and F. Fogolari.
    Multi-Agent Simulation of Protein Folding.
    In Proc. of First International Workshop on Multi-Agent Systems for Medicine, Computational Biology, and Bioinformatics (25 July 2005 – Uthrect, The Netherlands), in conjunction with AAMAS’05.
  5. F. Fogolari, L. Pieri, A. Dovier, L. Bortolussi, G. Giugliarelli, A. Corazza, G. Esposito, P. Viglino.
    Scoring predictive models using a reduced representation of proteins: model and energy definition.
    BMC Structural Biology 7:15, March 23th, 2007.
  6. Luca Bortolussi Agostino Dovier Federico Fogolari.
    Agent-based Protein Structure Prediction (draft)
    Multiagent and Grid Systems, IOS Press, Vol 3, No. 2, 2007.
  7. A. Dal Palu’, A. Dovier, F. Fogolari, and E. Pontelli.
    Constraint based protein fragment assembly.
    In BIO-LOGICAL 2009 Satellite workshop of the AI*IA 2009. Reggio Emilia, Dec. 12, 2009.
  8. A. Dal Palu’, A. Dovier, F. Fogolari, and E. Pontelli.
    CLP-based protein fragment assembly. (Draft)
    Theory and Practice of Logic Programming, special issue dedicated to ICLP 2010. 10(4-6): pp 709-724, July 2010. Material and Code for 1 and 8

Some invited talks

Comments are closed.