Thesis advisor: Peter Clote / In addition to the well-characterized messenger RNA, transfer RNA and ribosomal RNA, many new classes of noncoding RNA(ncRNA) have been discovered in the past few years. ncRNA has been shown to play important roles in multiple regulation and development processes. The increasing needs for RNA structural analysis software provide great opportunities on computational biologists. In this thesis I present three highly non-trivial RNA parametric structural analysis algorithms: 1) RNAhairpin and RNAmultiloop, which calculate parition functions with respect to hairpin number, multiloop number and multiloop order, 2) RNAshapeEval, which is based upon partition function calculation with respect to a fixed abstract shape, and 3) RNAprofileZ, which calculates the expected partition function and ensemble free energy given an RNA position weight matrix.I also describe the application of these software in biological problems, including evaluating purine riboswitch aptamer full alignment sequences to adopt their consensus shape, building hairpin and multiloop profiles for certain Rfam families, tRNA and pseudoknotted RNA secondary structure predictions. These algorithms hold the promise to be useful in a broad range of biological problems such as structural motifs search, ncRNA gene finders, canonical and pseudoknotted secondary structure predictions. / Thesis (MS) — Boston College, 2010. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Biology.

A recent line of works established a remarkable connection for antiferromagnetic 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximating the partition function for graphs with maximum degree \Delta undergoes a computational transition that coincides with the statistical physics uniqueness/non-uniqueness phase transition on the infinite \Delta-regular tree. Despite this clear picture for 2-spin systems, there is little known for multi-spin systems. We present the first analog of the above inapproximability results for multi-spin systems. The main difficulty in previous inapproximability results was analyzing the behavior of the model on random \Delta-regular bipartite graphs, which served as the gadget in the reduction. To this end one needs to understand the moments of the partition function. Our key contribution is connecting: (i) induced matrix norms, (ii) maxima of the expectation of the partition function, and (iii) attractive fixed points of the associated tree recursions (belief propagation). We thus obtain a generic analysis of the Gibbs distribution of any multi-spin system on random regular bipartite graphs. We also treat in depth the k-colorings and the q-state antiferromagnetic Potts models. Based on these findings, we prove that for \Delta constant and even k<\Delta, it is NP-hard to approximate within an exponential factor the number of k-colorings on triangle-free \Delta-regular graphs. We also prove an analogous statement for the antiferromagnetic Potts model. Our hardness results for these models complement the conjectured regime where the models are believed to have efficient approximation schemes. We systematize the approach to obtain a general theorem for the computational hardness of counting in antiferromagnetic spin systems, which we ultimately use to obtain the inapproximability results for the k-colorings and q-state antiferromagnetic Potts models, as well as (the previously known results for) antiferromagnetic 2-spin systems. The criterion captures in an appropriate way the statistical physics uniqueness phase transition on the tree.

<p> Recent investigations by H. G. Thode, J. Macnamara and C. Collins have shown that the S^32/S^34 ratio in natural sulfur-containing compounds varies by as much as five percent. These wide-spread variations suggest that fractionation of the sulfur isotopes occurs in natural processes due to differences in the chemical properties of isotopic molecules. In order to determine the magnitude of the effects that could be expected, partition function ratios for isotopic molecules containing sulfur and equilibrium constants for many isotopic exchange reactions involving sulfur have been calculated by methods of statistical mechanics. The results of these calculations are discussed. </p> / Thesis / Master of Science (MSc)

Doctor of Philosophy / Department of Chemistry / Paul E. Smith / Molecular Dynamics (MD) simulations have played an important role in providing detailed atomic information for the study of biological systems. The quality of an MD simulation depends on both the degree of sampling and the accuracy of force field. Kirkwood-Buff (KB) theory provides a relationship between species distributions from simulation results and thermodynamic properties from experiments. Recently, it has been used to develop new, hopefully improved, force fields and to study preferential interactions. Here we combine KB theory and MD simulations to study a variety of intermolecular interactions in solution. Firstly, we present a force field for neutral amines and carboxylic acids. The parameters were developed to reproduce the composition dependent KB integrals obtained from an analysis of the experimental data, allowing for accurate descriptions of activities involved with uncharged N-terminus and lysine residues, as well as the protonated states for the C-terminus and both aspartic and glutamic acids. Secondly, the KB force fields and KB theory are used to investigate the urea cosolvent effect on peptide aggregation behavior by molecular dynamics simulation. Neo-pentane, benzene, glycine and methanol are selected to represent different characteristics of proteins. The chemical potential derivatives with respect to the cosolvent concentrations are calculated and analyzed, and the four solutes exhibit large differences. Finally, the contributions from the vibrational partition function to the total free energy and enthalpy changes are investigated for several systems and processes including: the enthalpy of evaporation, the free energy of solvation, the activity of a solute in solution, protein folding, and the enthalpy of mixing. The vibrational frequencies of N-methylacetamide, acetone and water are calculated using density functional theory and MD simulations. We argue that the contributions from the vibrational partition function are large and in classical force fields these contributions should be implicitly included by the use of effective intermolecular interactions.

