Numerical methods for ill-posed, linear problems

A means of assessing the effectiveness of methods used in the numerical solution of various linear ill-posed problems is outlined. Two methods: Tikhonov' s method of regularization and the quasireversibility method of Lattès and Lions are appraised from this point of view.

In the former method, Tikhonov provides a useful means for incorporating a constraint into numerical algorithms. The analysis suggests that the approach can be generalized to embody constraints other than those employed by Tikhonov. This is effected and the general "T-method" is the result.

A T-method is used on an extended version of the backwards heat equation with spatially variable coefficients. Numerical computations based upon it are performed.

The statistical method developed by Franklin is shown to have an interpretation as a T-method. This interpretation, although somewhat loose, does explain some empirical convergence properties which are difficult to pin down via a purely statistical argument.

Mathematical study of complex networks : brain, internet, and power grid

The dissertation is concerned with the mathematical study of various network problems. First, three real-world networks are considered: (i) the human brain network (ii) communication networks, (iii) electric power networks. Although these networks perform very different tasks, they share similar mathematical foundations. The high-level goal is to analyze and/or synthesis each of these systems from a “control and optimization” point of view. After studying these three real-world networks, two abstract network problems are also explored, which are motivated by power systems. The first one is “flow optimization over a flow network” and the second one is “nonlinear optimization over a generalized weighted graph”. The results derived in this dissertation are summarized below.

Brain Networks: Neuroimaging data reveals the coordinated activity of spatially distinct brain regions, which may be represented mathematically as a network of nodes (brain regions) and links (interdependencies). To obtain the brain connectivity network, the graphs associated with the correlation matrix and the inverse covariance matrix—describing marginal and conditional dependencies between brain regions—have been proposed in the literature. A question arises as to whether any of these graphs provides useful information about the brain connectivity. Due to the electrical properties of the brain, this problem will be investigated in the context of electrical circuits. First, we consider an electric circuit model and show that the inverse covariance matrix of the node voltages reveals the topology of the circuit. Second, we study the problem of finding the topology of the circuit based on only measurement. In this case, by assuming that the circuit is hidden inside a black box and only the nodal signals are available for measurement, the aim is to find the topology of the circuit when a limited number of samples are available. For this purpose, we deploy the graphical lasso technique to estimate a sparse inverse covariance matrix. It is shown that the graphical lasso may find most of the circuit topology if the exact covariance matrix is well-conditioned. However, it may fail to work well when this matrix is ill-conditioned. To deal with ill-conditioned matrices, we propose a small modification to the graphical lasso algorithm and demonstrate its performance. Finally, the technique developed in this work will be applied to the resting-state fMRI data of a number of healthy subjects.

Communication Networks: Congestion control techniques aim to adjust the transmission rates of competing users in the Internet in such a way that the network resources are shared efficiently. Despite the progress in the analysis and synthesis of the Internet congestion control, almost all existing fluid models of congestion control assume that every link in the path of a flow observes the original source rate. To address this issue, a more accurate model is derived in this work for the behavior of the network under an arbitrary congestion controller, which takes into account of the effect of buffering (queueing) on data flows. Using this model, it is proved that the well-known Internet congestion control algorithms may no longer be stable for the common pricing schemes, unless a sufficient condition is satisfied. It is also shown that these algorithms are guaranteed to be stable if a new pricing mechanism is used.

Electrical Power Networks: Optimal power flow (OPF) has been one of the most studied problems for power systems since its introduction by Carpentier in 1962. This problem is concerned with finding an optimal operating point of a power network minimizing the total power generation cost subject to network and physical constraints. It is well known that OPF is computationally hard to solve due to the nonlinear interrelation among the optimization variables. The objective is to identify a large class of networks over which every OPF problem can be solved in polynomial time. To this end, a convex relaxation is proposed, which solves the OPF problem exactly for every radial network and every meshed network with a sufficient number of phase shifters, provided power over-delivery is allowed. The concept of “power over-delivery” is equivalent to relaxing the power balance equations to inequality constraints.

