The goals of gene prediction using computational approaches are to determine gene location and the corresponding functionality of the coding region. A subset of gene prediction is the gene structure prediction problem, which is to define the exon-intron boundaries of a gene. Gene prediction follows two general approaches: statistical patterns identification and sequence similarity comparison. Similarity based approaches have gained increasing popularity with the recent vast increase in genomic data in GenBank. The proposed gene prediction algorithm is a similarity based algorithm which capitalizes on the fact that similar sequences bear similar functions. The proposed algorithm, like most other similarity based algorithms, is based on dynamic programming. Given a genomic DNA, X = x1 xn and a closely related cDNA, Y = y1 yn, these sequences are aligned with matching pairs stored in a data set. These indexes of matching sets contain a large jumble of all matching pairs, with a lot of cross over indexes. Dynamic programming alignment is again used to retrieve the longest common non-crossing subsequence from the collection of matching fragments in the data set. This algorithm was implemented in Java on the Unix platform. Statistical comparisons were made against other software programs in the field. Statistical evaluation at both the DNA and exonic level were made against Est2genome, Sim4, Spidey, and Fgenesh-C. The proposed gene structure prediction algorithm, by far, has the best performance in the specificity category. The resulting specificity was greater than 98%. The proposed algorithm also has on par results in terms of sensitivity and correlation coeffcient. The goal of developing an algorithm to predict exonic regions with a very high level of correctness was achieved.

RNA molecules play important roles, including catalysis of chemical reactions and control of gene expression, and their functions largely depend on their folded structures. Since determining these structures by biochemical means is expensive, there is increased demand for computational predictions of RNA structures. One computational approach is to find the secondary structure (a set of base pairs) that minimizes a free energy function for a given RNA conformation. The forces driving RNA folding can be approximated by means of a free energy model, which associates a free energy parameter to a distinct considered feature. The main goal of this thesis is to develop state-of-the-art computational approaches that can significantly increase the accuracy (i.e., maximize the number of correctly predicted base pairs) of RNA secondary structure prediction methods, by improving and refining the parameters of the underlying RNA free energy model. We propose two general approaches to estimate RNA free energy parameters. The Constraint Generation (CG) approach is based on iteratively generating constraints that enforce known structures to have energies lower than other structures for the same molecule. The Boltzmann Likelihood (BL) approach infers a set of RNA free energy parameters which maximize the conditional likelihood of a set of known RNA structures. We discuss several variants and extensions of these two approaches, including a linear Gaussian Bayesian network that defines relationships between features. Overall, BL gives slightly better results than CG, but it is over ten times more expensive to run. In addition, CG requires software that is much simpler to implement. We obtain significant improvements in the accuracy of RNA minimum free energy secondary structure prediction with and without pseudoknots (regions of non-nested base pairs), when measured on large sets of RNA molecules with known structures. For the Turner model, which has been the gold-standard model without pseudoknots for more than a decade, the average prediction accuracy of our new parameters increases from 60% to 71%. For two models with pseudoknots, we obtain an increase of 9% and 6%, respectively. To the best of our knowledge, our parameters are currently state-of-the-art for the three considered models.

No description available.

RNA molecules play important roles, including catalysis of chemical reactions and control of gene expression, and their functions largely depend on their folded structures. Since determining these structures by biochemical means is expensive, there is increased demand for computational predictions of RNA structures. One computational approach is to find the secondary structure (a set of base pairs) that minimizes a free energy function for a given RNA conformation. The forces driving RNA folding can be approximated by means of a free energy model, which associates a free energy parameter to a distinct considered feature. The main goal of this thesis is to develop state-of-the-art computational approaches that can significantly increase the accuracy (i.e., maximize the number of correctly predicted base pairs) of RNA secondary structure prediction methods, by improving and refining the parameters of the underlying RNA free energy model. We propose two general approaches to estimate RNA free energy parameters. The Constraint Generation (CG) approach is based on iteratively generating constraints that enforce known structures to have energies lower than other structures for the same molecule. The Boltzmann Likelihood (BL) approach infers a set of RNA free energy parameters which maximize the conditional likelihood of a set of known RNA structures. We discuss several variants and extensions of these two approaches, including a linear Gaussian Bayesian network that defines relationships between features. Overall, BL gives slightly better results than CG, but it is over ten times more expensive to run. In addition, CG requires software that is much simpler to implement. We obtain significant improvements in the accuracy of RNA minimum free energy secondary structure prediction with and without pseudoknots (regions of non-nested base pairs), when measured on large sets of RNA molecules with known structures. For the Turner model, which has been the gold-standard model without pseudoknots for more than a decade, the average prediction accuracy of our new parameters increases from 60% to 71%. For two models with pseudoknots, we obtain an increase of 9% and 6%, respectively. To the best of our knowledge, our parameters are currently state-of-the-art for the three considered models. / Science, Faculty of / Computer Science, Department of / Graduate

