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 version of RCSB web site released

The RCSB team just released the next major update of the RCSB PDB web site. Here the main features of this release:

• General Site Improvements
• Improved Layout of Query Results Page
• Latest Structures Widget
• Improved Display for Electron Microscopy Entries
• Jmol Page Visualization Features
• Structure Alignment Improvements
• Structure Alignment Service
• Support for Circular Permutations
• Molecule of the Month Improvements
• One-page Layout for Molecule of the Month
• Molecule of the Month Features Linked to Relevant Entries
• Chemical Component (Ligand) Search Improvements
• Chemical Component Results Display
• Chemical Component Search Form
• Chemical Formula Expression Search
• Molecular Weight and InChI Search
• Superstructure Search
• SMARTS Search
• Chemical Name Auto-Complete
• SDF File Download Option for Ligand Results
• Search for Entries with Non-Standard Amino-Acids/Nucleotides
• Tabular Report Improvements
• Inline Filter vs. Advanced Search
• Customize Columns
• Biological Process, Cellular Component, and Molecular Function GO Terms
• CATH, SCOP, and PFAM Domain Assignments with Residue Ranges

biojava-structure now supports Chemical Component Dictionary

I have updated the BioJava structure data model to support the PDB
chemical component dictionary. This has the benefit that now

* Chemically modified amino acids can be detected (and treated as
amino acids, rather than Hetatom groups)
* It is possible to get a component type for each Group, which allows
to identify ligands.

As a consequence the nr. of amino acids in a chain can change compared
to the previous data representation. As such the loading of chem.
comps is set to "false" by default. It can be configure by the
"loadChemCompInfo" flag in the PDB/mmCIF file parsers.

PDB ID 1A4W - Thrombin with Thiazole-containing Inhibitors. Image source: RCSB PDB

An example where this representation makes a difference is PDB ID 1A4W. This structure contains several Ligands and a chemically modified residue. Without the help of the Chemical Component Dictionary it would have been difficult to correctly represent this protein.

You can get the code either from BioJava SVN, or from the (still slightly experimental) Maven repository at http://www.biojava.org/download/maven/ .

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

From multi resistant drugs to multi resistant plants

I have always been critical about the increasing monoculture in agriculture. The combination of powerful herbicides and special herbicide resistant crop has on one side increased yield, on the other side reduced the diversity of available crop strains.

Similar to the way some diseases adjust to our drugs and become resistant, it seems multi- herbicide resistant plants are now also becoming a problem:

http://www.nytimes.com/2010/05/04/business/energy-environment/04weed.html

This should come to little surprise for anybody who knows a bit of history of modern agriculture. There are other examples of monoculture and how evolution and adaption of nature in the end puts the harvest at risk. The most prominent example to day is the Banana:

Modern bananas are not as sweet as they used to be in the first half of the 20th century. The then dominant Gros Michael banana essentially was extinct due to monoculture and the emergence of a fungus, killing this plant. This happened before the 1960ies, so not many people can remember this today. I have never eaten a Gros Michael banana myself, so I can only cite other sources that claim that Gros Michael was a better tasting fruit than the Cavendish variety we are eating today. The Cavendish is resistant to the fungus that killed Gros Michael, but reportedly not as sweet and creamy.

Here more about the history of the banana:

http://www.naturalnews.com/023339_banana_bananas_disease.html

To come back to the beginning of this blog, the emergence of multi-resistant plants should alert all farmers. Growing a variety of different strains should become a priority again.

Integration of open access literature into the RCSB Protein Data Bank Using BioLit

In our latest article we describe how we integrate open access articles from PubMedCentral that mention PDB IDs into the RCSB PDB web site. For every PDB entry it is now possible to see how it has been used in the publicly available literature.

http://www.biomedcentral.com/1471-2105/11/220/abstract

On a side note, I am not impressed about the slow pace with which this article got through the review and publication process. It took months to get this out.

New look and feel at RCSB PDB web site

RCSB PDB has been advised by a worldwide top consultancy about how to take the look and feel to the next level. We are planning to release the result with the next major update. Please take a look and let us know any feedback:

http://betastaging.rcsb.org/pdb/home/home.do