Flow Networks: In this part of the dissertation, the minimum-cost flow problem over an arbitrary flow network is considered. In this problem, each node is associated with some possibly unknown injection, each line has two unknown flows at its ends related to each other via a nonlinear function, and all injections and flows need to satisfy certain box constraints. This problem, named generalized network flow (GNF), is highly non-convex due to its nonlinear equality constraints. Under the assumption of monotonicity and convexity of the flow and cost functions, a convex relaxation is proposed, which always finds the optimal injections. A primary application of this work is in the OPF problem. The results of this work on GNF prove that the relaxation on power balance equations (i.e., load over-delivery) is not needed in practice under a very mild angle assumption.

Generalized Weighted Graphs: Motivated by power optimizations, this part aims to find a global optimization technique for a nonlinear optimization defined over a generalized weighted graph. Every edge of this type of graph is associated with a weight set corresponding to the known parameters of the optimization (e.g., the coefficients). The motivation behind this problem is to investigate how the (hidden) structure of a given real/complex valued optimization makes the problem easy to solve, and indeed the generalized weighted graph is introduced to capture the structure of an optimization. Various sufficient conditions are derived, which relate the polynomial-time solvability of different classes of optimization problems to weak properties of the generalized weighted graph such as its topology and the sign definiteness of its weight sets. As an application, it is proved that a broad class of real and complex optimizations over power networks are polynomial-time solvable due to the passivity of transmission lines and transformers.

The deep ocean density structure at the Last Glacial Maximum : What was it and why?

The search for reliable proxies of past deep ocean temperature and salinity has proved difficult, thereby limiting our ability to understand the coupling of ocean circulation and climate over glacial-interglacial timescales. Previous inferences of deep ocean temperature and salinity from sediment pore fluid oxygen isotopes and chlorinity indicate that the deep ocean density structure at the Last Glacial Maximum (LGM, approximately 20,000 years BP) was set by salinity, and that the density contrast between northern and southern sourced deep waters was markedly greater than in the modern ocean. High density stratification could help explain the marked contrast in carbon isotope distribution recorded in the LGM ocean relative to that we observe today, but what made the ocean's density structure so different at the LGM? How did it evolve from one state to another? Further, given the sparsity of the LGM temperature and salinity data set, what else can we learn by increasing the spatial density of proxy records?

We investigate the cause and feasibility of a highly and salinity stratified deep ocean at the LGM and we work to increase the amount of information we can glean about the past ocean from pore fluid profiles of oxygen isotopes and chloride. Using a coupled ocean--sea ice--ice shelf cavity model we test whether the deep ocean density structure at the LGM can be explained by ice--ocean interactions over the Antarctic continental shelves, and show that a large contribution of the LGM salinity stratification can be explained through lower ocean temperature. In order to extract the maximum information from pore fluid profiles of oxygen isotopes and chloride we evaluate several inverse methods for ill-posed problems and their ability to recover bottom water histories from sediment pore fluid profiles. We demonstrate that Bayesian Markov Chain Monte Carlo parameter estimation techniques enable us to robustly recover the full solution space of bottom water histories, not only at the LGM, but through the most recent deglaciation and the Holocene up to the present. Finally, we evaluate a non-destructive pore fluid sampling technique, Rhizon samplers, in comparison to traditional squeezing methods and show that despite their promise, Rhizons are unlikely to be a good sampling tool for pore fluid measurements of oxygen isotopes and chloride.

Developmentally regulated transcription factors in Drosophila melanogaster

During early stages of Drosophila development the heat shock response cannot be induced. It is reasoned that the adverse effects on cell cycle and cell growth brought about by Hsp70 induction must outweigh the beneficial aspects of Hsp70 induction in the early embryo. Although the Drosophila heat shock transcription factor (dHSF) is abundant in the early embryo, it does not enter the nucleus in response to heat shock. In older embryos and in cultured cells the factor is localized within the nucleus in an apparent trimeric structure that binds DNA with high affinity. The domain responsible for nuclear localization upon stress resides between residues 390 and 420 of the dHSF. Using that domain as bait in a yeast two-hybrid system we now report the identification and cloning of a nuclear transport protein Drosophila karyopherin-α3(dKap- α3). Biochemical methods demonstrate that the dKap-α3 protein binds specifically to the dHSF's nuclear localization sequence (NLS). Furthermore, the dKap-α3 protein does not associate with NLSs that contain point mutations which are not transported in vivo. Nuclear docking studies also demonstrate specific nuclear targeting of the NLS substrate by dKap-α3.Consistant with previous studies demonstrating that early Drosophila embryos are refractory to heat shock as a result of dHSF nuclear exclusion, we demonstrate that the early embryo is deficient in dKap-α3 protein through cycle 12. From cycle 13 onward the transport factor is present and the dHSF is localized within the nucleus thus allowing the embryo to respond to heat shock.

