Structural biology has witnessed an unprecedented influx of mathematical and computational techniques over the past three decades. These techniques have transformed research in a field that has become increasingly data-driven. As part of this revolution, optimization techniques are now used routinely to solve problems in structure elucidation and the study of structure-function relationships. However, many fundamental problems in this field remain largely unsolved. We present some of the challenges and opportunities in biological informatics, and review recent progress toward the solution of problems in the deciphering of protein structures, as well as the comparison and classification of known protein structures.