Expedition in Data and Harmonic Analysis on Graphs

The graph Laplacian operator is widely studied in spectral graph theory largely due to its importance in modern data analysis. Recently, the Fourier transform and other time-frequency operators have been defined on graphs using Laplacian eigenvalues and eigenvectors. We extend these results and prove that the translation operator to the i’th node is invertible if and only if all eigenvectors are nonzero on the i’th node. Because of this dependency on the support of eigenvectors we study the characteristic set of Laplacian eigenvectors. We prove that the Fiedler vector of a planar graph cannot vanish on large neighborhoods and then explicitly construct a family of non-planar graphs that do exhibit this property. We then prove original results in modern analysis on graphs. We extend results on spectral graph wavelets to create vertex-dyanamic spectral graph wavelets whose support depends on both scale and translation parameters. We prove that Spielman’s Twice-Ramanujan graph sparsifying algorithm cannot outperform his conjectured optimal sparsification constant. Finally, we present numerical results on graph conditioning, in which edges of a graph are rescaled to best approximate the complete graph and reduce average commute time.

STRUCTURE AND FUNCTION OF THE GROUP III CHAPERONINS, A UNIQUE CLADE OF PROTEIN FOLDING NANOMACHINES

The survival and descent of cells is universally dependent on maintaining their proteins in a properly folded condition. It is widely accepted that the information for the folding of the nascent polypeptide chain into a native protein is encrypted in the amino acid sequence, and the Nobel Laureate Christian Anfinsen was the first to demonstrate that a protein could spontaneously refold after complete unfolding. However, it became clear that the observed folding rates for many proteins were much slower than rates estimated in vivo. This led to the recognition of required protein-protein interactions that promote proper folding. A unique group of proteins, the molecular chaperones, are responsible for maintaining protein homeostasis during normal growth as well as stress conditions. Chaperonins (CPNs) are ubiquitous and essential chaperones. They form ATP-dependent, hollow complexes that encapsulate polypeptides in two back-to-back stacked multisubunit rings, facilitating protein folding through highly cooperative allosteric articulation. CPNs are usually classified into Group I and Group II. Here, I report the characterization of a novel CPN belonging to a third Group, recently discovered in bacteria. Group III CPNs have close phylogenetic association to the Group II CPNs found in Archaea and Eukarya, and may be a relic of the Last Common Ancestor of the CPN family. The gene encoding the Group III CPN from Carboxydothermus hydrogenoformans and Candidatus Desulforudis audaxviator was cloned in E. coli and overexpressed in order to both characterize the protein and to demonstrate its ability to function as an ATPase chaperone. The opening and closing cycle of the Chy chaperonin was examined via site-directed mutations affecting the ATP binding site at R155. To relate the mutational analysis to the structure of the CPN, the crystal structure of both the AMP-PNP (an ATP analogue) and ADP bound forms were obtained in collaboration with Sun-Shin Cha in Seoul, South Korea. The ADP and ATP binding site substitutions resulted in frozen forms of the structures in open and closed conformations. From this, mutants were designed to validate hypotheses regarding key ATP interacting sites as well as important stabilizing interactions, and to observe the physical properties of the resulting complexes by calorimetry.