No description available.

Sequence analysis and structure analysis are two of the fundamental areas of bioinformatics research. This dissertation discusses, specifically, protein structure related problems including protein structure alignment and query, and genome sequence related problems including haplotype reconstruction and genome rearrangement. It first presents an algorithm for pairwise protein structure alignment that is tested with structures from the Protein Data Bank (PDB). In many cases it outperforms two other well-known algorithms, DaliLite and CE. The preliminary algorithm is a graph-theory based approach, which uses the concept of \stars" to reduce the complexity of clique-finding algorithms. The algorithm is then improved by introducing \double-center stars" in the graph and applying a self-learning strategy. The updated algorithm is tested with a much larger set of protein structures and shown to be an improvement in accuracy, especially in cases of weak similarity. A protein structure query algorithm is designed to search for similar structures in the PDB, using the improved alignment algorithm. It is compared with SSM and shows better performance with lower maximum and average Q-score for missing proteins. An interesting problem dealing with the calculation of the diameter of a 3-D sequence of points arose and its connection to the sublinear time computation is discussed. The diameter calculation of a 3-D sequence is approximated by a series of sublinear time deterministic, zero-error and bounded-error randomized algorithms and we have obtained a series of separations about the power of sublinear time computations. This dissertation also discusses two genome sequence related problems. A probabilistic model is proposed for reconstructing haplotypes from SNP matrices with incomplete and inconsistent errors. The experiments with simulated data show both high accuracy and speed, conforming to the theoretically provable e ciency and accuracy of the algorithm. Finally, a genome rearrangement problem is studied. The concept of non-breaking similarity is introduced. Approximating the exemplar non-breaking similarity to factor n1..f is proven to be NP-hard. Interestingly, for several practical cases, several polynomial time algorithms are presented.

Thesis (Ph. D.)--University of Washington, 1998. / Vita. Includes bibliographical references (leaves [117]-125).

The Fe(II) and 2-oxoglutarate dependent oxygenases (2OG oxygenases) catalyse a broad range of oxidative reactions in various organisms. 2OG oxygenases use 2OG and molecular oxygen to catalyse the oxidation of a variety of substrates including small molecules, fatty acids, nucleic acids and proteins. Several human 2OG oxygenases are implicated in diseases. The fat mass and obesity associated protein (FTO) is linked to obesity, whilst collagen prolyl-4-hydroxylases (CPHs), the procollagen lysyl hydroxylases (PLODs), and the hypoxia inducible factor hydroxylases (PHDs) are linked to cancer. Therefore, structure-based inhibition studies on FTO, CPH and related 2OG oxygenases are of significant therapeutic interest. The obesity-associated FTO is an mRNA N⁶-methyladenine (m⁶A) demethylase and a homologue of E. coli alkylated DNA repair protein (AlkB), a DNA repair enzyme that demethylates N¹-methyladenine (m¹A) and N³-methylcytosine (m³C) bases. Human AlkB homologue 5 (ALKBH5) has a similar substrate profile as FTO, i.e. ALKBH5 is another mRNA m⁶A demethylase, making it a target for structural and inhibition studies to improve inhibitor selectivity for FTO. The CPH and PLODs catalyse hydroxylation of collagen prolyl- and lysyl-residues; the resultant 4-hydroxyprolyl- and 4-hydroxylysyl-residues are important for the formation of the collagen triple helix and intermolecular crosslinks, respectively. Another 2OG oxygenase, the 2-oxoglutarate and iron-dependent oxygenase domain-containing protein 2 (OGFOD2), is related by sequence similarity to the PLODs but its biological role is unknown. This thesis describes crystallographic, biochemical and inhibition studies on five 2OG oxygenases: AlkB, FTO, ALKBH5, OGFOD2 and CPH. Three AlkB-inhibitor complexes were determined; taken together, these structures serve as proof-of-principle that the AlkB subfamily 2OG oxygenases are amenable to structure-based inhibition studies. Several classes of inhibitors of FTO were then identified and their binding modes were investigated through the determination of 7 crystal structures of FTO-inhibitor complexes. Subsequently, a crystal structure of ALKBH5 was determined, which provided insights into its substrate recognition mechanisms. The ALKBH5 structure also serves as a template for inhibitor design. Preliminary structural and biochemical data were also obtained for OGFOD2 and CPH. Overall, these results contribute to the development of a biophysical understanding of human 2OG oxygenases, and will help to enable the development of selective inhibitors of 2OG oxygenases involved in nucleic acid and collagen modifications.