The most significant impediment for protein structure prediction is the inadequacy of conformation space search. Conformation space is too large and the energy landscape too rugged for existing search methods to consistently find near-optimal minima. Conformation space search methods thus have to focus exploration on a small fraction of the search space. The ability to choose appropriate regions, i.e. regions that are highly likely to contain the native state, critically impacts the effectiveness of search. To make the choice of where to explore requires information, with higher quality information resulting in better choices. Most current search methods are designed to work in as many domains as possible, which leads to less accurate information because of the need for generality. However, most domains provide unique, and accurate information. To best utilize domain specific information search needs to be customized for each domain. The first contribution of this thesis customizes search for protein structure prediction, resulting in significantly more accurate protein structure predictions. Unless information is perfect, mistakes will be made, and search will focus on regions that do not contain the native state. How search recovers from mistakes is critical to its effectiveness. To recover from mistakes, this thesis introduces the concept of adaptive balancing of exploitation with exploration. Adaptive balancing of exploitation with exploration allows search to use information only to the extent to which it guides exploration toward the native state. Existing methods of protein structure prediction rely on information from known proteins. Currently, this information is from either full-length proteins that share similar sequences, and hence have similar structures (homologs), or from short protein fragments. Homologs and fragments represent two extremes on the spectrum of information from known proteins. Significant additional information can be found between these extremes. However, current protein structure prediction methods are unable to use information between fragments and homologs because it is difficult to identify the correct information from the enormous amount of incorrect information. This thesis makes it possible to use information between homologs and fragments by adaptively balancing exploitation with exploration in response to an estimate of template protein quality. My results indicate that integrating the information between homologs and fragments significantly improves protein structure prediction accuracy, resulting in several proteins predicted with <1>°A RMSD resolution.

First--principles electronic structure calculations have been performed to help identify and direct the synthesis of new superhard compounds. An improved figure of merit for hardness is identified and used to show that carbon nitrides are not likely to be harder than diamond. / Ph. D.

Yes / Mandelic acids are prototypic chiral molecules where the sensitivity of crystallized forms (enantiopure/racemic compound/polymorphs) to both conditions and substituents provides a new insight into the factors that may allow chiral separation by crystallization. The determination of a significant number of single crystal structures allows the analysis of 13 enantiopure and 30 racemic crystal structures of 21 (F/Cl/Br/CH3/CH3O) substituted mandelic acid derivatives. There are some common phenyl packing motifs between some groups of racemic and enantiopure structures, although they show very different hydrogen-bonding motifs. The computed crystal energy landscape of 3-chloromandelic acid, which has at least two enantiopure and three racemic crystal polymorphs, reveals that there are many more possible structures, some of which are predicted to be thermodynamically more favorable as well as slightly denser than the known forms. Simulations of mandelic acid dimers in isolation, water, and toluene do not differentiate between racemic and enantiopure dimers and also suggest that the phenyl ring interactions play a major role in the crystallization mechanism. The observed crystallization behavior of mandelic acids does not correspond to any simple “crystal engineering rules” as there is a range of thermodynamically feasible structures with no distinction between the enantiopure and racemic forms. Nucleation and crystallization appear to be determined by the kinetics of crystal growth with a statistical bias, but the diversity of the mandelic acid crystallization behavior demonstrates that the factors that influence the kinetics of crystal nucleation and growth are not yet adequately understood. / EPSRC, Max Planck Society for the Advancement of Sciences, UCL-MPS Impact Ph.D. Fellowship, EU COST Action

