Proteins are macro-molecules involved in virtually all of life processes. Protein sequence and structure data is accumulated at an ever increasing rate in publicly-available databases. To extract knowledge from these databases, we need efficient and accurate tools; this is a major goal of computational structural biology. The tasks we consider are searching and mining protein data; we rely on protein fragment libraries to build more efficient tools. We describe FragBag – an example of using fragment libraries to improve protein structural search. To search for patterns in structure space, we discuss methods to generate efficient low-dimensional maps. In particular, we use these maps to identify patterns of functional diversity and sequence diversity. Finally, we discuss how to extend these methods to protein sequences. To do this, one needs to predict local structure from sequence; we survey previous work that suggests that this is a very feasible task. Furthermore, we show that such predictions can be used to improve sequence alignments. Namely, protein fragments can be used to leverage protein structural data to improve remote homology detection.