A Semidefinite Programming Approach to Side Chain Positioning with New Rounding Strategies

References

• Alizadeh F. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. (1995) 5:13–51Crossref, Google Scholar
• Alon N., Kahale N. Approximating the independence number via the Θ-function. Math. Programming (1998) 80:253–264Crossref, Google Scholar
• Althaus E., Kohlbacher O., Lenhof H.-P., Müller P. A combinatorial approach to protein docking with flexible side-chains. Proc. Fourth Annual Internat. Conf. Comput. Molecular Biol. (2000) (ACM Press, New York) 15–24Crossref, Google Scholar
• Arora S., Safra M. Probabilistic checking of proofs: A new characterization of NP. J. ACM (1998) 45:70–122Crossref, Google Scholar
• Arora S., Lund C., Motwani R., Sudan M., Szegedy M. Proof verification and hardness of approximation problems. J. ACM (1998) 45:501–555Crossref, Google Scholar
• Banner D. W., Bloomer A., Petsko G. A., Phillips D. C., Wilson I. A. Atomic coordinates for triose phosphate isomerase from chicken muscle. Biochem. Biophys. Res. Commun. (1976) 72:146–155Crossref, Google Scholar
• Benson S. J., Ye Y., Zhang X. Mixed linear and semidefinite programming for combinatorial and quadratic optimization. Optim. Methods Software (1999) 11:515–544Crossref, Google Scholar
• Bertsimas D., Ye Y., Du D.-Z., Pardalos P. M. Semidefinite relaxations, multivariate normal distributions, and order statistics. Handbook of Combinatorial Optimization (1998) 3(Kluwer Academic Publishers, New York) 1–19Crossref, Google Scholar
• Boppana R. B. Eigenvalues and graph bisection: An average-case analysis. Proc. Twenty-eighth Annual Sympos. Foundation Comput. Sci. (1987) (IEEE Computer Society Press, Washington, D.C.) 280–285Crossref, Google Scholar
• Bower M. J., Cohen F. E., Dunbrack R. L. Prediction of protein side-chain rotamers from a backbone-dependent rotamer library: A homology modeling tool. J. Molecular Biol. (1997) 267:1268–1282Crossref, Google Scholar
• Cornell W. D., Cieplak P., Bayly C. I., Gould I. R., Merz K. M., Ferguson D. M., Spellmeyer D. C., Fox T., Caldwell J. W., Kollman P. A. A second generation force field for the simulation of proteins, nucleic acids, and organic molecules. J. Am. Chemical Soc. (1995) 117:5179–5197Crossref, Google Scholar
• Dahiyat B. I., Mayo S. L. De novo protein design: Fully automated sequence selection. Science (1997) 278:82–87Crossref, Google Scholar
• Desmet J., De Maeyer M., Lasters I., Merz K., LeGrand S. The “dead end elimination” theorem as a new approach to the side-chain packing problem. The Protein Folding Problem and Tertiary Structure Prediction (1994) (Birkhäuser, Boston, MA) 307–337Crossref, Google Scholar
• Desmet J., De Maeyer M., Hazes B., Lasters I. The dead-end elimination theorem and its use in protein side-chain positioning. Nature (1992) 356:539–542Crossref, Google Scholar
• Donath W. E., Hoffman A. Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices. IBM Tech. Disclosure Bull. (1972) 15:938–944Google Scholar
• Dunbrack R.L., Karplus M. Backbone-dependent rotamer library for proteins: Application to side-chain prediction. J. Molecular Biol. (1993) 230:543–574Crossref, Google Scholar
• Eriksson O., Zhou Y., Elofsson A. Side chain-positioning as an integer programming problem. Proc. First Workshop Algorithms BioInformatics (2001) (BRICS, University of Aarhus, Denmark) 129–141Crossref, Google Scholar
• Feige U., Kilian J. Heuristics for finding large independent sets, with applications to coloring semi-random graphs. Proc. Thirty-ninth Annual Sympos. Foundation Comput. Sci. (1998) (IEEE Computer Society, Los Alamitos, CA) 674–683Crossref, Google Scholar
• Fourer R., Gay D. M., Kernighan B. W.AMPL: A Modeling Language for Mathematical Programming (2002) (Brooks/Cole Publishing Company, Pacific Grove, CA) Google Scholar
• Frieze A., Jerrum M. Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica (1997) 18:61–77Crossref, Google Scholar
• Fujisawa K., Fukuda M., Kojima M., Nakata K. Numerical evaluation of SDPA. (1997) . Technical report B-330, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro-ku, Tokyo 152, JapanGoogle Scholar
• Goemans M. X., Williamson D. P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM (1995) 42:1115–1145Crossref, Google Scholar
• Goldstein R. F. Efficient rotamer elimination applied to protein side-chains and related spin glasses. Biophys. J. (1994) 66:1335–1340Crossref, Google Scholar
• Gordon D. B., Mayo S. L. Radical performance enhancements for combinatorial optimization algorithms based on the dead-end elimination theorem. J. Comput. Chem. (1998) 19:1505–1514Crossref, Google Scholar
• Grötschel M., Lovász L., Schrijver A.Geometric Algorithms and Combinatorial Optimization (1993) 2nd ed.(Springer-Verlag, Berlin, Germany) Crossref, Google Scholar
• ILOG CPLEX (2000) . ILOG CPLEX 7.1. http://www.ilog.com/Google Scholar
• Karger D., Motwani R., Sudan M. Approximate graph coloring by semidefinite programming. J. ACM (1998) 45:246–265Crossref, Google Scholar
• Kohlbacher O., Lenhof H.-P. BALL—rapid software prototyping in computational molecular biology. Bioinformatics (2000) 16:815–824Crossref, Google Scholar
• Lasters I., De Maeyer M., Desmet J. Enhanced dead-end elimination in the search for the global minimum energy conformation of a collection of protein side chains. Protein Engrg. (1995) 8:815–822Crossref, Google Scholar
• Lau H. C. A new approach for weighted constraint satisfaction. Constraints (2002) 7:151–165Crossref, Google Scholar
• Lau H. C., Watanabe O., Karlsson R., Lingas A. Randomized approximation of the constraint satisfaction problem. Proc. Fifth Scandinavian Workshop Algorithm Theory (1996) (Springer, Berlin, Germany) 76–87Crossref, Google Scholar
• Leach A. R., Lemon A. P. Exploring the conformational space of protein side chains using dead-end elimination and the A* algorithm. Proteins (1998) 33:227–239Crossref, Google Scholar
• Lee C. Predicting protein mutant energetics by self-consistent ensemble optimization. J. Molecular Biol. (1994) 236:918–939Crossref, Google Scholar
• Lee C., Subbiah S. Prediction of protein side-chain conformation by packing optimization. J. Molecular Biol. (1991) 217:373–388Crossref, Google Scholar
• Lesk A. M., Brändén C.-I., Chothia C. Structural principles of α/β barrel proteins: The packing of the interior of the sheet. Proteins (1989) 5:139–148Crossref, Google Scholar
• Lovász L. On the Shannon capacity of a graph. IEEE Trans. Inform. Theory (1979) 25:1–7Crossref, Google Scholar
• Malakauskas S. M., Mayo S. L. Design, structure and stability of a hyperthermophilic protein variant. Nature Structural Biol. (1998) 5:470–475Crossref, Google Scholar
• Mueller U., Perl D., Schmid F. X., Heinemann U. Thermal stability and atomic-resolution crystal structure of the Bacillus caldolyticus cold shock protein. J. Molecular Biol. (2000) 297:975–988Crossref, Google Scholar
• Nesterov Y., Nemirovskii A.Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms (1993) (SIAM, Philadelphia, PA) Google Scholar
• Nicholls A., Sharp K. A., Honig B. Protein folding and association: Insights from the interfacial and thermodynamic properties of hydrocarbons. Proteins (1991) 11:281–296Crossref, Google Scholar
• Pierce N. A., Winfree E. Protein design is NP-hard. Protein Engrg. (2002) 15:779–782Crossref, Google Scholar
• Ponder J. W., Richards F. M. Tertiary templates for proteins: Use of packing criteria in the enumeration of allowed sequences for different structural classes. J. Molecular Biol. (1987) 193:775–791Crossref, Google Scholar
• Raghavan P., Thompson C. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica (1987) 7:365–374Crossref, Google Scholar
• Rolim J. D. P., Trevisan L. A case study of de-randomization methods for combinatorial approximation problems. J. Combin. Optim. (1998) 2:219–236Crossref, Google Scholar
• Seneta E.Non-Negative Matrices and Markov Chains (1981) 2nd ed.(Springer-Verlag, New York) Crossref, Google Scholar
• Vandenberghe L., Boyd S. Semidefinite programming. SIAM Rev. (1996) 38:49–95Crossref, Google Scholar
• Zwick U. Outward rotations: A tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems. Proc. Thirty-first Annual ACM Sympos. Theory Comput. (1999) (ACM Press, New York) 679–687Crossref, Google Scholar