A phenomenon as complex as protein folding requires a complex model to approximate it. This thesis presents a bottom-up approach for building complex probabilistic models of protein secondary structure by incorporating the multiple information sources which we call experts. Expert opinions are represented by probability distributions over the set of possible structures. Bayesian treatment of a group of experts results in a consensus opinion that combines the experts' probability distributions using the operators of normalized product, quotient and exponentiation. The expression of this consensus opinion simplifiesto a product of the expert opinions with two assumptions: (1) balanced training of experts, i. e. , uniform prior probability over all structures, and (2) conditional independence between expert opinions,given the structure. This research also studies how Markov chains and hidden Markov models may be used to represent expert opinion. Closure properties areproven, and construction algorithms are given for product of hidden Markov models, and product, quotient and exponentiation of Markovchains. Algorithms for extracting single-structure predictions from these models are also given. Current product-of-experts approaches in machine learning are top-down modeling strategies that assume expert independence, and require simultaneous training of all experts. This research describes a bottom-up modeling strategy that can incorporate conditionally dependent experts, and assumes separately trained experts.

The physical and chemical properties of materials are intimately related to their underlying crystal structure: the detailed arrangement of atoms and chemical bonds within. This thesis uses computational methods to predict crystal structure, with a particular focus on structures and stable phases that emerge at high pressure. We explore three distinct systems. We first apply the ab initio random structure searching (AIRSS) technique and density functional theory (DFT) calculations to investigate the high-pressure behaviour of beryllium, magnesium and calcium difluorides. We find that beryllium fluoride is extensively polymorphic at low pressures, and predict two new phases for this compound - the silica moganite and CaCl$_2$ structures - to be stable over the wide pressure range 12-57 GPa. For magnesium fluoride, our results show that the orthorhombic `O-I' TiO$_2$ structure ($Pbca$, $Z=8$) is stable for this compound between 40 and 44 GPa. Our searches find no new phases at the static-lattice level for calcium difluoride between 0 and 70 GPa; however, a phase with $P\overline{6}2m$ symmetry is energetically close to stability over this pressure range, and our calculations predict that this phase is stabilised at high temperature. The $P\overline{6}2m$ structure exhibits an unstable phonon mode at large volumes which may signal a transition to a superionic state at high temperatures. The Group-II difluorides are isoelectronic to a number of other AB$_2$-type compounds such as SiO$_2$ and TiO$_2$, and we discuss our results in light of these similarities. Compressed hydrogen sulfide (H$_2$S) has recently attracted experimental and theoretical interest due to the observation of high-temperature superconductivity in this compound ($T_c$ = 203 K) at high pressure (155 GPa). We use the AIRSS technique and DFT calculations to determine the stable phases and chemical stoichiometries formed in the hydrogen-sulfur system as a function of pressure. We find that this system supports numerous stable compounds: H$_3$S, H$_7$S$_3$, H$_2$S, H$_3$S$_2$, H$_4$S$_3$, H$_2$S$_3$ and HS$_2$, at various pressures. Working as part of a collaboration, our predicted H$_3$S and H$_4$S$_3$ structures are shown to be consistent with XRD data for this system, with H$_4$S$_3$ identified as a major decomposition product of H$_2$S in the lead-up to the superconducting state. Calcium and oxygen are two elements of generally high terrestrial and cosmic abundance, and we explore structures of calcium peroxide (CaO$_2$) in the pressure range 0-200 GPa. Stable structures for CaO$_2$ with $C2/c$, $I4/mcm$ and $P2_1/c$ symmetries emerge at pressures below 40 GPa, which we find are thermodynamically stable against decomposition into CaO and O$_2$. The stability of CaO$_2$ with respect to decomposition increases with pressure, with peak stability occurring at the CaO B1-B2 phase transition at 65 GPa. Phonon calculations using the quasiharmonic approximation show that CaO$_2$ is a stable oxide of calcium at mantle temperatures and pressures, highlighting a possible role for CaO$_2$ in planetary geochemistry, as a mineral redox buffer. We sketch the phase diagram for CaO$_2$, and find at least five new stable phases in the pressure/temperature ranges 0 $\leq P\leq$ 60 GPa, 0 $\leq T\leq$ 600 K, including two new candidates for the zero-pressure ground state structure.

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.