Members of the C-type lectin domain (CTLD) superfamily are metazoan proteins functionally important in glycoprotein metabolism, mechanisms of multicellular integration and immunity. This thesis presents the results of several computational and experimental studies of the CTLD structure, function and evolution.¶ Core structural properties of the CTLD fold were explored in a comparative analysis of the 37 distinct CTLD structures available publicly, which demonstrate significant structural conservation despite low or undetectable sequence similarity. Pairwise structural alignments of all CTLD structures were created with three different methods (DALI, CE and LOCK) and analysed manually and using a computational algorithm developed for this purpose. The analysis revealed a set of conserved positions and interactions, which were classified based on their role in CTLD structure maintenance.¶ The CTLD family is large and diverse. To organize and annotate the several thousand of known CTLD-containing protein sequences and integrate the information on their evolution, structure and function a local database and a web-based interface to it were developed. The software is written in Perl, is based on bioperl, bioperl-db and Apache::ASP modules, and can be used for collaborative annotation of any collection of phylogenetically related sequences.¶ Several studies of CTLD genomics were performed. In one such study, carried out in collaboration with the RIKEN structural genomics centre, CTLD sequences from the Caenorhabditis elegans genome were identified and clustered into groups based on similarity. The most representative members of the groups were then selected, which if characterized structurally would tell most about the C. elegans CTLDs and provide templates for homology modelling of all C. elegans CTLD structures.¶ In the other whole-genome study, the CTLD family in the puffer fish Fugu rubripes was analysed using the draft genome sequence. This work extended and complemented three genome-level surveys on human, C. elegans and D. melanogaster reported previously. The study showed that the CTLD repertoire of Fugu rubripes is very similar to that of mammals, although several interesting differences exist, and that Fugu CTLD-encoding genes are selectively duplicated in a manner suggesting an ancient large-scale duplication event. Another important finding was the identification of several new CTLDcps, which had mammalian orthologues not recognized previously.¶ CBCP, a novel CTLD-containing protein highly conserved between fish and mammals with previously unknown domain architecture, was predicted in the Fugu study based solely on ab initio gene models from the Fugu locus and cross-species genomic DNA alignments. To test if the prediction was correct, a full-length cDNA of the mouse CBCP was cloned, its tissue distribution characterized and untranslated regions determined by RACE. The full-length mCBCP transcript is 10 kb long, encodes a protein of 2172 amino acids and confirms the original prediction. The presence of a large N-terminal NG2 domain makes CBCP a member of a small but very interesting family of Metazoan proteins.

Of the 20 standard amino acids, cysteines are the only amino acids that have a reactive sulphur atom, thus enabling two cysteines to form strong covalent bonds known as disulfide bonds. Even though almost all proteins have cysteines, not all of them have disulfide bonds. Disulfide bonds provide structural stability to proteins and hence are an important constraint in determining the structure of a protein. As a result, disulfide bonds are used to study various protein properties, one of them being protein folding. Protein structure prediction is the problem of predicting the three-dimensional structure of a protein from its one-dimensional amino acid sequence. Ab initio methods are a group of methods that attempt to solve this problem from first principles, using only basic physico-chemical properties of proteins. These methods use structure libraries of short amino acid fragments in the process of predicting the structure of a protein. The protein structures from which these structure libraries are created are not classified in any other way apart from being non-redundant. In this thesis, we investigate the structural dissimilarities of short amino acid fragments when occurring in proteins with disulfide bonds and when occurring in those proteins without disulfide bonds. We are interested in this because, as mentioned earlier, the protein structures from which the structure libraries of ab initio methods are created, are not classified in any form. This means that any significant structural difference in amino acids and short fragments when occurring in proteins with and without disulfide bonds would remain unnoticed as these structure libraries have both fragments from proteins with disulfide bonds and without disulfide bonds together. Our investigation of structural dissimilarities of amino acids and short fragments is done in four phases. In phase one, by statistically analysing the phi and psi backbone dihedral angle distributions we show that these fragments have significantly different structures in terms of dihedral angles when occurring in proteins with and without disulfide bonds. In phase two, using directional statistics we investigate how structurally different are the 20 different amino acids and the short fragments when occurring in proteins with and without disulfide bonds. In phase three of our work, we investigate the differences in secondary structure preference of the 20 amino acids in proteins with and without disulfide bonds. In phase four, we further investigate and show that there are significant differences within the same secondary structure region of amino acids when they occur in proteins with and without disulfide bonds. Finally, we present the design and implementation details of a dihedral angle and secondary structure database of short amino acid fragments (DASSD) that is publicly available. Thus, in this thesis we show previously unknown significant structure differences in terms of backbone dihedral angles and secondary structures in amino acids and short fragments when they occur in proteins with and without disulfide bonds.

