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 (*i*BP)
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 *i*BP 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.