The three-dimensional structure of a protein molecule is the key to understanding its biological and physiological properties. A major problem in bioinformatics is to efficiently determine the three-dimensional structures of query proteins. Protein NMR structure de- termination is one of the main experimental methods and is comprised of: (i) protein sample production and isotope labelling, (ii) collecting NMR spectra, and (iii) analysis of the spectra to produce the protein structure. In protein NMR, the three-dimensional struc- ture is determined by exploiting a set of distance restraints between spatially proximate atoms. Currently, no practical automated protein NMR method exists that is without human intervention. We first propose a complete automated protein NMR pipeline, which can efficiently be used to determine the structures of moderate sized proteins. Second, we propose a novel and efficient semidefinite programming-based (SDP) protein structure determination method. The proposed automated protein NMR pipeline consists of three modules: (i) an automated peak picking method, called PICKY, (ii) a backbone chemical shift assign- ment method, called IPASS, and (iii) a protein structure determination method, called FALCON-NMR. When tested on four real protein data sets, this pipeline can produce structures with reasonable accuracies, starting from NMR spectra. This general method can be applied to other macromolecule structure determination methods. For example, a promising application is RNA NMR-assisted secondary structure determination. In the second part of this thesis, due to the shortcomings of FALCON-NMR, we propose a novel SDP-based protein structure determination method from NMR data, called SPROS. Most of the existing prominent protein NMR structure determination methods are based on molecular dynamics coupled with a simulated annealing schedule. In these methods, an objective function representing the error between observed and given distance restraints is minimized; these objective functions are highly non-convex and difficult to optimize. Euclidean distance geometry methods based on SDP provide a natural formulation for realizing a three-dimensional structure from a set of given distance constraints. However, the complexity of the SDP solvers increases cubically with the input matrix size, i.e., the number of atoms in the protein, and the number of constraints. In fact, the complexity of SDP solvers is a major obstacle in their applicability to the protein NMR problem. To overcome these limitations, the SPROS method models the protein molecule as a set of intersecting two- and three-dimensional cliques. We adapt and extend a technique called semidefinite facial reduction for the SDP matrix size reduction, which makes the SDP problem size approximately one quarter of the original problem. The reduced problem is solved nearly one hundred times faster and is more robust against numerical problems. Reasonably accurate results were obtained when SPROS was applied to a set of 20 real protein data sets.

The three-dimensional structure of a protein molecule is the key to understanding its biological and physiological properties. A major problem in bioinformatics is to efficiently determine the three-dimensional structures of query proteins. Protein NMR structure de- termination is one of the main experimental methods and is comprised of: (i) protein sample production and isotope labelling, (ii) collecting NMR spectra, and (iii) analysis of the spectra to produce the protein structure. In protein NMR, the three-dimensional struc- ture is determined by exploiting a set of distance restraints between spatially proximate atoms. Currently, no practical automated protein NMR method exists that is without human intervention. We first propose a complete automated protein NMR pipeline, which can efficiently be used to determine the structures of moderate sized proteins. Second, we propose a novel and efficient semidefinite programming-based (SDP) protein structure determination method. The proposed automated protein NMR pipeline consists of three modules: (i) an automated peak picking method, called PICKY, (ii) a backbone chemical shift assign- ment method, called IPASS, and (iii) a protein structure determination method, called FALCON-NMR. When tested on four real protein data sets, this pipeline can produce structures with reasonable accuracies, starting from NMR spectra. This general method can be applied to other macromolecule structure determination methods. For example, a promising application is RNA NMR-assisted secondary structure determination. In the second part of this thesis, due to the shortcomings of FALCON-NMR, we propose a novel SDP-based protein structure determination method from NMR data, called SPROS. Most of the existing prominent protein NMR structure determination methods are based on molecular dynamics coupled with a simulated annealing schedule. In these methods, an objective function representing the error between observed and given distance restraints is minimized; these objective functions are highly non-convex and difficult to optimize. Euclidean distance geometry methods based on SDP provide a natural formulation for realizing a three-dimensional structure from a set of given distance constraints. However, the complexity of the SDP solvers increases cubically with the input matrix size, i.e., the number of atoms in the protein, and the number of constraints. In fact, the complexity of SDP solvers is a major obstacle in their applicability to the protein NMR problem. To overcome these limitations, the SPROS method models the protein molecule as a set of intersecting two- and three-dimensional cliques. We adapt and extend a technique called semidefinite facial reduction for the SDP matrix size reduction, which makes the SDP problem size approximately one quarter of the original problem. The reduced problem is solved nearly one hundred times faster and is more robust against numerical problems. Reasonably accurate results were obtained when SPROS was applied to a set of 20 real protein data sets.