The pair-rule gene fushi tarazu (ftz) is a well-studied zygotic segmentation gene that is necessary for the development of the even-numbered parasegments in Drosophila melanogastor. During early embryogenesis, ftz is expressed in a characteristic pattern of seven stripes, one in each of the even-numbered parasegments. With a view to understand how ftz is transcriptionally regulated, cDNAs that encode transcription factors that bind to the zebra element of the ftz promoter have been cloned. Chapter Ill reports the cloning and characterization of the eDNA encoding zeb-1 (zebra element binding protein), a novel steroid receptor-like molecule that specifically binds to a key regulatory element of the ftz promoter. In transient transfection assays employing Drosophila tissue culture cells, it has been shown that zeb-1 as well as a truncated zeb-1 polypeptide (zeb480) that lacks the putative ligand binding domain function as sequencespecific trans-activators of the ftz gene.

The Oct factors are members of the POU family of transcription factors that are shown to play important roles during development in mammals. Chapter IV reports the eDNA cloning and expression of a Drosophila Oct transcription factor. Whole mount in-situ hybridization experiments revealed that the spatial expression patterns of this gene during embryonic development have not yet been observed for any other gene. In early embryogenesis, its transcripts are transiently expressed as a wide uniform band from 20-40% of the egg length, very similar to that of gap genes. This pattern progressively resolves into a series of narrower stripes followed by expression in fourteen stripes. Subsequently, transcripts from this gene are expressed in the central nervous system and the brain. When expressed in the yeast Saccharomyces cerevisiae, this Drosophila factor functions as a strong, octamer-dependent activator of transcription. The data strongly suggest possible functions for the Oct factor in pattern formation in Drosophila that might transcend the boundaries of genetically defined segmentation genes.

Model studies of Ziegler-Natta olefin polymerization using group 3 and group 4 metallocenes

Evidence for the stereochemical isomerization of a variety of ansa metallocene compounds is presented. For the scandocene allyl derivatives described here, we have established that the process is promoted by a variety of salts in both ether and hydrocarbon solvents and is not accelerated by light. A plausible mechanism based on an earlier proposal by Marks, et al., is offered as an explanation of this process. It involves coordination of anions and/or donor solvents to the metal center with cation assistance to encourage metalcyclopentadienyl bond heterolysis, rotation about the Si-Cp bond of the detached cyclopentadienide and recoordination of the opposite face. Our observations in some cases of thermodynamic racemic:meso ratios under the reaction conditions commonly used for the synthesis of the metallocene chlorides suggests that the interchange is faster than metallation, such that the composition of the reaction mixture is determined by thermodynamic, not kinetic, control in these cases.

Two new ansa-scandocene alkenyl compounds react with olefins resulting in the formation of η³-allyl complexes. Kinetics and labeling experiments indicate a tuck-in intermediate on the reaction pathway; in this intermediate the metal is bound to the carbon adjacent to the silyllinker in the rear of the metallocene wedge. In contrast, reaction of permethylscandocene alkenyl compounds with olefins results, almost exclusively, in vinylic C-H bond activation. It is proposed that relieving transition state steric interactions between the cyclopentadienyl rings and the olefin by either linking the rings together or using a larger lanthanide metal may allow for olefin coordination, stabilizing the transition state for allylic σ-bond metathesis.

