Systematic domain based structure alignments at the RCSB PDB

At the RCSB PDB web site we habe been providing pre-calculated and systematic protein structure alignments already for about two years. Every week we run systematic structure alignments for newly released proteins across a representative subset of the database and try to identify related proteins based on their 3D shape.

This week we have released a major upgrade to those efforts. Our pre-computed alignments are now using domain information to split protein chains into smaller subunits. We introduced this change because many proteins are built of more than just one domain. In that case our previous results were a bit unclear in the sense that results for any of the domains were displayed together and that made the data more difficult to compare and interpret.

The new domain based procedure is using the SCOP domain assignments where available to define how to break up protein chains. If the structures are too new to be annotated by SCOP (like all newly released proteins), then we use a software called ProteinDomainParser to define domains based on geometric criteria. Even if the algorithm sometimes defines a break point that might not be the same what SCOP would define, it is still interesting if you find structural neighbors with such fragments of proteins.

In addition, this release of the RCSB PDB web site also provides a new display of protein chains and how different sources annotate protein domains (see the image above). This domain summary shows SCOP domains, ProteinDomainParser domains and Pfam domains. Here an example for  a Cyclodextrin glycosyl transferase (3BMV) from Thermoanerobacterium thermosulfurigenes. It is composed of four domains, which are identified by all of the three data sources.

New Paper: Precalculated Protein Structure Alignments at the RCSB PDB website

Bioinformatics just made our latest paper available as an early preview:
Precalculated Protein Structure Alignments at the RCSB-PDB website

ABSTRACT
Summary: With the continuous growth of the RCSB Protein Data Bank (PDB), Berman et al. (2000), providing an up-to-date systematic structure comparison of all protein structures poses an ever growing challenge. Here we present a comparison tool for calculating both 1D protein sequence and 3D protein structure alignments. This tool supports various applications at the RCSB PDB website. First, a structure alignment web service calculates pairwise alignments. Second, a stand-alone application runs alignments locally and visualizes the results. Third, pre-calculated 3D structure comparisons for the whole PDB are provided and updated on a weekly basis. These three applications allow users to discover novel relationships between proteins available either at the RCSB PDB or provided by the user.

Availability and Implementation: A web user interface is available at
http://www.rcsb.org/pdb/workbench/workbench.do. The source code
is available under the LGPL license from http://www.biojava.org.
A source bundle, prepared for local execution, is available from
http://source.rcsb.org

UPDATE: the link below should provide free access:
Read the full paper here

Getting the most out of the Combinatorial Extension (CE) algorithm

The CE algorithm is a frequently used algorithm for protein structure alignment. We have recently ported the CE algorithm from C to Java and made the new implementation available through BioJava project. It is run as part of the Protein Comparison Tool at the RCSB PDB web site. This was a good opportunity to learn a few hidden aspects of the original implementation and re-consider some of the parameter choices that have been take for the original code. Here a quick summary of how CE works and how to get the most out of it.

CE essentially has two main steps:

1. Finding Aligned Fragment Pairs (AFPs) between the two protein structures that share similarity. This step in most cases is quite quick, however this only provides a rough alignment as a result which needs refinement.
2. The alignment optimization steps is the slow part of the algorithm. It iteratively tries to extend the initial alignment while staying below a certain RMSD threshold.

So how does these two steps work in detail? Today we will look at Step 1:


Step 1: Finding AFPs:This step starts with calculating Matrices of intra-molecular distances withing each of the two proteins. These are matrices that describe the distances within a protein and they look something like this:

Here you can see the two matrices, on the left for the alpha chain of Hemoglobin, and on the right side for the beta chain of Hemoglobin. You can view their alignment at the RCSB PDB web site.

As you can see the two chains are very similar. Their pattern of intra-molecular distances looks similar, too. The regions that are colored indicate close proximity in space. Can you spot the helices?
There are a few different ways to compare such distance matrices. In order to identify the AFPs, CE takes the approach to "slide a window" over each of the matrices and tries to find regions where the two proteins looks similar.

This is how it is calculated: First all distances for fragments of size 8 are calculated and the difference of Distances is

This can be done by calculating differences of distances for each fragment of length winSize, which is one of the parameters that can be sent to CE and which is by default set to a length of 8.

The original CE paper has a table on the impact of this parameter. Here you can see how different values for winSize (here called Fragment size m) affect the final RMSD, alignment length and calculation time.It is impressive how much CPU speed has improved since back in those days: Now the alignment shows up almost instantly on my screen. However back then they only had a 248 Mhz CPU and you can see in the table above how many seconds one had to be patient back in 1998.

