1 Structure Detection by Deep Learning

To start the structure modeling procedure, the probability that phosphate, sugar, and base locate at each grid position of an input density map is computed by a deep neural network. The input map is scanned with a 643 Å^3 box along the map grid of an interval of 1 Å by moving with a stride of 16 Å. The box takes density values at each grid point in the box as input features and outputs the probabilities that heavy atoms of protein, sugar, phosphate, and base for each grid point. The network architecture consists of two networks, stage 1 and stage 2, where the stage 2 network further refines the initial stage 1 output by considering the probabilities assigned by the stage 1 network. The network architecture is shown above.

2. Structure Node Clustering

To trace the backbone from detection results, we first cluster grid points with detected structure classes to choose representative nodes and connecting representative nodes classified as sugar to construct backbone structure candidates. The clustering aims to reduce the number of grid points and to identify representative points for a structure class. Clustering was applied for all but protein class (i.e. seven classes in total; sugar, phosphate, base, and four bases, which are A, C, G, U/T).

3. Backbone Tracing

First, the representative nodes of the sugar prediction are connected into a graph. Only sugar nodes were used to trace the backbone since the detection accuracy for sugar was higher than phosphate and considering sugar was sufficient for tracing. Edges are connected between sugar nodes depending on the sugar probability of the nodes and the distance between them. Then, we traced backbones of nucleic acids with a Vehicle Routing Problem (VRP) solver. The VRP is similar to the Traveling Salesman Problem (TSP), but it uses multiple “vehicles” instead of a single “salesman” to connects edges in a graph while minimizing connecting costs. We found VRP is more suitable since a map may include multiple nucleic acid chains.

4 Sequence Assignment

Here we assign nucleic acid sequences to sugar nodes in the paths. This process has two sub-steps, assigning base sequence fragments to paths, and the assembly of assigned sequences. In the initial base sequence assignment, sugar backbone paths are cut into segments of 20 representative nodes by a sliding window with a stride of 2, which are aligned with the nucleic acid sequence to identify the top 20 candidate sequence fragments using a dynamic programming algorithm. Subsequently, assigned sequence fragments are assembled by a constraint programming (CP) solver, which maximizes the sum of the probability score of sugar nodes with the assigned bases while satisfying constraints that are required for consistency of overlapping path segments and nucleic acid sequences. Overall, this step can further refine the initial base assignment to further improve the base type assignment for structures.

5. Full Atom Model

Up to this step, the structure consists of the sugar backbone and base assignment to representative sugar nodes. Then, to the sugar nodes, phosphate and base nodes that are close and satisfy a distance condition are added (see Methods). Next, a full-atom nucleotide 3D structure of the standard conformation is superimposed to each triangle of sugar, phosphate, and base nodes. Finally, structure is further refined by using phenix.real_space_refine[23] on predicted RNA regions followed by all_atom_refine in Coot[13], which both refine a model structure by considering map density information.

1 Input Cryo-EM Map and Dependencies

The example input map is included here.
The dependencies of phenix and coot can be downloaded here: Phenix and Coot.