No description available.

Nuclear magnetic resonance (NMR) is one of the main approaches for protein struc- ture determination. The biggest advantage of this approach is that it can determine the three-dimensional structure of the protein in the solution phase. Thus, the natural dynamics of the protein can be studied. However, NMR protein structure determina- tion is an expertise intensive and time-consuming process. If the structure determi- nation process can be accelerated or even automated by computational methods, that will significantly advance the structural biology field. Our goal in this dissertation is to propose highly efficient and error tolerant methods that can work well on real and noisy data sets of NMR. Our first contribution in this dissertation is the development of a novel peak pick- ing method (WaVPeak). First, WaVPeak denoises the NMR spectra using wavelet smoothing. A brute force method is then used to identify all the candidate peaks. Af- ter that, the volume of each candidate peak is estimated. Finally, the peaks are sorted according to their volumes. WaVPeak is tested on the same benchmark data set that was used to test the state-of-the-art method, PICKY. WaVPeak shows significantly better performance than PICKY in terms of recall and precision. Our second contribution is to propose an automatic method to select peaks pro- duced by peak picking methods. This automatic method is used to overcome the limitations of fixed number-based methods. Our method is based on the Benjamini- Hochberg (B-H) algorithm. The method is used with both WaVPeak and PICKY to automatically select the number of peaks to return from out of hundreds of candidate peaks. The volume (in WaVPeak) and the intensity (in PICKY) are converted into p-values. Peaks that have p-values below some certain threshold are selected. Ex- perimental results show that the new method is better than the fixed number-based method in terms of recall. To improve precision, we tried to eliminate false peaks using consensus of the B-H selected peaks from both PICKY and WaVPeak. On average, the consensus method is able to identify more than 88% of the expected true peaks, whereas less than 17% of the selected peaks are false ones. Our third contribution is to propose for the first time, the 3D extension of the Median-Modified-Wiener-Filter (MMWF), and its novel variation named MMWF*. These spatial filters have only one parameter to tune: the window-size. Unlike wavelet denoising, the higher dimensional extension of the newly proposed filters is relatively easy. Thus, they can be applied to denoise multi-dimensional NMR-spectra. We tested the proposed filters and the Wiener-filter, an adaptive variant of the mean-filter, on a benchmark set that contains 16 two-dimensional and three-dimensional NMR- spectra extracted from eight proteins. Our results demonstrate that the adaptive spatial filters significantly outperform their non-adaptive versions. The performance of the new MMWF* on 2D/3D-spectra is even better than wavelet-denoising. Finally, we propose a novel framework that simultaneously conducts slice picking and spin system forming, an essential step in resonance assignment. Our framework then employs a genetic algorithm, directed by both connectivity information and amino acid typing information from the spin systems to assign the spin systems to residues. The inputs to our framework can be as few as two commonly used spectra, i.e., CBCA(CO)NH and HNCACB. Different from existing peak picking and resonance assignment methods that treat peaks as the units, our method is based on slices, which are one-dimensional vectors in three-dimensional spectra that correspond to certain (N, H) values. Experimental results on both benchmark simulated data sets and four real protein data sets demonstrate that our method significantly outperforms the state-of-the-art methods especially on the more challenging real protein data sets, while using a less number of spectra than those methods. Furthermore, we show that using the chemical shift assignments predicted by our method for the four real proteins can lead to accurate calculation of their final three-dimensional structures by using CS-ROSETTA server.

