Skip Navigation


Bioinformatics Advance Access originally published online on August 13, 2008
Bioinformatics 2008 24(19):2258-2259; doi:10.1093/bioinformatics/btn423
This Article
Right arrow Abstract Freely available
Right arrow FREE Full Text (Print PDF) Freely available
Right arrow All Versions of this Article:
24/19/2258    most recent
btn423v1
Right arrow Comments: Submit a response
Right arrow Alert me when this article is cited
Right arrow Alert me when Comments are posted
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Staykova, D. K.
Right arrow Articles by Billeter, M.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Staykova, D. K.
Right arrow Articles by Billeter, M.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2008. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

PRODECOMPv3: decompositions of NMR projections for protein backbone and side-chain assignments and structural studies

Doroteya K. Staykova *, Jonas Fredriksson and Martin Billeter *

Department of Chemistry, University of Gothenburg, P.O. Box 462, 405 30 Gothenburg, Sweden

*To whom correspondence should be addressed.


   ABSTRACT
TOP
 ABSTRACT
1 INTRODUCTION
 2 MULTI-WAY DECOMPOSITIONS
 3 RESULTS
 4 IMPLEMENTATION
 ACKNOWLEDGEMENTS
 REFERENCES
 

Summary: PRODECOMP (projection decomposition) is an implementation of a multi-way decomposition algorithm for the analysis of two-dimensional projections of high-dimensional nuclear magnetic resonance spectra. The newest version, PRODECOMPv3, features a dramatic speedup, more reliable decompositions, a substantial reduction in memory demands, a new graphical user interface and integration into third-party software. These improvements extend the applicability of decompositions to novel types of NMR data on proteins, yielding backbone and side-chain assignments as well as structural information, and therewith enabling complete characterizations of proteins.

Availability: Program, short manual and an example calculation are freely available at www2.chem.gu.se/bcbp/nmr/prodecomp.html

Contact: doroteya{at}chem.gu.se;


   1 INTRODUCTION
TOP
 ABSTRACT
 1 INTRODUCTION
2 MULTI-WAY DECOMPOSITIONS
 3 RESULTS
 4 IMPLEMENTATION
 ACKNOWLEDGEMENTS
 REFERENCES
 
Projection techniques in solution NMR (nuclear magnetic resonance) applied to proteins have the potential to reduce experiment times by several orders of magnitudes, making the approach highly feasible for structure genomics or the functional investigation of intrinsically unstructured proteins. However, the interpretation of projection spectra presents some additional challenges. Multi-way analysis is a mathematical tool for characterizing higher order data with applications in many fields (Bro, 2006). Simultaneous decomposition of a set of NMR projections yields reliable solutions even with signal-to-noise ratios of the individual projections close to 1 (Malmodin and Billeter, 2005, 2006; Staykova et al., 2008). Implemented as a general tool for projection decomposition called PRODECOMP, this approach has a wide range of applications in NMR. Projections of high-dimensional NMR spectra of two proteins, ubiquitin (8.5 kDa) and azurin (14 kDa), were used to demonstrate its capabilities of decomposing NMR data involving heteronuclear coupling, TOCSY and NOESY magnetization transfers (Levitt, 2001). With the help of accompanying programs for processing the PRODECOMP output, automated resonance assignments for backbone and side chain atoms, and distance restraints for structure determinations were obtained. The algorithm is also incorporated into generally available packages such as CCPN,1 and interfaced to other software (TopSpin, Bruker Biospin GmbH).


   2 MULTI-WAY DECOMPOSITIONS
TOP
 ABSTRACT
 1 INTRODUCTION
 2 MULTI-WAY DECOMPOSITIONS
3 RESULTS
 4 IMPLEMENTATION
 ACKNOWLEDGEMENTS
 REFERENCES
 
Two-dimensional (2D) projections Pm({omega}1, {omega}N) (projections enumerated by m) of a N–Dx spectrum S({omega}1,...,{omega}N) can be modeled as follows (Malmodin and Billeter, 2005; Malmodin and Billeter, 2006):


