# Presentation: 002542

## Enumeration of Near-Optimal Solutions for Peptide Docking Problems

- William Hart
- Sandia National Laboratories
- _[wehart@sandia.gov](mailto:wehart@sandia.gov)_
- Bob Carr (SNL)
- Harvey Greenberg (CU Denver)
- Matthew Hart (Grand Valley State)
- Richard Forrester (Dickson College)
- Diana Roe (SNL)

## Motivation

- Protein-protein interactions are essential to virtually all cellular processes
- Proteins are macro-molecules composed of a linear chain of amino acid residues
- Proteins folds into well-defined 3D structures that determine their role in cellular processes
- Protein-protein interactions provide insight into protein function

## Overview

- Goal: provide computational tools to predict protein-protein interactions
- Impact:
- Computational analyses can limit the number of laboratory experiments needed
- Computational analysis can focus the scope of laboratory experiments
- Note: we consider computational techniques that are motivated by phage-display experimental techniques

## Overview						cont’d

- Three problems with a single mathematical representation:
- Predict the structure of a peptide
- Predict the best structure of a peptide allowing for a set of possible amino acids for each sidechain
- Predict the best amino acids for the sidechains in a peptide

## Protein-Peptide Docking

**Protein-Peptide Docking**

- Idea: study protein-protein interactions through protein-peptide docking
- Many protein-protein interactions are mediated by modular domains
- PDZ, SH3, SH2, WW, PTB, FHA
- These domains often bind to a linear stretch of the binding partner
- Impact: Peptide libraries can identify bindingsequences that can be used to searchthe genome for binding partners

- Complex of the SH3 domain from tyrosine protein kinase (green) complexed with P38(grey), with linear portion highlighted (magenta)

## Phage-Display

- Phage-display libraries: an experimental technique used to probe protein-protein binding interactions
- Libraries are typically of size 4-12 residues in length
- Libraries generate a consensus binding sequence
- Questions that can be answered by phage-display experiments:
- What are potential binding partners?
- What are the sequence specificities of these binding interactions?

## Computational Phage-Display

**Computational Phage-Display**

- Idea: predict the peptide sequence that is most likely to bind
- Predict consensus sequences
- Impact:
- Provide the same typeof information asexperimental methods
- Can be used to design areduced “focused”phage-display library(minimizes experimental costs)

## Our Approach

- Assumptions:
- Side-chain structures can be well-captured by rotamer libraries
- Rotamer libraries taken from trusted data sources (e.g. PDB)
- Discretize the structure prediction
- 2. The peptide backbone is well-constrained
- We assume that it’s fixed
- If there is flexibility, then we could consider a (small) set of alternative backbone conformations
- Objective:
- Design the peptide that is most likely to bind
- Design a peptide library containing the best peptides

## Peptide Structure Prediction

- Goal: structure prediction for a given peptide
- Decision variables:
- Peptide-Protein Energy
- Amber scoring function
- Generalized Born continuum solvation calculation
- A peptide structure is defined by a set of rotamer choices

## An IQP Model

- Note: many of the energies are negative, so this IQP is not convex

## An ILP Formulation

- Note: this model can be refined to exploit data sparsity
- Note: similar models have been derived by several other authors...

## Integer Programming Solvers

- Solve linear IPs with branch-and-bound
- Branch to fix variables in subproblems
- Solvers
- Commercial: CPLEX, OSL, XPRESS
- Research: BoB, ALPS, PICO
- Performance:
- The ILP is small because peptides are typically short
- Can solve these ILPs within minutes at worst!

## Computational Phage-Display

- Method:
- Generate a bunch of (random) peptides
- Apply peptide structure prediction
- Rank peptides whose bindings were well-predicted
- Note:
- This process is inherently parallelizable
- Can generate a consensus prediction of binding affinity from the top binding peptides
- Consensus amino acid sequence
- Consensus matrix of amino acid frequency at each position

## Designing Phage-Display Experiments

- Note: to make robust computational predictions we need to consider a very wide range of peptide sequences
- Challenge: characterize the space of *interesting* peptides
- Impact: limit the cost of computational and experimental phage display experiments!
- We consider two approaches based on enumeration of near-optimal solutions

## Combinatorial Formulation 1

- Idea: combine rotamer libraries for different amino acids
- Decision variables:
- Note: this problem has the same mathematical formulation as peptide structure prediction!
- A peptide structure is defined by a set of rotamer choices
- This implicitly selects the amino acid sequence!
- Goal: enumerate near-optimal solutions and compute consensus information

## Solution Techniques

- Iterated Application of Standard IP solvers
- Add constraints to eliminate previously seen solutions
- Resolve augmented IP
- Very slow... (but maybe we could speed it up?)
- Combinatorial enumeration
- Maintain pool of near-optimal solutions
- Purge pool when improving incumbents are found
- Prune subproblems that are provably not within the enumeration tolerance(s)
- Combinatorial or IP-based bounds

## Branch-and-Bound

- Idea: apply methods develop for side chain prediction (Canutescu et al. ’03)
- Branch on variable with the fewest rotamers
- Sort rotamers by energies *E**ir*
- Simple bound:
- Pseudo-cost gradients computed to bias branching decisions
- Incumbent Generation:
- Sort rotamers with the “rotamer weight”
- Perform local minimization starting with the minimal weight rotamer for each amino acid

## Empirical Results

- Implementation with PEBBL:
- A modular C++ library for branch-and-bound (Rutgers/Sandia)
- Supports scalable parallelization
- Extended to enable enumeration of all near-optimal solutions
- Computational Experience
- Very large problems:  4M+ variables and constraints
- Solving for the single best point is computationally difficult
- Enumerating “enough” near-optimal solutions does not appear tractable

## Combinatorial Formulation 2

- Idea: focus on peptide design alone
- Method:
- Assign amino acids energies based on a Boltzman-weighted average of their corresponding rotamers
- The decision variables are now simply the choice of amino acid at each position
- The solver methodology has not changed!
- Observations:
- Boltzman-weighted statistics are well-motivated because the peptide-protein interactions are dominant
- This formulation should find more “robust” peptide sequences

## Empirical Results

- Peptide Design
- The best design can be quickly found (within a second)
- Near-optimal solutions are easy to find
- Peptide-Protein interactions are the dominant energies
- The top 1000 solutions can be generated within a few seconds

## Using Consensus Information

- Limit the scope of phage-display experiments
- Only include amino acids at sites where they appear in near optimal solutions
- Identify peptide docking candidates
- Use a consensus matrix to score peptide sequences with an expected frequency
- Can be use to scan the genome for binding partners
- A similar approach has been taken using Boltzman energies to predict binding affinities
- We expect that consensus information will prove more stable and predictive

## Future Work

- Compare/contrast IP-based enumeration with combinatorial enumeration
- The PEBBL library is the core B&B engine for PICO
- PEBBL supports enumeration, and PICO’s cutting mechanism has been augmented to support IP-based enumeration
- Goal: evaluate the impact of strong bounds
- Goal: evaluate IP formulations of Forrester and Greenberg for enumeration
- Design of synthetic organic compounds
- Idea: use a fixed organic skeleton that includes a finite number of peptides
- Goals:
- Design rotamer library (natural and synthetic peptides)
- Predict optimal structures

## The End

- Thanks!