Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: An Efficient Algorithm for Polymer Sequence Design
Authors: Kleinberg, Jon
Keywords: computer science
technical report
Issue Date: Mar-1998
Publisher: Cornell University
Abstract: Polymer sequence design is a natural inverse problem to protein structure prediction: given a target structure in three dimensions, we wish to design an amino acid sequence that will fold to it. A model of Sun, Brem, Chan, and Dill casts this problem as an optimization on a space of sequences of hydrophobic (H) and polar (P) monomers; the goal is to find a sequence which achieves a dense hydrophobic core with few solvent-exposed hydrophobic residues. Sun et al. developed a heuristic method to search the space of sequences, without a guarantee of optimality or near-optimality; Hart subsequently raised the computational tractability of constructing an optimal sequence in this model as an open question. Here we answer this question by providing an efficient algorithm to construct optimal sequences; the method has a polynomial running time, and performs very efficiently in practice. We illustrate the implementation of our method on structures drawn from the Protein Data Bank, and discuss some possible extensions of the model.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
98-1671.pdf203.75 kBAdobe PDFView/Open
98-1671.ps182.1 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us