The task of computing molecular structure from combinations of experim
ental and theoretical constraints is expensive because of the large nu
mber of estimated parameters (the 3D coordinates of each atom) and the
rugged landscape of many objective functions. For large molecular ens
embles with multiple protein and nucleic acid components, the problem
of maintaining tractability in structural computations becomes critica
l. A well-known strategy for solving difficult problems is divide-and-
conquer. For molecular computations, there are two ways in which probl
ems can be divided: (1) using the natural hierarchy within biological
macromolecules (taking advantage of primary sequence, secondary struct
ural subunits and tertiary structural motifs, when they are known); an
d (2) using the hierarchy that results from analyzing the distribution
of structural constraints (providing information about which substruc
tures are constrained to one another). In this paper, we show that. th
ese two hierarchies can be complementary and can provide information f
or efficient decomposition of structural computations. We demonstrate
five methods for building such hierarchies-two automated heuristics th
at use both natural and empirical hierarchies, one knowledge-based pro
cess using both hierarchies, one method based on the natural hierarchy
alone, and for completeness one random hierarchy oblivious to auxilia
ry information-and apply them to a data set for the procaryotic 30S ri
bosomal subunit using our probabilistic least squares structure estima
tion algorithm. We show that the three methods that combine natural hi
erarchies with empirical hierarchies create decompositions which incre
ase the efficiency of computations by as much as 50-fold. There is onl
y half this gain when using the natural decomposition alone, while the
random hierarchy suggests that a speedup of about five can be expecte
d just by virtue of having a decomposition. Although the knowledge-bas
ed method performs marginally better, the automatic heuristics are eas
ier to use, scale more reliably to larger problems, and can match the
performance of knowledge-based methods if provided with basic structur
al information.