A selectively isotopically labeled propylene, CH₂CD(¹³CH₃), was synthesized and its polymerization was carried out at low concentration in toluene solution using isospecific metallocene catalysts. Analysis of the NMR spectra (¹³C, ¹H, and ²H) of the resultant polymers revealed that the production of stereoerrors through chain epimerization proceeds exclusively by the tertiaryalkyl mechanism. Additionally, enantiofacial inversion of the terminally unsaturated polymer chain occurs by a non-dissociative process. The implications of these results on the mechanism of olefin polymerization with these catalysts is discussed.

I. Studies on bacteriophage DNA's and minicircular DNA's in M. lysodeikticus and E. coli 15. II. Flow dichroism of DNA solutions

Part I

Chapter 1.....A physicochemical study of the DNA molecules from the three bacteriophages, N1, N5, and N6, which infect the bacterium, M. lysodeikticus, has been made. The molecular weights, as measured by both electron microscopy and sedimentation velocity, are 23 x 10⁶ for N5 DNA and 31 x 10⁶ for N1 and N6 DNA's. All three DNA's are capable of thermally reversible cyclization. N1 and N6 DNA's have identical or very similar base sequences as judged by membrane filter hybridization and by electron microscope heteroduplex studies. They have identical or similar cohesive ends. These results are in accord with the close biological relation between N1 and N6 phages. N5 DNA is not closely related to N1 or N6 DNA. The denaturation T_m of all three DNA's is the same and corresponds to a (GC) content of 70%. However, the buoyant densities in CsCl of Nl and N6 DNA's are lower than expected, corresponding to predicted GC contents of 64 and 67%. The buoyant densities in Cs₂SO₄ are also somewhat anomalous. The buoyant density anomalies are probably due to the presence of odd bases. However, direct base composition analysis of N1 DNA by anion exchange chromatography confirms a GC content of 70%, and, in the elution system used, no peaks due to odd bases are present.

Chapter 2.....A covalently closed circular DNA form has been observed as an intracellular form during both productive and abortive infection processes in M. lysodeikticus. This species has been isolated by the method of CsC1-ethidium bromide centrifugation and examined with an electron microscope.

Chapter 3.....A minute circular DNA has been discovered as a homogeneous population in M. lysodeikticus. Its length and molecular weight as determined by electron microscopy are 0.445 μ and 0.88 x 10⁶ daltons respectively. There is about one minicircle per bacterium.

Chapter 4.....Several strains of E. coli 15 harbor a prophage. Viral growth can be induced by exposing the host to mitomycin C or to uv irradiation. The coliphage 15 particles from E. coli 15 and E, coli 15 T^- appear as normal phage with head and tail structure; the particles from E. coli 15 TAU are tailless. The complete particles exert a colicinogenic activity on E.coli 15 and 15 T^-, the tailless particles do not. No host for a productive viral infection has been found and the phage may be defective. The properties of the DNA of the virus have been studied, mainly by electron microscopy. After induction but before lysis, a closed circular DNA with a contour length of about 11.9 μ is found in the bacterium; the mature phage DNA is a linear duplex and 7.5% longer than the intracellular circular form. This suggests the hypothesis that the mature phage DNA is terminally repetitious and circularly permuted. The hypothesis was confirmed by observing that denaturation and renaturation of the mature phage DNA produce circular duplexes with two single-stranded branches corresponding to the terminal repetition. The contour length of the mature phage DNA was measured relative to φX RFII DNA and λ DNA; the calculated molecular weight is 27 x 10⁶. The length of the single-stranded terminal repetition was compared to the length of φX 174 DNA under conditions where single-stranded DNA is seen in an extended form in electron micrographs. The length of the terminal repetition is found to be 7.4% of the length of the nonrepetitious part of the coliphage 15 DNA. The number of base pairs in the terminal repetition is variable in different molecules, with a fractional standard deviation of 0.18 of the average number in the terminal repetition. A new phenomenon termed "branch migration" has been discovered in renatured circular molecules; it results in forked branches, with two emerging single strands, at the position of the terminal repetition. The distribution of branch separations between the two terminal repetitions in the population of renatured circular molecules was studied. The observed distribution suggests that there is an excluded volume effect in the renaturation of a population of circularly permuted molecules such that strands with close beginning points preferentially renature with each other. This selective renaturation and the phenomenon of branch migration both affect the distribution of branch separations; the observed distribution does not contradict the hypothesis of a random distribution of beginning points around the chromosome.

