The optimization approaches classically used during the determination of protein structure encounter various difficulties,
especially when the size of the conformational space is large. Indeed, in such a case, algorithmic convergence criteria are
more difficult to set up. Moreover, the size of the search space makes it difficult to achieve a complete exploration. The
*interval* branch-and-prune (*i*BP) approach, based on the reformulation of the distance geometry problem (DGP)
provides a theoretical frame for the generation of protein conformations, by systematically sampling the conformational
space. When an appropriate subset of interatomic distances is known exactly, this worst-case exponential-time algorithm
is provably complete and fixed-parameter tractable. These guarantees, however, immediately disappear as distance measurement
errors are introduced. Here we propose an improvement of this approach: threading-augmented interval branch-and-prune (TA*i*BP),
where the combinatorial explosion of the original iBP approach arising from its exponential complexity is alleviated by
partitioning the input instances into consecutive peptide fragments and by using self-organizing maps (SOMs) to obtain
clusters of similar solutions. A validation of the TA*i*BP approach is presented here on a set of proteins of various
sizes and structures. The calculation inputs are a uniform covalent geometry extracted from force field covalent terms,
the backbone dihedral angles with error intervals, and a few long-range distances. For most of the proteins smaller than
50 residues and interval widths of 20 degrees, the TA*i*BP approach yielded solutions with RMSD values smaller than
3 Angstroms with respect to the initial protein conformation. The efficiency of the TA*i*BP approach for proteins
larger than 50 residues will require the use of nonuniform covalent geometry and may have benefits from the recent
development of residue-specific force-fields.