When training data are available, supervised techniques can be applied to multispecies genomic alignments to investigate patterns that are predictive of function. These patterns, or “words”, can capture sequence composition, motifs, and evolutionary relations among species; for some types of functional elements they are still poorly understood – and thus need to be learned. However, in most cases the available training data is limited in comparison to the dimension of the space of all possible words, creating serious over-fitting problems. We have developed a computational strategy, called ESPERR (evolutionary and sequence pattern extraction through reduced representations), which uses training examples to produce encodings of multispecies alignments into reduced forms tailored to the prediction of chosen classes of functional elements. ESPERR employs a phylogeny-guided clustering followed by a heuristic optimization based on classification performance to create a reduced alphabet in which words are spelled, and uses variable order Markov models to adapt word length. Log-odds scores built upon such models can achieve a remarkable predictive performance in several applications; in particular, we describe the ESPERR Regulatory Potential score, which discriminates regulatory regions of the human genome from neutral sites with excellent accuracy.