A combinatorial toolbox for protein sequence design and landscape analysis in the grand canonical model

James Aspnes, Julia Hartling, Ming-Yang Kao*, Junhyong Kim, Gauri Shah

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


In modern biology, one of the most important research problems is to understand how protein sequences fold into their native 3D structures. To investigate this problem at a high level, one wishes to analyze the protein landscapes, i.e., the structures of the space of all protein sequences and their native 3D structures. Perhaps the most basic computational problem at this level is to take a target 3D structure as input and design a fittest protein sequence with respect to one or more fitness functions of the target 3D structure. We develop a toolbox of combinatorial techniques for protein landscape analysis in the Grand Canonical model of Sun, Brem, Chan, and Dill. The toolbox is based on linear programming, network flow, and a linear-size representation of all minimum cuts of a network. It not only substantially expands the network flow technique for protein sequence design in Kleinberg's seminal work but also is applicable to a considerably broader collection of computational problems than those considered by Kleinberg. We have used this toolbox to obtain a number of efficient algorithms and hardness results. We have further used the algorithms to analyze 3D structures drawn from the Protein Data Bank and have discovered some novel relationship s between such native 3D structures and the Grand Canonical model.

Original languageEnglish (US)
Pages (from-to)721-741
Number of pages21
JournalJournal of Computational Biology
Issue number5
StatePublished - Dec 1 2002


  • Combinatorial optimization
  • Computational hardness
  • Linear programming
  • Minimum cuts
  • Network flow
  • Protein 3D structures
  • Protein landscape analysis
  • Protein sequence design
  • The grand canonical model

ASJC Scopus subject areas

  • Modeling and Simulation
  • Molecular Biology
  • Genetics
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'A combinatorial toolbox for protein sequence design and landscape analysis in the grand canonical model'. Together they form a unique fingerprint.

Cite this