A protein conformational alphabet refers to the discretized states of the three-dimensional segmental structure of protein backbones. Here a letter corresponds to a cluster of combinations of three angles formed by
pseudobonds of four contiguous residues, and our alphabet consist of 17 letters obtained by clustering based on the probability distribution of these angles. A substitution matrix called CLESUM has been derived from an alignment database of representative structures to measure both evolutionary and geometrical similarity between any two such letters. A structural fragment is then mapped to a string, and two strings with their CLESUM score being higher than a preset threshold form a similar fragment pair (SFP). The search for SFPs by string comparison is fast. Furthermore, CLESUM scores reflect the importance of SFPs to structure alignment, and then the search space can be significantly reduced. A fast tool for pairwise alignment called CLePAPS is developed by collecting as many spatially consistent SFPs as possible. Extending the concept of SFPs to that of similar fragment blocks for multiple structure alignment leads to a fast tool for multiple structure alignment called BLOMAPS. Both CLePAPS and BLOMAPS are tested on ensembles of various structures. They are reliable, and about two or three orders faster than some well-known algorithms.