Strukturbestämning av proteiner är viktigt för att kunna förstå deras funktion och en snabbt utvecklande metod inom fältet är kryoelektronmikroskopi. Storleksbegränsningar förhindrar en bredare applikation av metoden eftersom små proteiner har för låg signal i förhållande till bakgrund för att kunna visualiseras som enstaka partiklar i elektronmiksoskopibilder. Hypotesen för projektet är att det är möjligt att avbilda väldigt små proteiner och kringgå den konventionella storleksbegränsningen genom att använda ett bärarprotein ((Putrescine Aminotransferase; YgjG) som kopplas till en affibody (Zwt) genom “helical fusion” och sedan binda ett litet målprotein till denna större struktur. Komplexet ska ge en tillräcklig storlek, symmetri och rigiditet för en lyckad elektronmikroskopi av bärare tillsammans med det lilla icke kovalent bundna målproteinet. För att karaktärisera den föreslagna bäraren, genomförs stabilitetstester genom CD, verifiering av inbindning av målproteinet i SPR, renhetsundersökning med SEC och slutligen kryoelektronmikroskopi för att testa konceptet. Det lilla målproteinet som kommer att avbildas i konceptstudien är en annan affibody (Z963), som i så fall skulle vara det minsta proteinet som någonsin har lösts med kryogenelektronmikroskopi. Resultaten visar att den undersökta tetramera-bäraren är väldigt stabil (Tm~ 85 oC) och kan tolerera en affibody-fusion med bibehållen bindning av multipla säten. Proteinet kan uttryckas rekombinant och renas till högt utbyte och bildar tetramerer även med fuserad affibody. De slutgiltiga resultaten från den kryoelektronmikroskopiska analysen inväntas fortfarande, men lovande griddar har skapats och en partikelselektion har gett klara 2-D klasser som också framhäver att det lilla målproteinet har bundit. Sammanfattningsvis har biofysikalisk karaktärisering indikerat att YgjG är en lovande bas för ett “imaging scaffold” och att preliminära enstaka-partikel kryoelektronmikroskopi analyser visar att den föreslagna strategin att undersöka små målproteiner är möjlig. / Determining structures of proteins is important to understand protein functions, and a rapidly evolving technique in this field is cryogen electron microscopy. However, size limitations are preventing wider applications of the technique because small proteins have poor signal to noise ratios and are not possible to distinguish in single-particle images. The hypothesis of this project is that it is possible to image very small proteins, bypassing the conventional size limitations of single-particle cryo-EM, by utilizing a carrier protein-scaffold (Putrescine Aminotransferase; YgjG) connected through helical fusion to an affibody (Zwt) that can bind to a small protein of interest. The complex provides a sufficient size, symmetry, and rigidity for successful electron microscopy also of the non-covalently bound small protein of interest. To characterise the proposed scaffold, thermal stability through CD, binding of target protein in SPR, purity through SEC and experiments towards proof-of-concept in cryo-EM will be performed. The small protein of interest to be imaged in the proof-of-concept setup is another affibody, called Z963, that would be the smallest protein ever solved with cryo-EM. The results show that the investigated tetrameric protein scaffold is a highly stable protein (Tm~85oC) that can tolerate affibody fusion with retained binding function of multiple sites. The protein can be recombinantly expressed and purified in high yield and forms tetramers also when fused to affibody. The cryo-EM results are still pending, but promising grids have been created and in an initial particle selection clear 2-D classes that also reveal the small bound protein of interest have been generated. To conclude, biophysical characterization indicates that YgjG is a promising base structure for an imaging scaffold and preliminary single-particle cryo-EM analyses show that the proposed strategy to investigate structures of small proteins of interest is feasible.

No description available.

No description available.