We develop a novel method for solving the local alignment problem of protein structure in an accurate and efficient manner at the amino acid level, based on a decomposition technique.  We define the structure alignment as a multi-objective optimization problem with both integer and continuous variables, i.e., maximizing the matching number of aligned atoms and minimizing their root mean square distance.  A very efficient algorithm is developed for optimizing the problem.  By controlling a single distance-related parameter, theoretically we can obtain a variety of optimal alignments corresponding to different optimal matching patterns, i.e., from a global alignment with a large matching portion to a local alignment with a small matching portion.  We show that the number of variables in our algorithm increases with atom numbers of protein pairs in almost a linear manner.  In addition to solid theoretical background, numerical experiments demonstrated significant improvement of the approach over the existing methods in terms of both quality and efficiency.