Spanning tree congestion was defined by Ostrovskii (2004) as a measure of how well a network can perform if only minimal connection can be maintained. We compute the parameter for several families of graphs. In particular, by partitioning a hypercube into pieces with almost optimal edge-boundaries, we give tight estimates of the parameter thereby disproving a conjecture of Hruska (2008). For a typical random graph, the parameter exhibits a zigzag behaviour reflecting the feature that it is not monotone in the number of edges. This motivates the study of the most congested graphs where we show that any graph is close to a graph with small congestion. Next, we enumerate independent sets. Using the independent set polynomial, we compute the extrema of averages in trees and graphs. Furthermore, we consider inverse problems among trees and resolve a conjecture of Wagner (2009). A result in a more general setting is also proved which answers a question of Alon, Haber and Krivelevich (2011). After briefly considering polynomial invariants of general graphs, we specialize into trees. Three levels of tree distinguishing power are exhibited. We show that polynomials which do not distinguish rooted trees define typically exponentially large equivalence classes. On the other hand, we prove that the rooted Ising polynomial distinguishes rooted trees and that the Negami polynomial determines the subtree polynomial, strengthening results of Bollobás and Riordan (2000) and Martin, Morin and Wagner (2008). The top level consists of the chromatic symmetric function and it is proved to be a complete invariant for caterpillars.

This thesis studies certain aspects of the global properties, including geometric and arithmetic, of the moduli spaces of complex structures of some special Calabi-Yau threefolds (B-model), and of the corresponding topological string partition functions defined from them which are closely related to the generating functions of Gromov-Witten invariants of their mirror Calabi-Yau threefolds (A-model) by the mirror symmetry conjecture. / Mathematics

This thesis introduces normal factor graphs under a new semantics, namely, the exterior function semantics. Initially, this work was motivated by two distinct lines of research. One line is ``holographic algorithms,'' a powerful approach introduced by Valiant for solving various counting problems in computer science; the other is ``normal graphs,'' an elegant framework proposed by Forney for representing codes defined on graphs. The nonrestrictive normality constraint enables the notion of holographic transformations for normal factor graphs. We establish a theorem, called the generalized Holant theorem, which relates a normal factor graph to its holographic transformation. We show that the generalized Holant theorem on one hand underlies the principle of holographic algorithms, and on the other reduces to a general duality theorem for normal factor graphs, a special case of which was first proved by Forney. As an application beyond Forney's duality, we show that the normal factor graphs duality facilitates the approximation of the partition function for the two-dimensional nearest-neighbor Potts model. In the course of our development, we formalize a new semantics for normal factor graphs, which highlights various linear algebraic properties that enables the use of normal factor graphs as a linear algebraic tool. Indeed, we demonstrate the ability of normal factor graphs to encode several concepts from linear algebra and present normal factor graphs as a generalization of ``trace diagrams.'' We illustrate, with examples, the workings of this framework and how several identities from linear algebra may be obtained using a simple graphical manipulation procedure called ``vertex merging/splitting.'' We also discuss translation association schemes with the aid of normal factor graphs, which we believe provides a simple approach to understanding the subject. Further, under the new semantics, normal factor graphs provide a probabilistic model that unifies several graphical models such as factor graphs, convolutional factor graphs, and cumulative distribution networks.

