Nhs: network-based hierarchical segmentation for cryo-electron microscopy density maps

Cryo-electron microscopy (cryo-EM) experiments yield low-resolution (3-30 Å) 3D-density maps of macromolecules. These density maps are segmented to identify structurally distinct proteins, protein domains, and subunits. Such partitioning aids the inference of protein motions and guides fitting of high-resolution atomistic structures. Cryo-EM density map segmentation has traditionally required tedious and subjective manual partitioning or semisupervised computational methods, whereas validation of resulting segmentations has remained an open problem in this field. We introduce a network-based hierarchical segmentation (Nhs) method, that provides a multi-scale partitioning, reflecting local and global clustering, while requiring no user input. This approach models each map as a graph, where map voxels constitute nodes and weighted edges connect neighboring voxels. Nhs initiates Markov diffusion (or random walk) on the weighted graph. As Markov probabilities homogenize through diffusion, an intrinsic segmentation emerges. We validate the segmentations with ground-truth maps based on atomistic models. When implemented on density maps in the 2010 Cryo-EM Modeling Challenge, Nhs efficiently and objectively partitions macromolecules into structurally and functionally relevant subregions at multiple scales.