Formula 1

(1)
where the symbols ‘*’ and {otimes} represent convolution operations and direct products. While the frequency parameter {omega}N is the same in the full spectrum S and the projections Pm, the {omega}–axis in Pm is a projection of the space spanned by the frequency axes {omega}1,...,{omega}N–1 in S (m refers to different linear combinations of frequencies on the left side which are reflected by different selections of FFormula on the right side). Terms in the sum enumerated by k are called components, and each component is characterized by 1D vectors FFormula ... FFormula, which are referred to as shapes. The latter characterize the resonances of all N nuclei present in the projections and thus provide the desired output; they can also be used to reconstruct the full-dimensional spectrum S. The term {varepsilon} is necessary to describe the difference due to noise or artifacts between the experimental input projections Pm on the left side of (1) and the model on the right side. Decomposition involves determining all shapes FFormula by minimizing {varepsilon}.


   3 RESULTS
TOP
 ABSTRACT
 1 INTRODUCTION
 2 MULTI-WAY DECOMPOSITIONS
 3 RESULTS
4 IMPLEMENTATION
 ACKNOWLEDGEMENTS
 REFERENCES
 
The original implementation of multi-way decomposition according to (1), based on the FNNLS algorithm (Bro and De Jong, 1997), demonstrated the feasibility of the approach when applied to NMR projection data PRODECOMPv1; Malmodin and Billeter, 2005; Malmodin and Billeter, 2006). Code modifications led to better convergence rates and more reliable components in crowded regions (PRODECOMPv2), which allowed obtaining complete backbone resonance assignments of ubiquitin using a combined set of projections from two 5D experiments yielding 9D components (Staykova et al., 2008). This application revealed limitations caused by huge memory requirements with large number of components or with increased spectral size. The ensuing improvements (PRODECOMPv3) not only removed the memory barrier, but also yielded a significant speedup in calculation time.

3.1 Algorithm improvements
A detailed analysis of the original algorithm revealed two major bottlenecks: scaling discrepancies between input data and trial shapes, and over-dimensioned temporary matrices.

Several modifications were implemented in the current version of PRODECOMP:

  • Normalizing of all input data substantially improved the convergence and removed ambiguities in the resulting shapes, revealing several previously missing components.
  • Large sparse matrices in the code were replaced by element-wise tracing, multiplication and buildup of corresponding data.
  • Among other improvements is also a definition of input and output formats coupled with conversion routines.

While the original version missed one of the six components in the test calculations of Figure 1 (white bars), scaling of input data resulted in observation of all components (gray bars). (Note that decomposition failures result in missing components rather than false positives.) Better memory management led to two important improvements: (a) a massive speedup in runtime (black bars) and (b) the possibility to decompose projections with higher resolution, e.g. increasing the number of points along the {omega}-axis from 121 to 256 or even 512. The modified decomposition algorithm, implemented in PRODECOMPv3, was successfully tested on projected spectra based on heteronuclear coupling, TOCSY and NOESY experiments. Note that the increase in resolution is crucial for the latter two types of experiments.


Figure 1
View larger version (22K):
[in this window]
[in a new window]
[Download PowerPoint slide]
  		Fig. 1. Relative runtimes, R, for various program versions and number of components (normalized to the leftmost calculation). The shading refers to different versions: white, PRODECOMPv1; gray, PRODECOMPv2; black, PRODECOMPv3. The hatching in the rightmost white bar indicates that only five of six components were resolved. Decompositions were tested on 46 projections (using stripes with 121 x 10 points from each projection) recorded for an ubiquitin sample.

 