Inorganic cations play decisive roles in many cellular and physiological processes and are essential components of plant nutrition. Therefore, the uptake of cations and their redistribution must be precisely controlled. Vacuolar antiporters are important elements in mediating the intracellular sequestration of these cations. CAXs (for CAtion eXchanger) are members of a multigene family and appear to predominately reside on vacuoles. Defining CAX regulation and substrate specificity have been aided by utilizing yeast as an experimental tool. Studies in plants suggest CAXs regulate apoplastic Ca2+ levels in order to optimize cell wall expansion, photosynthesis, transpiration and plant productivity. CAX studies provide the basis for making designer transporters that have been used to develop nutrient enhanced crops and plants for remediating toxic soils. In my second study, I have characterized and defined autoinhibitory domain of Arabidopsis CAX3. Several CAX transporters, including CAX1, appear to contain an approximately 40 amino acid N-terminal regulatory regions (NRR) that modulates transport through N-terminal autoinhibition. Deletion of the NRR from several CAXs (sCAX) enhances function in plant and yeast expression assays; however, to date, there are no functional assays for CAX3. In this report, we create a series of truncations in the CAX3 NRR and demonstrate activation of CAX3 in both yeast and plants by truncating a large portion of the NRR. Experiments on endomembrane-enriched vesicles isolated from yeast expressing activated CAX3 demonstrate that the gene encodes Ca2+/H+ exchange with properties distinct from CAX1. These studies demonstrate shared and unique aspects of CAX1 and CAX3 transport and regulation. My third study is to express and purify CAX proteins for X-ray crystallographic analysis. In this study, I initiated crystallization of vacuolar membrane localized CAX protein from eukaryotes. Membrane proteins continue to be challenging targets for structural biology because of their hydrophobic nature. We have demonstrated here that eukaryotic Ca2+/H+ exchanger can be successfully expressed in E. coli based expression system. Collectively, our findings suggest that CAX protein can be successfully expressed, detergent solublized and purified from E. coli with a yield sufficient for functional and structural studies.

Nuclear magnetic resonance (NMR) spectroscopy technique is becoming exceedingly significant due to its capability of studying protein structures in solution. However, NMR protein structure determination has remained a laborious and costly process until now, even with the help of currently available computer programs. After the NMR spectra are collected, the main road blocks to the fully automated NMR protein structure determination are peak picking from noisy spectra, resonance assignment from imperfect peak lists, and structure calculation from incomplete assignment and ambiguous nuclear Overhauser enhancements (NOE) constraints. The goal of this dissertation is to propose error-tolerant and highly-efficient methods that work well on real and noisy data sets of NMR protein structure determination and the closely related protein structure prediction problems. One major contribution of this dissertation is to propose a fully automated NMR protein structure determination system, AMR, with emphasis on the parts that I contributed. AMR only requires an input set with six NMR spectra. We develop a novel peak picking method, PICKY, to solve the crucial but tricky peak picking problem. PICKY consists of a noise level estimation step, a component forming step, a singular value decomposition-based initial peak picking step, and a peak refinement step. The first systematic study on peak picking problem is conducted to test the performance of PICKY. An integer linear programming (ILP)-based resonance assignment method, IPASS, is then developed to handle the imperfect peak lists generated by PICKY. IPASS contains an error-tolerant spin system forming method and an ILP-based assignment method. The assignment generated by IPASS is fed into the structure calculation step, FALCON-NMR. FALCON-NMR has a threading module, an ab initio module, an all-atom refinement module, and an NOE constraints-based decoy selection module. The entire system, AMR, is successfully tested on four out of five real proteins with practical NMR spectra, and generates 1.25A, 1.49A, 0.67A, and 0.88A to the native reference structures, respectively. Another contribution of this dissertation is to propose novel ideas and methods to solve three protein structure prediction problems which are closely related to NMR protein structure determination. We develop a novel consensus contact prediction method, which is able to eliminate server correlations, to solve the protein inter-residue contact prediction problem. We also propose an ultra-fast side chain packing method, which only uses local backbone information, to solve the protein side chain packing problem. Finally, two complementary local quality assessment methods are proposed to solve the local quality prediction problem for comparative modeling-based protein structure prediction methods.

