SOLVING LARGE COMBINATORIAL PROBLEMS IN MOLECULAR-BIOLOGY USING THE ELIPSYS PARALLEL CONSTRAINT LOGIC PROGRAMMING SYSTEM

Many areas of scientific endeavour can be characterized as the attempt to provide a consistent interpretation of a broad range of heterogene ous data and theories. In the area of protein structure prediction, fo r example, there are many types of diverse mutually constraining data and theories of protein structural organization that need to be integr ated in order to produce a single consistent prediction (or set of pre dictions) of the protein structure from the experimentally derived ami no acid sequence data. Understanding the role and function of proteins in the control of cell growth is an important part of contemporary ca ncer research. Protein structure prediction is immensely (combinatoria lly) complex, and traditional computational approaches to problems suc h as this have been based on the ''generate and test' paradigm in whic h hypotheses are first generated and then tested against any relevant constraints. In this paper we demonstrate the benefits of a new approa ch to solving large constrained combinatorial problems which uses the 'constrain-and-generate' paradigm and the ElipSys parallel constraint logic programming system. In ElipSys, constraints are used for a prior i pruning of the search tree while parallelism enhances the efficiency of the remaining search. Initial results show several orders of magni tude increase in performance over a sequential logic programming (Prol og) approach. The improved performance can be attributed to the comple mentary actions of the constraint handling and support for parallelism in the ElipSys runtime system. Taken together, the additional perform ance and new knowledge representation techniques made possible using E lipSys significantly extend the range and complexity of scientific pro blems that can be addressed using logic programming languages.