(1) The DOMINO optimizer is illustrated with the scoring function F of 8 variables {y_i} composed of a sum between 3 single body terms {α_i} and 11 pairwise terms {β_{i, j}}. The scoring function is encoded in the graphical model G. (2) (I) Decomposition of the graphical model results into a junction tree T 23; 24. The graphical model is first triangulated; a graph is triangulated if there are no cycles with more than three edges without a chord (a chord is an edge connecting two non-adjacent nodes in a cycle). The triangulation procedure adds edges (dotted lines) to the graphical model until no cycle is chordless. The triangulated graphical model is then converted into a complete subset graph. The nodes of the complete subset graph are maximum cliques in the triangulated graphical model (gray circles); a maximum clique is a sub-graph whose nodes are connected directly to each other and are not all part of another clique. The weight of an edge in the complete subset graph is the number of the shared variables between the adjacent subsets, as indicated; edges of weight zero are not shown. Next, the junction tree is the maximum spanning tree of the complete subset graph; a maximal spanning tree of a graph spans all of the nodes without cycles, using a subset of the original edges with the maximal sum of their weights. (II) The sampling space of each variable is discretized. (III) Finally, the globally optimal solution of F is gathered from enumerated subset states by passing messages between subset nodes. The numbers on the edges indicate a valid sequence of message passing.

The MultiFit algorithm is illustrated using an assembly between models of Rpb1 (red), Rpb2 (yellow), ARPC1 (light green), ARPC2 (blue), ARPC3 (gray), ARPC4 (dark green), and ARPC5 (purple) (PDB entry 1tyq). The component – template sequence identities and Cα RMSDs are indicated. The input to MultiFit is the assembly density map (grey mesh) and the atomic structures of the individual components (top left). The output is a ranked list of assembly models that optimize the MultiFit scoring function (one model is shown on bottom right). (1) The anchor points (the 7 labeled nodes) are constructed for the input density map by QVOL; the 9 grey edges indicate pairs of anchor points that are sufficiently close to allow components placed in their vicinity to interact with each other. (2) The sampling space of component placements is discretized by fitting each of the 7 components around each of the 7 anchor points (regions), and selecting a number of top-ranking placements for each component in each region; the small colored spheres indicate placement centroids. (3) The optimal combination of component placements is found by optimizing the scoring function S for each mapping of components to anchor points using DOMINO. (3.1) For efficiency, we replace the enumeration by a branch-and-bound procedure that eliminates some of the mappings and makes use of partial results. In the branch stage, we first decompose the anchor graph into an anchor junction tree using DOMINO’s decomposition algorithm (Fig. 1). The top 60% mappings of components to anchor points for each subset of anchor points (partial mappings) are found and stored by iterating over all possible partial mappings; the color of the circle indicates which component is mapped to the anchor point. The partial mappings are scored by partial scoring function S including only the terms involving the mapped components. Complete mappings consistent with the stored partial mappings are generated efficiently with a hashing procedure (not described). (3.2) Next, for each of these complete mappings, the optimal combination of placements for the 7 components is found by DOMINO; the color of the solid circles in the component junction tree indicates the component mapped to the corresponding anchor point in the anchor junction tree. The molecular model shown has a mapping score of 0 and the rank of 10. (4) The top 20 scoring coarse models are further refined. A refined sampling space is generated for each coarse configuration by docking pairs of its interacting components and selecting only those placements that are approximately consistent with the initial coarse configuration. (5) DOMINO is applied again to find the optimal combination of placements for the 7 components; the molecular model shown has a mapping score of 0 and the rank of 4.

(a) An assessment of the final model with the mapping score of 0. The model has the 4^th smallest value of the scoring function S (the 4^th model in (b)). The modeled and reference placements of the individual components are compared (Results); the corresponding placement scores are indicated below each comparison. (b) Five top ranked models for Arp2/3. The atomic representations of the models are displayed in the top row. The bottom row shows the centroid and the rotation axis for each component; the corresponding rank, the mapping score, the configuration score, and the assembly placement score are indicated below each model.