Nuclear magnetic resonance (NMR) spectroscopy technique is becoming exceedingly significant due to its capability of studying protein structures in solution. However, NMR protein structure determination has remained a laborious and costly process until now, even with the help of currently available computer programs. After the NMR spectra are collected, the main road blocks to the fully automated NMR protein structure determination are peak picking from noisy spectra, resonance assignment from imperfect peak lists, and structure calculation from incomplete assignment and ambiguous nuclear Overhauser enhancements (NOE) constraints. The goal of this dissertation is to propose error-tolerant and highly-efficient methods that work well on real and noisy data sets of NMR protein structure determination and the closely related protein structure prediction problems. One major contribution of this dissertation is to propose a fully automated NMR protein structure determination system, AMR, with emphasis on the parts that I contributed. AMR only requires an input set with six NMR spectra. We develop a novel peak picking method, PICKY, to solve the crucial but tricky peak picking problem. PICKY consists of a noise level estimation step, a component forming step, a singular value decomposition-based initial peak picking step, and a peak refinement step. The first systematic study on peak picking problem is conducted to test the performance of PICKY. An integer linear programming (ILP)-based resonance assignment method, IPASS, is then developed to handle the imperfect peak lists generated by PICKY. IPASS contains an error-tolerant spin system forming method and an ILP-based assignment method. The assignment generated by IPASS is fed into the structure calculation step, FALCON-NMR. FALCON-NMR has a threading module, an ab initio module, an all-atom refinement module, and an NOE constraints-based decoy selection module. The entire system, AMR, is successfully tested on four out of five real proteins with practical NMR spectra, and generates 1.25A, 1.49A, 0.67A, and 0.88A to the native reference structures, respectively. Another contribution of this dissertation is to propose novel ideas and methods to solve three protein structure prediction problems which are closely related to NMR protein structure determination. We develop a novel consensus contact prediction method, which is able to eliminate server correlations, to solve the protein inter-residue contact prediction problem. We also propose an ultra-fast side chain packing method, which only uses local backbone information, to solve the protein side chain packing problem. Finally, two complementary local quality assessment methods are proposed to solve the local quality prediction problem for comparative modeling-based protein structure prediction methods.

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.

NMR spectroscopy is not only for protein structure determination, but also for drug screening and studies of dynamics and interactions. In both cases, one of the main bottleneck steps is backbone assignment. When a homologous structure is available, it can accelerate assignment. Such structure-based methods are the focus of this thesis. This thesis aims for fast and robust methods for NMR assignment problems; in particular, structure-based backbone assignment and chemical shift mapping. For speed, we identified situations where the number of 15N-labeled experiments for structure-based assignment can be reduced; in particular, when a homologous assignment or chemical shift mapping information is available. For robustness, we modeled and directly addressed the errors. Binary integer linear programming, a well-studied method in operations research, was used to model the problems and provide practically efficient solutions with optimality guarantees. Our approach improved on the most robust method for structure-based backbone assignment on 15N-labeled data by improving the accuracy by 10% on average on 9 proteins, and then by handling typing errors, which had previously been ignored. We show that such errors can have a large impact on the accuracy; decreasing the accuracy from 95% or greater to between 40% and 75%. On automatically picked peaks, which is much noisier than manually picked peaks, we achieved an accuracy of 97% on ubiquitin. In chemical shift mapping, the peak tracking is often done manually because the problem is inherently visual. We developed a computer vision approach for tracking the peak movements with average accuracy of over 95% on three proteins with less than 1.5 residues predicted per peak. One of the proteins tested is larger than any tested by existing automated methods, and it has more titration peak lists. We then combined peak tracking with backbone assignment to take into account contact information, which resulted in an average accuracy of 94% on one-to-one assignments for these three proteins. Finally, we applied peak tracking and backbone assignment to protein-ligand docking to illustrate the potential for fast 3D complex determination.

