A theoretical basis for the alignment of a protein sequence to a set of protein structure templates is presented, based on a Bayesian statistical analysis. The optimal Hamiltonian for this threading is closely related to the Hamiltonian optimized for molecular dynamics based on spin-glass theory. The Bayesian theory provides the optimal penalty functions for insertions and deletions in the alignment, which can be put in the form of a chemical potential. In contrast to standard methods for determining gap penalties, these penalties involve the logarithm of the probability distribution of gaps in alignments against correct templates as compared to the probability distribution of gaps in alignments against random templates, as determined self-consistently. Sequences of unknown proteins can be aligned to known protein structures, identifying similar structural motifs and generating reasonably correct alignments.