Chapter 5....Some physicochemical studies on the minicircular DNA species in E. coli 15 (0.670 μ, 1.47 x 10⁶ daltons) have been made. Electron microscopic observations showed multimeric forms of the minicircle which amount to 5% of total DNA species and also showed presumably replicating forms of the minicircle. A renaturation kinetic study showed that the minicircle is a unique DNA species in its size and base sequence. A study on the minicircle replication has been made under condition in which host DNA synthesis is synchronized. Despite experimental uncertainties involved, it seems that the minicircle replication is random and the number of the minicircles increases continuously throughout a generation of the host, regardless of host DNA synchronization.

Part II

The flow dichroism of dilute DNA solutions (A₂₆₀≈0.1) has been studied in a Couette-type apparatus with the outer cylinder rotating and with the light path parallel to the cylinder axis. Shear gradients in the range of 5-160 sec.^-1 were studied. The DNA samples were whole, "half," and "quarter" molecules of T4 bacteriophage DNA, and linear and circular λb₂b₅c DNA. For the linear molecules, the fractional flow dichroism is a linear function of molecular weight. The dichroism for linear A DNA is about 1.8 that of the circular molecule. For a given DNA, the dichroism is an approximately linear function of shear gradient, but with a slight upward curvature at low values of G, and some trend toward saturation at larger values of G. The fractional dichroism increases as the supporting electrolyte concentration decreases.

Regional variations in upper mantle structure beneath North America

Several types of seismological data, including surface wave group and phase velocities, travel times from large explosions, and teleseismic travel time anomalies, have indicated that there are significant regional variations in the upper few hundred kilometers of the mantle beneath continental areas. Body wave travel times and amplitudes from large chemical and nuclear explosions are used in this study to delineate the details of these variations beneath North America.

As a preliminary step in this study, theoretical P wave travel times, apparent velocities, and amplitudes have been calculated for a number of proposed upper mantle models, those of Gutenberg, Jeffreys, Lehman, and Lukk and Nersesov. These quantities have been calculated for both P and S waves for model CIT11GB, which is derived from surface wave dispersion data. First arrival times for all the models except that of Lukk and Nersesov are in close agreement, but the travel time curves for later arrivals are both qualitatively and quantitatively very different. For model CIT11GB, there are two large, overlapping regions of triplication of the travel time curve, produced by regions of rapid velocity increase near depths of 400 and 600 km. Throughout the distance range from 10 to 40 degrees, the later arrivals produced by these discontinuities have larger amplitudes than the first arrivals. The amplitudes of body waves, in fact, are extremely sensitive to small variations in the velocity structure, and provide a powerful tool for studying structural details.

Most of eastern North America, including the Canadian Shield has a Pn velocity of about 8.1 km/sec, with a nearly abrupt increase in compressional velocity by ~ 0.3 km/sec near at a depth varying regionally between 60 and 90 km. Variations in the structure of this part of the mantle are significant even within the Canadian Shield. The low-velocity zone is a minor feature in eastern North America and is subject to pronounced regional variations. It is 30 to 50 km thick, and occurs somewhere in the depth range from 80 to 160 km. The velocity decrease is less than 0.2 km/sec.

Consideration of the absolute amplitudes indicates that the attenuation due to anelasticity is negligible for 2 hz waves in the upper 200 km along the southeastern and southwestern margins of the Canadian Shield. For compressional waves the average Q for this region is > 3000. The amplitudes also indicate that the velocity gradient is at least 2 x 10^-3 both above and below the low-velocity zone, implying that the temperature gradient is < 4.8°C/km if the regions are chemically homogeneous.

In western North America, the low-velocity zone is a pronounced feature, extending to the base of the crust and having minimum velocities of 7.7 to 7.8 km/sec. Beneath the Colorado Plateau and Southern Rocky Mountains provinces, there is a rapid velocity increase of about 0.3 km/sec, similar to that observed in eastern North America, but near a depth of 100 km.

