| Scientists and engineers have long been interested in understanding protein structures and designing protein sequences with desired functions. Predicting the structure of a protein sequence, known as the protein folding problem, is one of the most important problems in biology. The accuracy of structure prediction methods is regarded as an excellent index of the current understanding of how proteins fold. The reverse problem, that of designing a sequence with a conceived structure, is known as the protein design problem, and has immediate application in enzyme design and drug development. Successful protocols for protein design have already altered modern agriculture, biology, bioengineering, and pharmaceutical industry, and will continue to affect our ability to exert major influence on human life in the coming future.;The first part of this dissertation focuses on the protein side-chain conformation problem. Finding the protein side-chain conformation with minimal energetic level requires solving a large-scale discrete optimization problem, which is known to be very challenging. By utilizing graph-theory and constraint programming, we have developed a residue-rotamer-reduction algorithm that exploits the underlining mathematical structures of the problem. Consequently, large problem instances with several thousand residues are solved routinely on desktop computers within minutes, which would otherwise require orders of magnitudes more computational resources by previous algorithms.;The second part of this dissertation concentrates on the protein contact map overlap maximization problem, which is one of the most robust approaches for protein structure alignment. By incorporating problem-specific reduction schemes within a generic branch-and-bound framework, we have developed a branch-and-reduce algorithm and have solved many interesting instances of this problem for the first time. The algorithm also returns alignments comparable to those produced manually by experts, and therefore permits development of high-throughput techniques for structure alignment.;The last part of this dissertation centers on combinatorial library design, which is a promising protein engineering method. Despite the fact that several mathematical models have been proposed recently and shown great promise, little is known about their theoretic properties. We have discovered several important properties, and shown how to exploit these results to design powerful algorithms. |
