BSAlign: Rapid Detection of
Ligand-binding Sites inProtein Structures
Zeyar Aung & Joo Chuan Tong
Data Mining Department
Institute for Infocomm Research, A*StarSingapore

19th International Conference on
Genome Informatics (GIW 2008)

OutlineProblem Definition
Motivation
Existing Methods
Out Proposed Method: BSAlign
Graph Representation
Detection of Similar Binding Sites

Experimental Results
Future Work and Conclusion

Problem Definition

Proteins and Ligands
Protein:Physical basis oflife.
Performs vitalfunctions in cells.
Amino acidsequence folded into
3D structure.

Ligand:A specific chemical compound that binds to a specific protein to form acomplex.
Can inhibit, promote, or alter the function of the receptor protein.

Ligand-binding Site
The region in the receptor protein where the ligand binds.

Ligand-binding Site Detection
Input:
1.

Protein structure A withligand L bound to it (i.e. aknown protein-ligandcomplex).

2.

Target protein structure B
to which ligand L issuspected to be bound.

Output:
The potential binding siteof L in B that is similar tothat of L in A.

Motivation

Ligand-binding site detection isuseful for:Protein function prediction
Proteins that binds to the same ligand tends to have similarfunctions.

Drug discovery
New drug target identification
Generation of targeted drug leads like inhibitors
Side-effect prediction, etc.

Existing Methods

Generic Structure Comparison
Methods
CE, DALI, SSAP, etc.
Purely geometrical; does not take physicochemical
properties into account.
Sequential alignment.
Not suitable for the task of binding site detection.

Dedicated Binding Site Detection
Methods
Graph-based
ASSAM (pseudo-atoms, sub-graph isomorphism)eF-site, Cavbase (pseudo-centers, sub-graphisomorphism)
SiteEngine (pseudo-centers, geometric hashing)

Fingerprint-based
SiteAlign (cavity fingerprint, fast comparison)

FasterLimitations of existing methods:
Graph-based Methods
Use sub-residue level of representation (pseudo-atoms orpseudo-centers).
Accurate but slow.

Fingerprint-based Methods
Concise representation and time-efficient comparison.
Fast, but not accurate.

Our objective:
To develop a ligand-binding site detection methodthat is both accurate and fast.

Our Proposed Method

BSAlign = Binding Site AlignerProtein Structure as Graph

Vertex: each residue is a vertex.
Edge: two vertices are connected if are at most 15Å
apart.

Vertex and Edge Labels
Vertex labels (for residues)
1.

Solvent accessibility (%)

2.

Physicochemical property (non-polar, polar, aromatic, positive,negative)

3.

Secondary structure type (helix, sheet, loop)

Edge labels (for relationship between two residues)
1.

Distance between CA atoms of two residues

2.

Angle between CA-CB vectors of two residues

DSSP Algorithm is used to calculate the solvent accessibilities
and the secondary structures.

Detection of Similar Binding Sites
Represent both the query binding site and the target protein
structure as graphs.
Find the largest common portions in two graphs (maximumcommon sub-graph isomorphism).

The larger the common sub-graph the more similar thetwo input structures are.

Maximum Common Sub-graph
Isomorphism

Edge-Product Graph
Transform the two input
graphs (binding site andone for target structure)
into a single edge-productgraph.
The resultant edge-productgraph depends on thecompatibilities of vertices
and edges in two input
graphs.

Edge-Product Graph

Vertex and Edge Compatibilities

SA = Solvent accessibility; PT = Physicochemical type;
SS = Secondary structure type

DC = Distance between CA atoms;
AN = Angle between two CA-CB vectors

Maximum Clique Detection
Find the maximum clique (fully-connected sub-graph) in theedge-product graph.
The maximum clique corresponds to the maximum commonsub-graph.
CLIQUER algorithm (Helsinki University of Technology) isused.

Auto-tuning of Parameters
Clique detection is a time-consuming process.
If the edge-product graph is too big, the detection ofthe maximum clique in it is very slow.
Iteratively re-construct the edge-product graph withstricter vertex and edge compatibility parameters eachtime.
Stop when the number of edges is in the edge-productgraph becomes less than 1 million.

Mapping of Matching Edge Pairs into
Matching Vertex Pairs
Each vertex in the maximum clique of the edge-product graph is a pairof edges of the original graphs that are matching.
Matching edge pairs are mapped into matching vertex pairs (i.e.
alignment of residues) using the Hungarian algorithm for optimalassignment.

Refinement and Scoring
Scoring Function:

RMSD (root-mean square deviation) is calculated by superimposing thematching (aligned) residues of one structure onto another.
The initial alignment is iteratively refined by removing the furthest residue
pair form the superimposed structures and thenre-superimposing the remaining structures.
Stop the refinement when the alignment score cannot be furtherimproved.

Overall ProcessExperimental Results

Data Set
Shulman-Peleg et al. (J. Mol. Biol., 2004)
126 proteins: 34 adenine-binding proteins + 92 other proteinsExperiment
Query binding site: ATP-binding sites of protein 1atp.
Target proteins: 126 proteins.
Compare the query binding site against the target
proteins one-by-one.
Rank those 126 proteins by their alignment scores.

15 Highest Ranking Proteins

Interpretation of Results
9 out of 15 (60%) of the highest ranking proteins are
the adenine-binding proteins (bound to adeninecontaining compounds like ATP, ANP, and AP5).
BSAlign provides same level of accuracy as a stateof-the-art method called SiteEngine (Shulman-Peleget al., J. Mol. Biol., 2004).
Among these 9 adenine-binding proteins, 8 are
also reported by SiteEngine.

ExampleATP-binding sites of 1atp and 1csn:
No. of aligned residue = 10; RMSD = 0.48Å.

Running Time
Platform: PC with Pentium D 3.2GHz CPU and 2GB
running Linux.
1atp x 126 proteins
BSAlign: 871 seconds (14 minutes and 31 seconds)
SiteEngine: 12,010 seconds (3 hours, 18 minutes, and 10
seconds)

BSAlign is about 14 times faster than SiteEngine
while offering the same level of accuracy.

Conclusion and Future Works

Conclusion
Ligand-binding site detection is an important problem inprotein function prediction and drug discovery.
We have proposed a new binding-site detection method calledBSAlign .
BSAlign employs a residue-based graph-representation andmaximum common sub-graph isomorphism to detect thesimilarity of the binding sites.
BSAlign is 14 times faster than a state-of-the-art method called
SiteEngine while offering the same level of accuracy.
The efficiency contribution of BSAlign can be very usefulfor speed-critical applications like drug discovery.

Future Works
To evaluate BSAlign with a larger and more diverse data
set in order to ascertain its accuracy performance.
To try out a different sub-graph isomorphism model byusing the vertex-product graphs.

Acknowledgement
Dr Joo Chuan Tong (PI, Molecular Design Group, Institutefor Infocomm Research)
Dr See-Kiong Ng (Department Head, Data Mining
Department, Institute for Infocomm Research)Thank you all for listening.
Any questions?