An increasing number of proteins with unknown function have their three-dimensional structure solved at high resolution. This situation, largely due to structural genomics initiatives, has been stimulating the development of automated structure-based function prediction methods. Knowledge of residues important for function – and more particularly – for binding can help automated prediction of function in different ways. The properties of a binding site such as its shape or amino acid composition can provide clues on the ligand that may bind to it. Also, having information on functionally important regions in similar proteins can refine the process of annotation transfer between homologues. Experimental results indicate that functional residues often have an unfavourable contribution to the stability of the folded state of a protein. This observation is the underlying principle of several computational methods for predicting the location of functional sites in protein structures. These methods search protein structures for destabilising residues, with the assumption that these are likely to be important for function. We have developed a method to detect clusters of destabilising residues which are in close spatial proximity within a protein structure. Individual residue contributions to protein stability are evaluated using detailed atomic models and an energy function based on fundamental physico-chemical principles. Our overall aim in this work was to evaluate the overlap between these clusters of destabilising residues and known binding sites in proteins. Unfortunately, reliable benchmark datasets of known binding sites in proteins are sorely lacking. Therefore, we have undertaken a comprehensive approach to define binding sites unambiguously from structural data. We have rigorously identified seven issues which should be considered when constructing datasets of binding sites to validate prediction methods, and we present the construction of two new datasets in which these problems are handled. In this regard, our work constitute a major improvement over previous studies in the field. Our first dataset consists of 70 proteins with binding sites for diverse types of ligands (e.g. nucleic acids, metal ions) and was constructed using all available data, including literature curation. The second dataset contains 192 proteins with binding sites for small ligands and polysaccharides, does not require literature curation, and can therefore be automatically updated. We have used our dataset of 70 proteins to evaluate the overlap between destabilising regions and binding sites (the second dataset of 192 proteins was not used for that evaluation as it constitutes a later improvement). The overlap is on average limited but significantly larger than random. The extent of the overlap varies with the type of bound ligand. Significant overlap is obtained for most polysaccharide- and small ligand-binding sites, whereas no overlap is observed for nucleic acid-binding sites. These differences are rationalised in terms of the geometry and energetics of the binding sites. Although destabilising regions, as detected in this work, can in general not be used to predict all types of binding sites in protein structures, they can provide useful information, particularly on the location of binding sites for polysaccharides and small ligands. In addition, our datasets of binding sites in proteins should help other researchers to derive and validate new function prediction methods. We also hope that the criteria which we use to define binding sites may be useful in setting future standards in other analyses.

Bioinformática estrutural de proteínas modificadas por eventos de splicing alternativo / Structural Bioinformatics of Proteins modified by Alternative Splicing

