ALBERT

Notes: Abstract. This paper is concerned with the development of techniques for massively parallel computation at the molecular scale, which we refer to as molecular parallelism. While this may at first appear to be purely science fiction, Adleman [Ad1] has already employed molecular parallelism in the solution of the Hamiltonian path problem, and successfully tested his techniques in a lab experiment on DNA for a small graph. Lipton [L] showed that finding the satisfying inputs to a Boolean expression of size n can be done in O(n) lab steps using DNA of length O(n log n) base pairs. This recent work by Adleman and Lipton in molecular parallelism considered only the solution of NP search problems, and provided no way of quickly executing lengthy computations by purely molecular means; the number of lab steps depended linearly on the size of the simulated expression. See [Re3] for further recent work on molecular parallelism and see [Re4] for an extensive survey of molecular parallelism. Our goal is to execute lengthy computations quickly by the use of molecular parallelism. We wish to execute these biomolecular computations using short DNA strands by more or less conventional biotechnology engineering techniques within a small number of lab steps. This paper describes techniques for achieving this goal, in the context of well defined abstract models of biomolecular computation. Although our results are of theoretical consequence only, due to the large amount of molecular parallelism (i.e., large test tube volume) required , we believe that our theoretical models and results may be a basis for more practical later work, just as was done in the area of parallel computing. We propose two abstract models of biomolecular computation. The first, the Parallel Associative Memory (PAM) model, is a very high-level model which includes a Parallel Associative Matching (PA-Match) operation, that appears to improve the power of molecular parallelism beyond the operations previously considered by Lipton [L]. We give some simulations of conventional sequential and parallel computational models by our PAM model. Each of the simulations use strings of length O(s) over an alphabet of size O(s) (which correspond to DNA of length O(s log s) base pairs). Using O(s log s) PAM operations that are not PA-Match (or O(s) operations assuming a ligation operation) and t PA-Match operations, we can: 1. simulate a nondeterministic Turing Machine computation with space bound s and time bound 2 O(s) , with t = O(s) , 2. simulate a CREW PRAM with time bound D, with M memory cells, and processor bound P, where here s = O( log (PM)) and t = O(D+s), 3. find the satisfying inputs to a Boolean circuit constructible in s space with n inputs, unbounded fan-out, and depth D, where here t = O(D+s). We also propose a Recombinant DNA (RDNA) model which is a low-level model that allows operations that are abstractions of very well understood recombinant DNA operations and provides a representation, which we call the complex , for the relevant structural properties of DNA. The PA-Match operation for lengthy strings of length s cannot be feasibly implemented by recombinant DNA techniques directly by a single step of complementary pairing in DNA; nevertheless we show this Matching operation can be simulated in the RDNA model with O(s) slowdown by multiple steps of complementary pairing of substrings of length 2 (corresponding to logarithmic length DNA subsequences). Each of the other operations of the PAM model can be executed in our RDNA model, without slowdown. We further show that, with a further O(s)/ log (1/ε) slowdown, the simulations can be done correctly with probability 1/2 even if certain recombinant DNA operations (e.g., Separation) can error with a probability ε. We also observe efficient simulations can be done by PRAMs and thus Turing Machines of our molecular models.

Notes: Abstract. In this paper we show that if the input points to the geometric closest pair problem are given with limited precision (each coordinate is specified with O( log n) bits), then we can compute the closest pair in O(n log log n) time. We also apply our spatial decomposition technique to the k -nearest neighbor and n -body problems, achieving similar improvements. To make use of the limited precision of the input points, we use a reasonable machine model that allows ``bit shifting'' in constant time—we believe that this model is realistic, and provides an interesting way of beating the Ω(n log n) lower bound that exists for this problem using the more typical algebraic RAM model.

Notes: Abstract The correspondence of classical dynamical chaos and statistical properties of the energy spectrum has been investigated for the single-particle motion in strongly deformed nuclear potentials with axial symmetry. The properties of the classical and of the quantized system were analyzed for two potentials: the two-center well potential of finite depth and the two-center oscillator shell model. It has been found that in such mean fields the occurrence of fully developed random matrix statistics is a generic feature corresponding to a global instability of classical trajectories. But due to the absence of scaling invariance, for the general case with a mixed phase space a significant energy dependence of the chaotic phase-space volume has been obtained so that the over-all level-spacing distribution cannot be specified by the chaotic volume as a single parameter. The reason for the appearance of chaoticity turns out to be rather complex. Besides the expected important role of large deformations of high multipolarity, including the neck degree of freedom, the spin-orbit part of the nuclear interaction can also be responsible for the occurrence of dynamical chaos.

Notes: Abstract An extended level scheme of109Sn is presented showing high-spin states up to Ex≈ 8 MeV and spins up toJπ=(41/2+). Their decay to the 5/2+ ground state has been observed identifying a 12.8 keV 7/2+ → 5/2+ transition. A half-life of T1/2=7(1) ns has been measured for the 17/2+ state atE x =2114 keV. The experimental data are compared with the predictions of shell-model calculations.

Notes: Abstract Polarization and azimuthal dependencies of optical second-harmonic generation at the surface of cubic ionic crystals have been measured on polished surfaces of BaF2 (111) and (100), CaF2 (111) and NaCl (111), using a fundamental wavelength of 532 nm. The results are interpreted in terms of available theory, which shows that for transparent cubic media only the dipolar surface contribution depends on the crystal orientation. For BaF2 (111) and NaCl (111) the crystallineC 3vgeometry could be identified but not for CaF2 (111). Although the nature of the electronic surface structure giving rise to a dipolar polarizability remains undetermined, the experimental result suggests that it may be due to impurity or defect states in the band gap at the surface.

Notes: Abstract The energy of the acoustic pulse generated by laser-surface interactions and measured by probe beam deflection was used to investigate laser surface damage thresholds of fluoride crystals with optical quality. It was found that damage thresholds decrease with increasing density of surface states. The defect density also controls the energy absorption mechanism: for surfaces with few defects, like polished MgF2 and CaF2, avalanche breakdown occurs at above 1 GW/cm2, whereas for materials with lower damage thresholds, such as LiF, BaF2, and roughened or incubated surfaces of CaF2, multiphoton absorption across the band gap is observed.

Notes: Abstract. After explosive ablation from sapphire crystals by linearly polarised laser pulses, regular structures are observed on the bottom of the ablation pit. These structures do not comply with conventional ripple patterns. Instead, they more nearly resemble wickerwork, aligned perpendicular to the laser beam polarisation. A similar morphology is obtained by arc discharge erosion at AgCdO electrodes, suggesting that an explosive laser ablation may be characterised by high electric field effects and self organisation in the ablation craters.

Notes: Abstract Low-lying states of theN=50 nucleus87Rb have been investigated in the (α, α') reaction measuringγγ- and delayedγ-rf-coincidences. A half-life ofT 1/2=6(1) ns was obtained for the level at 1578.1 keV. This experimental result confirms the 9/2+ assignment and the proton 1g9/2 single-particle character of this state. Experimental M2 transition strengths in85,87Rb are compared with predictions of the shell model and the particle-core coupling model.