  The analysis of the three-dimensional structure of proteins is an important
topic in molecular biochemistry. Structure plays a critical role in defining
the function of proteins and is more strongly conserved than amino acid
sequence over evolutionary timescales. A key challenge is the identification
and evaluation of structural similarity between proteins; such analysis can aid
in understanding the role of newly discovered proteins and help elucidate
evolutionary relationships between organisms. Computational biologists have
developed many clever algorithmic techniques for comparing protein structures,
however, all are based on heuristic optimization criteria, making statistical
interpretation somewhat difficult. Here we present a fully probabilistic
framework for pairwise structural alignment of proteins. Our approach has
several advantages, including the ability to capture alignment uncertainty and
to estimate key "gap" parameters which critically affect the quality of the
alignment. We show that several existing alignment methods arise as maximum a
posteriori estimates under specific choices of prior distributions and error
models. Our probabilistic framework is also easily extended to incorporate
additional information, which we demonstrate by including primary sequence
information to generate simultaneous sequence-structure alignments that can
resolve ambiguities obtained using structure alone. This combined model also
provides a natural approach for the difficult task of estimating evolutionary
distance based on structural alignments. The model is illustrated by comparison
with well-established methods on several challenging protein alignment
examples.
