**Background**: The determination of protein structures satisfying distance constraints is an important
problem in structural biology. Whereas the most common method currently employed is simulated annealing,
there have been other methods previously proposed in the literature. Most of them, however, are designed
to find one solution only.

**Results**: In order to explore exhaustively the feasible conformational space, we propose here an
interval Branch-and-Prune algorithm (iBP) to solve the Distance Geometry Problem (DGP) associated to
protein structure determination. This algorithm is based on a discretization of the problem obtained by
recursively constructing a search space having the structure of a tree, and by verifying whether the
generated atomic positions are feasible or not by making use of pruning devices. The pruning devices used
here are directly related to features of protein conformations.

**Conclusions**: We described the new algorithm iBP to generate protein conformations satisfying distance
constraints, that would potentially allows a systematic exploration of the conformational space. The algorithm
*i*BP has been applied on three alpha-helical peptides.