In this paper, two programs are described (CBSIe and CBS2e). These are implemented in the parallel constraint logic programming language ElipSys. These predict protein topologies from secondary structure assignments and topological folding rules (constraints). These programs illustrate how recent developments in logic programming environments cart be applied to solve largescale combinatorial problems in molecular biology. We demonstrate that parallel constraint logic programming is able to overcome some of the important limitations of more established logic programming languages i.e. Prolog. This is particularly the case in providing features that enhance the declarative nature of the program and also in addressing directly the problems of scaling-up logic programs to solve scientifically realistic problems. Moreover, we show that for large topological problems CBSIe was approximately 60 times faster than an equivalent Prolog implementation (CBS1) on a sequential device with further performance enhancements possible on parallel computer architectures. CBS2e is an extension of CBSIe that addresses the important problem of integrating the use of uncertain (weighted) protein folding constraints with categorical ones, through the use of a cost function that is minimized. CBS2e achieves this with a relatively minor reduction of performance. These results significantly extend the range and complexity of protein structure prediction methods that can reasonably be addressed using AI languages.