Complicated travel time curves observed on profiles with stations in both eastern and western North America can be explained in detail by a model taking into account the lateral variations in the structure of the low-velocity zone. These variations involve primarily the velocity within the zone and the depth to the top of the zone; the depth to the bottom is, for both regions, between 140 and 160 km.

The depth to the transition zone near 400 km also varies regionally, by about 30-40 km. These differences imply variations of 250 °C in the temperature or 6 % in the iron content of the mantle, if the phase transformation of olivine to the spinel structure is assumed responsible. The structural variations at this depth are not correlated with those at shallower depths, and follow no obvious simple pattern.

The computer programs used in this study are described in the Appendices. The program TTINV (Appendix IV) fits spherically symmetric earth models to observed travel time data. The method, described in Appendix III, resembles conventional least-square fitting, using partial derivatives of the travel time with respect to the model parameters to perturb an initial model. The usual ill-conditioned nature of least-squares techniques is avoided by a technique which minimizes both the travel time residuals and the model perturbations.

Spherically symmetric earth models, however, have been found inadequate to explain most of the observed travel times in this study. TVT4, a computer program that performs ray theory calculations for a laterally inhomogeneous earth model, is described in Appendix II. Appendix I gives a derivation of seismic ray theory for an arbitrarily inhomogeneous earth model.

Studies on T-even bacteriophage DNA

Part I. The regions of sequence homology and non-homology between the DNA molecules of T2, T4, and T6 have been mapped by the electron microscopic heteroduplex method. The heteroduplex maps have been oriented with respect to the T4 genetic map. They show characteristic, reproducible patterns of substitution and deletion loops. All heteroduplex molecules show more than 85% homology. Some of the loop patterns in T2/T4 heteroduplexes are similar to those in T4/T6.

We find that the rII, the lysozyme and ac genes, the D region, and gene 52 are homologous in T2, T4, and T6. Genes 43 and 47 are probably homologous between T2 and T4. The region of greatest homology is that bearing the late genes. The host range region, which comprises a part of gene 37 and all of gene 38, is heterologous in T2, T4, and T6. The remainder of gene 37 is partially homologous in the T2/T4 heteroduplex (Beckendorf, Kim and Lielausis, 1972) but it is heterologous in T4/T6 and in T2/T6. Some of the tRNA genes are homologous and some are not. The internal protein genes in general seem to be non-homologous.

The molecular lengths of the T-even DNAs are the same within the limit of experimental error; their calculated molecular weights are correspondingly different due to unequal glucosylation. The size of the T2 genome is smaller than that of T4 or T6, but the terminally repetitious region in T2 is larger. There is a length distribution of the terminal repetition for any one phage DNA, indicating a variability in length of the DNA molecules packaged within the phage.

Part II. E. coli cells infected with phage strains carrying extensive deletions encompassing the gene for the phage ser-tRNA are missing the phage tRNAs normally present in wild type infected cells. By DNA-RNA hybridization we have demonstrated that the DNA complementary to the missing tRNAs is also absent in such deletion mutants. Thus the genes for these tRNAs must be clustered in the same region of the genome as the ser-tRNA gene. Physical mapping of several deletions of the ser-tRNA and lysozyme genes, by examination of heteroduplex DNA in the electron microscope, has enabled us to locate the cluster, to define its maximum size, and to order a few of the tRNA genes within it. That such deletions can be isolated indicates that the phage-specific tRNAs from this cluster are dispensable.

Part III. Genes 37 and 38 between closely related phages T2 and T4 have been compared by genetic, biochemical, and hetero-duplex studies. Homologous, partially homologous and non-homologous regions of the gene 37 have been mapped. The host range determinant which interacts with the gene 38 product is identified.

Part IV. A population of double-stranded ØX-RF DNA molecules carrying a deletion of about 9% of the wild-type DNA has been discovered in a sample cultivated under conditions where the phage lysozyme gene is nonessential. The structures of deleted monomers, dimers, and trimers have been studied by the electron microscope heteroduplex method. The dimers and trimers are shown to be head-to-tail repeats of the deleted monomers. Some interesting examples of the dynamical phenomenon of branch migration in vitro have been observed in heteroduplexes of deleted dimer and trimer strands with undeleted wild-type monomer viral strands.