The optimization problem that arises for protein structure determination is undergoing a change of perspective due to the larger importance in biology taken by the disordered regions of biomolecules and intrinsically disordered proteins. Indeed, in such cases, the algorithm convergence criterion is more difficult to set up; moreover, the enormous size of the space makes it difficult to achieve a complete exploration. The interval Branch-and-Prune (iBP) approach, based on a reformulating of the Distance Geometry Problem (DGP) and proposed few years ago, provides a theoretical frame for the fast generation of protein conformations, by systematically sampling the conformational space. When an appropriate subset of inter-atomic distances is known exactly, this worst-case exponential-time algorithm is provably complete and fixed-parameter tractable. These guarantees, however, quickly disappear as distance measurement errors are introduced. Here we propose a variant of this approach: the threading-augmented interval Branch-and-Prune (TAiBP), 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 TAiBP 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 some long-range distances. For most of the protein smaller than 50 residues and interval widthes of 20 degrees, the TAiBP approach yielded solutions with RMSD values smaller than 3 Angstroms with respect to the initial protein conformation. The efficiency of TAiBP approach for proteins larger than 50 residues will require the use of non-uniform covalent geometry, and may benefit from the recent development of residue-specific force-field.