It is well known that the biological function of a protein depends on its 3D structure. Therefore, solving the problem of protein structures is one of the most important works for studying proteins. However, protein structure prediction is a very challenging task because there is still no clear feature about how a protein folds to its 3D structure yet. In this thesis, we propose a genetic algorithm (GA) based on the lattice model to predict the 3D structure of an unknown protein, target protein, whose primary sequence and secondary structure elements (SSEs) are assumed known. Hydrophobic-hydrophilic model (HP model) is one of the most simplified and popular protein folding models. These models consider the hydrophobic-hydrophobic interactions of protein structures, but the results of prediction are still not encouraged enough. Therefore, we suggest that some other features should be considered, such as SSEs, charges, and disulfide bonds. That is, the fitness function of GA in our method considers not only how many hydrophobic-hydrophobic pairs there are, but also what kind of SSEs these amino acids belong to. The lattice model is in fact used to help us get a rough folding of the target protein, since we have no idea how they fold at the very beginning. We show that these additional features do improve the prediction accuracy by comparing our prediction results with their real structures with RMSD.

Functional expression of a protein in life form is decided by its tertiary structure. In the past few decades, a significant number of studies have been made on this subject. However, the folding rules of a protein still stay unsolved. The challenge is to predict the three-dimensional tertiary structure of a protein from its primary amino acid sequence. We propose a hybrid method combining homology model and the folding approach to predict protein three-dimensional structure from amino acid sequence. The previous researches on folding problem mostly take the HP (Hydrophobic-Polar) model, which is not able to simulate the native structure of proteins. We use a more exquisite model, the sliced lattice model, to approximate the native forms. Another essential factor influencing protein structures is disulfide bonds, which are ignored in the HP model. We use the ant colony optimization algorithm to approximate the folding problem with the constrained disulfide bond on the sliced lattice HP model. We show that the prediction results are better than previous methods by the measurement of RMSD(Root Mean Square Deviation).

Bioinformatics applications can address the transfer of information at several stages of the central dogma of molecular biology, including transcription and translation. This dissertation focuses on using Bayesian models to interpret biological data in bioinformatics, using Markov chain Monte Carlo (MCMC) for the inference method. First, we use our approach to interpret data at the transcription level. We propose a two-level hierarchical Bayesian model for variable selection on cDNA Microarray data. cDNA Microarray quantifies mRNA levels of a gene simultaneously so has thousands of genes in one sample. By observing the expression patterns of genes under various treatment conditions, important clues about gene function can be obtained. We consider a multivariate Bayesian regression model and assign priors that favor sparseness in terms of number of variables (genes) used. We introduce the use of different priors to promote different degrees of sparseness using a unified two-level hierarchical Bayesian model. Second, we apply our method to a problem related to the translation level. We develop hidden Markov models to model linker/non-linker sequence regions in a protein sequence. We use a linker index to exploit differences in amino acid composition between regions from sequence information alone. A goal of protein structure prediction is to take an amino acid sequence (represented as a sequence of letters) and predict its tertiary structure. The identification of linker regions in a protein sequence is valuable in predicting the three-dimensional structure. Because of the complexities of both models encountered in practice, we employ the Markov chain Monte Carlo method (MCMC), particularly Gibbs sampling (Gelfand and Smith, 1990) for the inference of the parameter estimation.