I tried to reproduce this table with the current implementation, but the numbers don't show up exactly the same. There were a few follow up publication on the algorithm during which this step got improved. The trace step has now some RMSD threshold parameters which make sure that the RMSD between the traces stay within limits.

In this table the internal numbers after the Step 1: As you can see the main effect is on the nr. of traces that are being detected.

winSize	nr traces	RMSD after initial trace
4	2,662,211	4.4
6	1,858,380	3.8
8	1,158,327	4.6
10	891,807	4.3
12	847,802	4.3
16	758584	4.0
24	261,290	5.0
36	17395	4.6

To come back to the differences of distances between the fragments of length winSize: at this stage the difference of distance matrix looks like this:

Each dot on the matrix corresponds to the start of a fragment and color corresponds to closely similar fragments. As you can see there are plenty of regions that have similar fragments, and the fragments come in groups.

The next step, optimizing the alignment, will be discussed some other time...

New Structure Alignment Features at the RCSB PDB Web Site

With the upcoming new release there will be a couple of new protein structure alignment related features:

*) The RCSB PDB web site is providing a structure alignment service. This service can calculate structure alignment on the server side. It also caches all alignments. This means if you come back the next day you can view the same result quickly.

Preview the new alignment service here:
http://betastaging.rcsb.org/pdb/workbench/workbench.do





*) Circular Permutations (CP) in proteins are difficult for alignment algorithms to detect since they depend on the sequence order. These permutations are re-arrangements of the sequence, resulting in different amino acid connectivity, while conserving the overall 3D shape of a protein. Spencer Bliven has extended the Java version of CE and introduced support for the detection of such permutations. This is achieved by working with an internal representation of the proteins that allows to identify alignments across N and C termini. Since this slows down the calculation about three times, the detection of CP is optional.

View an Example of a Cirularly Permutated protein structure alignment

Latest release of RCSB PDB web site contains all vs. all protein structure alignments

Last night we released the latest major version of the RCSB PDB web site. This release contains a number of exciting new features:

All vs. all protein structure alignments

* Interactive Structure Alignment Display
* Expert Mode for Protein Comparison Tool

General Site Improvements

* Home Page Layout and Customization
* OpenSearch Integration
* Resizable Viewer Applets

Query Results Page and Tabular Reports Improvements

* Bidirectional Sorting
* New Image Collage Page
* Report Table Filtering
* One-to-Many Relationships in Report Tables

Ligand Search Improvements

* Ligand Top-Bar Search
* Ligand Advanced Search
* Chemical Structure Search
* Ligand Summary Page

Testing upcoming release of all v.s. all protein structure alignment comparisons

At RCSB PDB we are currently working on an all vs. all comparison of PDB. A preliminary version of this is available from the betastaging site for public testing. e.g.:

http://betastaging.rcsb.org/pdb/explore/structureCluster.do?structureId=2W72

This is a beta site so it might not always be available or some things might not work as expected, still it should give you a pretty good impression of what is in preparation. If you want to help testing, have a look there and let me know how it goes.

Some documentation on the all vs. all procedure can be found here:

http://betastaging.rcsb.org/pdb/static.do?p=general_information/cluster/structureAll.jsp

All vs All Structure Alignments in PDB

Proteins can have various degrees of similarity. If two proteins show high similarity in their amino acid sequence, it is generally assumed that they are closely evolutionary related. With increasing evolutionary distance the degree of similarity usually drops, but proteins can still show similar function and have an overall similar 3D structure, even if the sequence similarity is low. The detection of such remote similarities is important in order to infer functional and evolutionary relationships between protein families and is a core technique used in structural bioinformatics.

For the RCSB-PDB web site I have recently been working on a new all against all comparison of all protein chains. While protein sequence comparisons can be computed quickly, the calculation of protein structure alignments is much more time consuming. So far we were computing about 140 mio. pairwise alignments in ~100.000 CPU hours on the Open Science Grid (OSG). With the help of Chris Bizon we could easily deploy our code there and I can highly recommend giving the OSG a try also for other scientists. A technical report about how we computed about 140 mio. pairwise alignments in ~100.000 CPU hours is available from here:

http://osg-docdb.opensciencegrid.org/cgi-bin/ShowDocument?docid=919

Protein Comparison Tool

In the recent months I spent some time developing the new RCSB PDB Protein Comparison Tool (you can see an example for it on the right-hand menu of this blog).

In particular I spent a lot of time porting the CE and FATCAT algorithms from C to Java and developing a new user interface. Check out the latest version at http://betastaging.rcsb.org/pdb/workbench/workbench.do . (E.g. try to align 4HHB chain A and 4HHB chain B ).

Having the algorithms in Java opens the door for a number of nice applications. It is now possible to launch the structure comparison application with a single mouse click using the Java Web Start technology.