A new methodology is developed to calculate density of states of interstellar and atmospheric clusters that takes account of their loosely bound nature and incorporates kinetically important angular momentum constraints explicitly. The method is based on classical phase space integration for the intermonomer modes of the cluster with imposition of the constraints of selected total energy and total angular momentum. It achieves considerable efficiency via essentially analytic evaluation of the momentum space integrals coupled with efficient Monte Carlo sampling of configurations. The derivation for the equation for the density of states is outlined and all steps in the simplification of the accessible momentum space volume are detailed. The method is tested rigorously against an entirely analytic result obtained for the ideal case of a dimer with spherical top fragments and no interaction potential. Interstellar applications of the new approach are presented for (HCN)2 and (CO)2. The new intermononmer density of states has been integrated over metastable states to obtain the intermonomer partition function, which in turn is used to calculate the metastable equilibrium constants for interstellar clusters, which in turn is used tocalculate the second order rate constant of overall dimer formation in the interstellar environment. Atmospheric applications of the new approach are presented for (H2O)2. The new intermonomer density of states is convoluted with the intramonomer density of states to obtain the convoluted density of states. This convoluted density of states is then integrated over total energy and angular momentum to obtain the anharmonic partition function, which in turn is used to calculate the equilibrium constant for atmospheric clusters, which in turn is used to calculate the third order rate constant for overall dimer formation in the atmospheric environment. Kinetic quantities are also calculated with the intermonomer and convoluted density of states for interstellar and atmospheric clusters, respectively. These densities of states are combined with RRKM theory to compute unimolecular dissociation rate constants, which are then averaged with respect to the thermal capture flux distribution to compute average lifetimes as a function of temperature.

A new methodology is developed to calculate density of states of interstellar and atmospheric clusters that takes account of their loosely bound nature and incorporates kinetically important angular momentum constraints explicitly. The method is based on classical phase space integration for the intermonomer modes of the cluster with imposition of the constraints of selected total energy and total angular momentum. It achieves considerable efficiency via essentially analytic evaluation of the momentum space integrals coupled with efficient Monte Carlo sampling of configurations. The derivation for the equation for the density of states is outlined and all steps in the simplification of the accessible momentum space volume are detailed. The method is tested rigorously against an entirely analytic result obtained for the ideal case of a dimer with spherical top fragments and no interaction potential. Interstellar applications of the new approach are presented for (HCN)2 and (CO)2. The new intermononmer density of states has been integrated over metastable states to obtain the intermonomer partition function, which in turn is used to calculate the metastable equilibrium constants for interstellar clusters, which in turn is used tocalculate the second order rate constant of overall dimer formation in the interstellar environment. Atmospheric applications of the new approach are presented for (H2O)2. The new intermonomer density of states is convoluted with the intramonomer density of states to obtain the convoluted density of states. This convoluted density of states is then integrated over total energy and angular momentum to obtain the anharmonic partition function, which in turn is used to calculate the equilibrium constant for atmospheric clusters, which in turn is used to calculate the third order rate constant for overall dimer formation in the atmospheric environment. Kinetic quantities are also calculated with the intermonomer and convoluted density of states for interstellar and atmospheric clusters, respectively. These densities of states are combined with RRKM theory to compute unimolecular dissociation rate constants, which are then averaged with respect to the thermal capture flux distribution to compute average lifetimes as a function of temperature.

A new methodology is developed to calculate density of states of interstellar and atmospheric clusters that takes account of their loosely bound nature and incorporates kinetically important angular momentum constraints explicitly. The method is based on classical phase space integration for the intermonomer modes of the cluster with imposition of the constraints of selected total energy and total angular momentum. It achieves considerable efficiency via essentially analytic evaluation of the momentum space integrals coupled with efficient Monte Carlo sampling of configurations. The derivation for the equation for the density of states is outlined and all steps in the simplification of the accessible momentum space volume are detailed. The method is tested rigorously against an entirely analytic result obtained for the ideal case of a dimer with spherical top fragments and no interaction potential. Interstellar applications of the new approach are presented for (HCN)2 and (CO)2. The new intermononmer density of states has been integrated over metastable states to obtain the intermonomer partition function, which in turn is used to calculate the metastable equilibrium constants for interstellar clusters, which in turn is used tocalculate the second order rate constant of overall dimer formation in the interstellar environment. Atmospheric applications of the new approach are presented for (H2O)2. The new intermonomer density of states is convoluted with the intramonomer density of states to obtain the convoluted density of states. This convoluted density of states is then integrated over total energy and angular momentum to obtain the anharmonic partition function, which in turn is used to calculate the equilibrium constant for atmospheric clusters, which in turn is used to calculate the third order rate constant for overall dimer formation in the atmospheric environment. Kinetic quantities are also calculated with the intermonomer and convoluted density of states for interstellar and atmospheric clusters, respectively. These densities of states are combined with RRKM theory to compute unimolecular dissociation rate constants, which are then averaged with respect to the thermal capture flux distribution to compute average lifetimes as a function of temperature.