The protein folding problem represents one of the most challenging and potentially rewarding problems in computational biology. This problem can be posed as, "Given a primary amino acid sequence of a protein, how does this protein fold into its active three-dimensional structure?" One approach to solving this problem results from the alignment of an unknown protein structure to a homologous protein with an experimentally-determined structure. Two novel mixed-integer linear programming models and an integer linear programming model have been developed to rigorously address the global pairwise sequence alignment problem. The important components of these model formulations are (i) conservation constraints, (ii) a rank-ordered list of alignments, and (iii) pairwise interaction scores with optimality guarantees.

The prediction of contacts between residues within a protein is useful to reduce the conformational space that must be searched by structure prediction algorithms. Three modeling contributions in this thesis work have addressed the contact prediction problem for (i) globular, α-helical bundle proteins, (ii) membrane, α-helical bundle proteins, and (iii) proteins with α/β structure. All three of these problems are addressed using mixed-integer linear programming techniques and are validated on a variety of test proteins. The development of these low distance contacts can provide additional distance restraints for first principles approaches to the tertiary structure prediction problem for both globular and membrane proteins.

The reduction of the conformational space of a protein was further explored in an investigation of general dihedral angle and distance bounding strategies. The protein tertiary structure prediction problem is then formulated as the minimization of an atomistic-level force field subject to constraints from contact predictions and other general bounding strategies. This problem was addressed by the development of a hybrid optimization algorithm that combines (i) the αBB deterministic optimization approach, (ii) the conformational space annealing algorithm, (iii) torsion angle dynamics methods, (iv) rotamer optimization algorithms, (v) sequential quadratic programming methods, and (vi) a parallel implementation. This hybrid algorithm was tested and validated with (i) test proteins from the literature, (ii) α-helical bundle proteins with contact predictions, (iii) blind protein structure predictions, and (iv) NMR structure prediction and refinement examples.