3.2 Graphical user interface
The graphical user interface (GUI) of Figure 2 was designed to facilitate the input of projections and the choice of run-time parameters: selection of an interval along the {omega}N dimension, number of expected components in this interval, a regularization factor and the number of iterations to be performed (Staykova et al., 2008). Projections in TopSpin format or from other formats after conversion to the internal CEP (coupled evolution periods) format can be loaded. Various subsets of projections as well as individual run-time parameters can be selected without reloading the data. Integrated into PRODECOPMv3 are additional functionalities for visual examination of the resulting shapes as well as for storing the components in various formats, including an extensible markup language (XML) for CCPN.


Figure 2
View larger version (61K):
[in this window]
[in a new window]
[Download PowerPoint slide]
  		Fig. 2. GUI of PRODECOMPv3: inputs are 2D projections in TopSpin (Bruker Biospin GmbH) format or from other sources via CEP format (top right panel: selected projections from a TOCSY-type experiment). Decomposition output is stored in XML/CCPN and ASCII format and visualized. The example in the lower right panel shows six components with strongly overlapping signals in {omega}N). In this experiment, each component corresponds to one protein residue; one component is highlighted by black lines (see www2.chem.gu.se/bcbp/nmr/prodecomp.html for individual plots of all components).

 

   4 IMPLEMENTATION
TOP
 ABSTRACT
 1 INTRODUCTION
 2 MULTI-WAY DECOMPOSITIONS
 3 RESULTS
 4 IMPLEMENTATION
ACKNOWLEDGEMENTS
 REFERENCES
 
PRODECOMPv3 is written in Python as a freely available software library. The decomposition function is being integrated within the CCPN model (proposed standard for data exchange between different programs and databases in macromolecular NMR) and TopSpin (instrument software by Bruker Biospin GmbH for recording and processing of experiments). PRODECOMPv3 has been tested on Windows, different Linux environments and Mac OS using the same code.


   ACKNOWLEDGEMENTS
TOP
 ABSTRACT
 1 INTRODUCTION
 2 MULTI-WAY DECOMPOSITIONS
 3 RESULTS
 4 IMPLEMENTATION
 ACKNOWLEDGEMENTS
REFERENCES
 
We would like to thank Wolfgang Bermel from Bruker Biospin GmbH for implementing the NMR experiments.

Funding: EU (LSHG-CT-2005-018988).

Conflict of Interest: none declared.


   FOOTNOTES
 
Associate Editor: Anna Tramontano

1Collaborative Computing Project for NMR, www.ccpn.ac.uk Back

Received on June 23, 2008; revised on August 6, 2008; accepted on August 7, 2008

   REFERENCES
TOP
 ABSTRACT
 1 INTRODUCTION
 2 MULTI-WAY DECOMPOSITIONS
 3 RESULTS
 4 IMPLEMENTATION
 ACKNOWLEDGEMENTS
 REFERENCES
 

    Bro R. Review on multiway analysis in chemistry - 2000-2005. Crit. Rev. Anal. Chem (2006) 36:279–293.[CrossRef]

    Bro R, DeJong S. A fast non-negativity-constrained least squares algorithm. J. Chemom (1997) 11:393–401.[CrossRef]

    Levitt MH. (2001) Chichester, England: Wiley.

    Malmodin D, Billeter M. Multiway decomposition of NMR spectra with coupled evolution periods. J. Am. Chem. Soc (2005) 127:13486–13487.[CrossRef][Web of Science][Medline]

    Malmodin D, Billeter M. Robust and versatile interpretation of spectra with coupled evolution periods using multi-way decomposition. Magn. Reson. Chem (2006) 44:S185–S195.[CrossRef][Web of Science][Medline]

    Staykova DK, et al. Assignment of protein NMR spectra based on projections, multi-way decomposition and a fast correlation approach. J. B, iomol. NMR (2008) 42.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow FREE Full Text (Print PDF) Freely available
Right arrow All Versions of this Article:
24/19/2258    most recent
btn423v1
Right arrow Comments: Submit a response
Right arrow Alert me when this article is cited
Right arrow Alert me when Comments are posted
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Staykova, D. K.
Right arrow Articles by Billeter, M.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Staykova, D. K.
Right arrow Articles by Billeter, M.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?