A técnica de espectroscopia por Ressonância Magnética Nuclear (NMR) de alta resolução foi utilizada para estudos estruturais em duas biomoléculas: a proteína HPr da bactéria Staphylococcus aureus, e o peptídeo C da insulina humana. Ambas estão relacionadas com a regulação da absorção de glicose pelas células, no primeiro caso em procariontes, e no segundo em organismos superiores. A proteína HPr (\"Histidine-containing protein\") de Staphylococcus aureus é uma das componentes centrais do sistema PTS (fosfoenolpiruvato:açúcar-fosfotransferase) de translocação grupal, responsável pelo transporte ativo de açúcar para o interior da célula bacterial. Nesse processo, a His15 do sítio ativo de HPr é fosforilada pela enzima EI, transferindo, a seguir, o grupo fosfato para a enzima EUA A mutação His15&#8594Ala interrompe a transferência do grupo fosfato; apesar disso, a afinidade entre HPr(H15A) e as enzimas EI/EIlA se mostrou semelhante à da nativa. Utilizando técnicas de NMR bidimensionais (COSY, TOCSY, NOESY, HSQC) etridimensionais (HNCA, HNCO, NOESY-HSQC) foi determinada a estrutura da mutante His15&#8594Ala de HPr de S. aureus. Sua estrutura consiste de um sanduíche-aberto, composto de 3 hélices-a paralelamente empacotadas contra uma folha formada por 4 fitas-&#946 anti-paralelas. Esse padrão é encontrado em todas as proteínas HPr já determinadas em diversas espécies, divergindo, porém, significativamente da estrutura previamente publicada para a proteína nativa de S. aureus com relação à orientação relativa de alguns elementos de estrutura secundária. Através de uma análise detalhada dos espectros NOESY das proteínas HPr mutante e nativa puderam ser encontradas diferenças conformacionais na região em tomo do sítio-ativo. Uma comparação com as outras estruturas de HPr já publicadas revelou uma maior semelhança entre a proteína mutante de S. aureus e a proteína no complexo HPr/EI de E. coli, fornecendo evidências de que a estrutura encontrada para a mutante represente a conformação assumida pela proteína HPr no momento de sua interação com a enzima EI, assim explicando a sua afinidade inalterada. O peptídeo-C da proinsulina é importante para a biosíntese da insulina, tendo sido considerado, por muito tempo, biologicamente inerte. Estudos recentes em pacientes diabéticos retomaram a discussão quanto a sua possível atividade reguladora. Utilizando a técnica de espectroscopia de NMR bidimensional (COSY, TOCSY, NOESY), foram realizados estudos estruturais no peptídeo-C da proinsulina humana. Quando dissolvido em 50%/50% água e TFE, o peptídeo-C apresentou 3 regiões centrais (9-12, 15-18, 22-25) com tendência à formação de dobras, uma região N-terminal (2-5) com 2 conformações em voltas-&#946 tipo I e I, e uma região Cterminal (26-31), de conformação extremamente bem definida, incluindo uma volta-&#946 tipo III\' (27-30). Em estudos descritos na literatura já foi demonstrada a atividade do pentapeptídeo C-terminal (EGSLQ), na forma de interações quirais com um receptor ainda desconhecido. Estudos anteriores por NMR prevêem a existência de uma estrutura na região C-terminal, a qual foi denominada de \"CA-Knuckle\". Nossa proposta é que a estrutura aqui obtida para o pentapeptídeo C-terminal seja justamente o \"CA-Knuckle\", representando o sítio-ativo do peptídeo-C da proinsulina humana. / High resolution Nuclear Magnetic Resonance spectroscopy has been used for structural studies on two biological macromolecules; the HPr protein from the bacterium Staphylococcus aureus, and the Cpeptide from human proinsulin. Both are related to the regulation of glucose absorption by celIs, the former case in prokaryotes and the latter in higher organisms. The HPr protein (Histidine Containing Protein) from S. aureus is one of the central components of the PTS (Phosphoenolpyruvate;sugar-phosphotransferase) system responsible for the active transport of sugars into the bacterial celI. During this process, His15 of the HPr active site is phosphorylated by enzyme I (EI), and then subsequently transfers this phosphate onto enzyme lIA (EIIA). The His15&#8594Ala mutant of HPr, whilst unable to participate in phosphate transfer, nevertheless retains similar affinities for both EI and EIIA. Using two-dimensional (COSY, TOCSY, NOESY, HSQC) and three-dimensional (HNCA, HNCO, NOESY-HSQC) NMR techniques, the structure of the His15Ala mutant of the HPr protein from S. aureus was determined. Its structure consists of an open &#946-sandwich, composed of three &#945-helices packed against a four-stranded anti-parallel &#946-sheet. This pattern has been seen in all other HPr proteins from other species so far determined but is markedly different from the previously published native structure from S. aureus with respect to the relative orientations of some of the elements of secondary structure. A detailed comparison of the native and mutant structures revealed differences in the conformation of the active site loop. The latter assumes a conformation similar to that seen in the structure of the complex between E. coli HPr and EI. This may explain the normal affinities of the mutant protein for EI and EIIA despite the absence of the active site histidine. The C-peptide of proinsulin is important for the biosynthesis of insulin but has been considered for a long time to be biologically inert. Recent studies in diabetic patients have stimulated a new debate concerning its possible regulatory role. Structural studies of the C-peptide were performed using two dimensional NMR spectroscopy (COSY, TOCSY and NOESY). ln the presence of 50% TFE three central regions of the molecule (residues 9-12, 15-18 and 22-25) showed tendencies to form ~-bends. The N terminal region (residues 2 to 5) was present in the form of either a type I or I\' &#946-turn, whilst the C terminal region (26-31) presented the most welI-defrnedstructure of the whole molecule which included a type III\' &#946-turn. The C-terminal pentapeptide (EGSLQ) has been described in the literature as being responsible for chiral interactions with an as yet uncharacterized receptor. Previous NMR studies have predicted the existence of a well-defined structure at the C-terminus of the C-peptide, kwown as the CAknuckle. We propose that the structure described here for the C-terminal pentapeptide is the CA-knuckle and represents the active site of the C-peptide of human proinsulin.

P2X receptors (P2XRs) are trimeric cation channels activated by extracellular ATP. Human P2XRs (P2X1-7) are expressed in nearly all mammalian tissues, and they are an important drug target because of their involvement in inflammation and neuropathic pain. The aim of this thesis is to address the following questions. P2XR crystal structures have revealed an unusual U-shape conformation for bound ATP; how does the U-shape conformation of ATP and its derivatives affect channel activation? Where and how do the selective, non-competitive inhibitors AZ10606120 and A438079 bind to P2X7R? What is the structure of the hP2X1R intracellular domain in the closed state? Molecular modelling and bioinformatics were used to answer these questions, hypotheses resulting from this work were tested in collaboration with Prof. Evans. Investigating the binding modes of ATP and its deoxy forms in hP2X1R showed that the ribose 2′-hydroxyl group is stabilising the U-shape conformation by a hydrogen bond to the γ-phosphate. The reduced ability of 2′-deoxy ATP to adopt the U-shape conformation could explain its weak agonist action in contrast to full agonists ATP and 3′-deoxy ATP. Ligand docking of AZ10606120 and A438079 into the hP2X7R predicted an allosteric binding site, this site has meanwhile been confirmed by P2X7R/antagonist X-ray structures. MD simulations suggested that unique P2X7R regions (residues 73-79 and T90/T94) contribute to an increase of the allosteric pocket volume compared to the hP2X1R. This difference in size might be the key for selectivity. The hP2X1R intracellular domain in the closed state was modelled ab initio, and interpreted in context of chemical cross-links (collaboration with Prof. Evans). This suggests a symmetrical arrangement of two short b-antiparallel strands within the Nterminal region and short a-helix in the C-terminal region and additional asymmetrical states.

P-glycoprotein (P-gp or ABCB1) is a membrane-bound active transporter belonging to the ABC protein superfamily. It is responsible for xenobioIc efflux and also contributes to multidrug resistance in diverse diseases including cancer and epilepsy. P-gp has been increasingly recognised as a potential target for future therapeutics. Although the protein has been studied for decades, understanding of the P-gp transport mechanism is still incomplete. Two P-gp orthologues, mouse (m) and human (h), were therefore expressed in yeasts and purified in the presence of the detergent, n-Dodecyl-β-D- Maltoside (DDM). Purified proteins were examined for aggregation and monodispersity via dynamic light scattering (DLS) and their thermal stability was determined by an assay using a thiol-specific dye (CPM). ATPase activity, measured in a detergent environment, showed that the proteins were active with a basal activity of 60 ± 4 and 35 ± 3 nmol/min/mg for mP-gp and hP-gp, respectively. Crystallisation trials were conducted in the presence of nucleotide. In meso crystallisation using commercial monoolein pre- dispensed plates yielded hexagonal crystal-like objects however they failed to diffract X- rays. P-gp samples were also subjected to cryo-EM where mP-gp in the post-hydrolytic (ADP-bound, vanadate-trapped) state provided the highest resolution dataset that led to a reconstruction of 3D density map at the resolution of 7.9 Å which showed an inward- facing conformation. Rigid-body model fitting unveiled densities that were not accounted for by the fitted model illustrating new features such as bound ADP, extended NBD1- TMD2 linker and alternative allocrite-binding sites. Ultimately, the knowledge of P-gp conformation alteration was enhanced and a refined alternating access mechanism of P- gp was proposed based upon information derived from this study.

Fragment assembly methods represent the state of the art in computational protein structure prediction. However, one limitation of these methods, particularly for larger protein structures, is inadequate conformational sampling. This thesis describes studies aimed at uncovering potential causes of ineffective sampling, and the development of methods to try and address these problems. To identify behaviours that might lead to poor conformational sampling, we developed measures to study fragment-based sampling trajectories. Applying these measures to the Rosetta Abinitio and EdaFold methods showed similarities and differences in the ways that these methods make predictions, and pointed to common limitations. In both protocols, structural features such as alpha-helices were more frequently altered during the search, as compared with regions such as loops. Analyses of the fragment libraries used by these methods showed that fragments covering loop regions were less likely to possess native-like structural features, and this likely exacerbated the problems of inadequate sampling in these regions. Inadequate loop sampling leads to poor fold-level exploration within individual runs of methods such as Rosetta, and this necessitates the use of many independent runs. Guided by these findings, we developed new heuristic-based search algorithms. These algorithms were designed to facilitate the exploration of multiple energy basins within runs. Over many runs, the enhanced exploration in our protocols produced decoy sets with larger fractions of native-like solutions as compared to runs of Rosetta. Experiments with different fragment sets indicated that our methods could better translate increased fragment set quality into improvements in predictive accuracy distributions. These improvements depend most strongly on the ability of search algorithms to reliably generate native-like structures using a fragment set. In contrast, inadequate retention of native-like decoys when associated with unfavourable score values appears to be less of an issue. This thesis shows that targeted developments in conformational sampling strategies can improve the accuracy and reliability of predictions. With effective conformational sampling methods, developments in methods for fragment set construction and other areas may more reliably enhance predictive ability.