This paper presents a learning approach for detecting nematocysts in Scanning Electron Microscope (SEM) images. The image dataset was collected and made available to us by biologists for the purposes of morphological studies of corals, jellyfish, and other species in the phylum Cnidaria. Challenges for computer vision presented by this biological domain are rarely seen in general images of natural scenes. We formulate nematocyst detection as labeling of a regular grid of image patches. This structured prediction problem is specified within two frameworks: CRF and HC-Search. The CRF uses graph cuts for inference. The HC-Search approach is based on search in the space of outputs. It uses a learned heuristic function (H) to uncover high-quality candidate labelings of image patches, and then uses a learned cost function (C) to select the final prediction among the candidates. While locally optimal CRF inference may be sufficient for images of natural scenes, our results demonstrate that CRF with graph cuts performs poorly on the nematocyst images, and that HC-Search outperforms CRF with graph cuts. This suggests biological images of flexible objects present new challenges requiring further advances of, or alternatives to existing methods.