DNA computing using single-molecule hybridization detection

DNA computing aims at using nucleic acids for computing. Since micromolar DNA solutions can act as billions of parallel nanoprocessors, DNA computers can in theory solve optimization problems that require vast search spaces. However, the actual parallelism currently being achieved is at least a hundred million-fold lower than the number of DNA molecules used. This is due to the quantity of DNA molecules of one species that is required to produce a detectable output to the computations. In order to miniaturize the computation and considerably reduce the amount of DNA needed, we have combined DNA computing with single-molecule detection. Reliable hybridization detection was achieved at the level of single DNA molecules with fluorescence cross-correlation spectroscopy. To illustrate the use of this approach, we implemented a DNA-based computation and solved a 4-variable 4-clause instance of the computationally hard Satisfiability (SAT) problem.     

Extracting kinetics from single-molecule force spectroscopy: nanopore unzipping of DNA hairpins

Single-molecule force experiments provide powerful new tools to explore biomolecular interactions. Here, we describe a systematic procedure for extracting kinetic information from force-spectroscopy experiments, and apply it to nanopore unzipping of individual DNA hairpins. Two types of measurements are considered: unzipping at constant voltage, and unzipping at constant voltage-ramp speeds. We perform a global maximum-likelihood analysis of the experimental data at low-to-intermediate ramp speeds. To validate the theoretical models, we compare their predictions with two independent sets of data, collected at high ramp speeds and at constant voltage, by using a quantitative relation between the two types of measurements. Microscopic approaches based on Kramers theory of diffusive barrier crossing allow us to estimate not only intrinsic rates and transition state locations, as in the widely used phenomenological approach based on Bell's formula, but also free energies of activation. The problem of extracting unique and accurate kinetic parameters of a molecular transition is discussed in light of the apparent success of the microscopic theories in reproducing the experimental data.     

Measuring thermodynamic details of DNA hybridization using fluorescence

Modern real-time PCR systems make it easy to monitor fluorescence while temperature is varied for hundreds of samples in parallel, permitting high-throughput studies. We employed such system to investigate melting transitions of ordered nucleic acid structures into disordered random coils. Fluorescent dye and quencher were attached to oligonucleotides in such a way that changes of fluorescence intensity with temperature indicated progression of denaturation. When fluorescence melting data were compared with traditional ultraviolet optical experiments, commonly used dye/quencher combinations, like fluorescein and tetramethylrhodamine, showed substantial discrepancies. We have therefore screened 22 commercially available fluorophores and quenchers for their ability to reliably report annealing and melting transitions. Dependence of fluorescence on temperature and pH was also investigated. The optimal performance was observed using Texas Red or ROX dyes with Iowa Black RQ or Black Hole quenchers. These labels did not alter two-state nature of duplex melting process and provided accurate melting temperatures, free energies, enthalpies, and entropies. We also suggest a new strategy for determination of DNA duplex thermodynamics where concentration of a dye-labeled strand is kept constant and its complementary strand modified with a quencher is added at increasing excess. These methodological improvements will help build predictive models of nucleic acid hybridization.     

The electromechanics of DNA in a synthetic nanopore

We have explored the electromechanical properties of DNA on a nanometer-length scale using an electric field to force single molecules through synthetic nanopores in ultrathin silicon nitride membranes. At low electric fields, E < 200 mV/10 nm, we observed that single-stranded DNA can permeate pores with a diameter >/=1.0 nm, whereas double-stranded DNA only permeates pores with a diameter >/=3 nm. For pores <3.0 nm diameter, we find a threshold for permeation of double-stranded DNA that depends on the electric field and pH. For a 2 nm diameter pore, the electric field threshold is approximately 3.1 V/10 nm at pH = 8.5; the threshold decreases as pH becomes more acidic or the diameter increases. Molecular dynamics indicates that the field threshold originates from a stretching transition in DNA that occurs under the force gradient in a nanopore. Lowering pH destabilizes the double helix, facilitating DNA translocation at lower fields.     

Adaptive control of hybridization noise in DNA sequencing-by-hybridization

We consider the problem of sequence reconstruction in sequencing-by-hybridization in the presence of spectrum errors. As suggested by intuition, and reported in the literature, false-negatives (i.e., missing spectrum probes) are by far the leading cause of reconstruction failures. In a recent paper we have described an algorithm, called "threshold-theta", designed to recover from false negatives. This algorithm is based on overcompensating for missing extensions by allowing larger reconstruction subtrees. We demonstrated, both analytically and with simulations, the increasing effectiveness of the approach as the parameter theta grows, but also pointed out that for larger error rates the size of the extension trees translates into an unacceptable computational burden. To obviate this shortcoming, in this paper we propose an adaptive approach which is both effective and efficient. Effective, because for a fixed value of theta it performs as well as its single-threshold counterpart, efficient because it exhibits substantial speed-ups over it. The idea is that, for moderate error rates a small fraction of the target sequence can be involved in error recovery; thus, expectedly the remainder of the sequence is reconstructible by the standard noiseless algorithm, with the provision to switch to operation with increasingly higher thresholds after detecting failure. This policy generates interesting and complex interplays between fooling probes and false negatives. These phenomena are carefully analyzed for random sequences and the results are found to be in excellent agreement with the simulations. In addition, the experimental algorithmic speed-ups of the multithreshold approach are explained in terms of the interaction amongst the different threshold regimes.     

Dynamics of DNA molecules in a membrane channel probed by active control techniques

The dynamics of single-stranded DNA in an alpha-Hemolysin protein pore was studied at the single-molecule level. The escape time for DNA molecules initially drawn into the pore was measured in the absence of an externally applied electric field. These measurements revealed two well-separated timescales, one of which is surprisingly long (on the order of milliseconds). We characterized the long timescale as being associated with the binding and unbinding of DNA from the pore. We have also found that a transmembrane potential as small as 20 mV strongly biased the escape of DNA from the pore. These experiments have been made possible due to the development of a feedback control system, allowing the rapid modulation of the applied force on individual DNA molecules while inside the pore.     

DNA base-calling from a nanopore using a Viterbi algorithm

Nanopore-based DNA sequencing is the most promising third-generation sequencing method. It has superior read length, speed, and sample requirements compared with state-of-the-art second-generation methods. However, base-calling still presents substantial difficulty because the resolution of the technique is limited compared with the measured signal/noise ratio. Here we demonstrate a method to decode 3-bp-resolution nanopore electrical measurements into a DNA sequence using a Hidden Markov model. This method shows tremendous potential for accuracy (~98%), even with a poor signal/noise ratio.     

Translocation of a single-stranded DNA through a conformationally changing nanopore

We investigate the translocation of a single-stranded DNA through a pore which fluctuates between two conformations, using coupled master equations. The probability density function of the first passage times of the translocation process is calculated, displaying a triple-, double-, or monopeaked behavior, depending on the interconversion rates between the conformations, the applied electric field, and the initial conditions. The cumulative probability function of the first passage times, in a field-free environment, is shown to have two regimes, characterized by fast and slow timescales. An analytical expression for the mean first passage time of the translocation process is derived, and provides, in addition to the interconversion rates, an extensive characterization of the translocation process. Relationships to experimental observations are discussed.     

Probing DNA base pairing energy profiles using a nanopore

We experimentally show that the voltage driven unzipping of long DNA duplexes by an α-hemolysin pore is sensitive to the shape of the base pairing energy landscape. Two sequences of equal global stability were investigated. The sequence with an homogeneous base pairing profile translocates faster than the one with alternative weak and strong regions. We could qualitatively account for theses observations by theoretically describing the voltage driven translocation as a biased random walk of the unzipping fork in the sequence dependent energy landscape. Electronic supplementary material  The online version of this article (doi:) contains supplementary material, which is available to authorized users.     

Real-time detection of cruciform extrusion by single-molecule DNA nanomanipulation

During cruciform extrusion, a DNA inverted repeat unwinds and forms a four-way junction in which two of the branches consist of hairpin structures obtained by self-pairing of the inverted repeats. Here, we use single-molecule DNA nanomanipulation to monitor in real-time cruciform extrusion and rewinding. This allows us to determine the size of the cruciform to nearly base pair accuracy and its kinetics with second-scale time resolution. We present data obtained with two different inverted repeats, one perfect and one imperfect, and extend single-molecule force spectroscopy to measure the torque dependence of cruciform extrusion and rewinding kinetics. Using mutational analysis and a simple two-state model, we find that in the transition state intermediate only the B-DNA located between the inverted repeats (and corresponding to the unpaired apical loop) is unwound, implying that initial stabilization of the four-way (or Holliday) junction is rate-limiting. We thus find that cruciform extrusion is kinetically regulated by features of the hairpin loop, while rewinding is kinetically regulated by features of the stem. These results provide mechanistic insight into cruciform extrusion and help understand the structural features that determine the relative stability of the cruciform and B-form states.     

Real-time detection of single-molecule DNA compaction by condensin I

BACKGROUND: Condensin is thought to contribute to large-scale DNA compaction during mitotic chromosome assembly. It remains unknown, however, how the complex reconfigures DNA structure at a mechanistic level. RESULTS: We have performed single-molecule DNA nanomanipulation experiments to directly measure in real-time DNA compaction by the Xenopus laevis condensin I complex. Condensin can bind to the nanomanipulated DNA in the absence of ATP, but it compacts the DNA only in the presence of hydrolyzable ATP. Linear compaction is evidenced by a reduction in the end-to-end extension of nanomanipulated DNA. The reaction results in total compaction of the DNA (i.e., zero end-to-end extension). Discrete and reversible DNA compaction events are observed in the presence of competitor DNA when the DNA is subjected to weak stretching forces (F = 0.4 picoNewton [pN]). The distribution of step sizes is broad and displays a peak at approximately 60 nm ( approximately 180 bp) as well as a long tail. This distribution is essentially unaffected by the topological state of the DNA substrate. Increasing the force to F = 10 pN drives the system toward step-wise reversal of compaction. The distribution of step sizes observed upon disruption of condensin-DNA interactions displays a sharp peak at approximately 30 nm ( approximately 90 bp) as well as a long tail stretching out to hundreds of nanometers. CONCLUSIONS: The DNA nanomanipulation assay allows us to demonstrate for the first time that condensin physically compacts DNA in an ATP-hydrolysis-dependent manner. Our results suggest that the condensin complex may induce DNA compaction by dynamically and reversibly introducing loops along the DNA.     

Winding single-molecule double-stranded DNA on a nanometer-sized reel

A molecular system of a nanometer-sized reel was developed from F₁–ATPase, a rotary motor protein. By combination with magnetic tweezers and optical tweezers, single-molecule double-stranded DNA (dsDNA) was wound around the molecular reel. The bending stiffness of dsDNA was determined from the winding tension (0.9–6.0 pN) and the diameter of the wound loop (21.4–8.5 nm). Our results were in good agreement with the conventional worm-like chain model and a persistence length of 54 ± 9 nm was estimated. This molecular reel system offers a new platform for single-molecule study of micromechanics of sharply bent DNA molecules and is expected to be applicable to the elucidation of the molecular mechanism of DNA-associating proteins on sharply bent DNA strands.     

Recent developments in single-molecule DNA mechanics

Over the past two decades, measurements on individual stretched and twisted DNA molecules have helped define the basic elastic properties of the double helix and enabled real-time functional assays of DNA-associated molecular machines. Recently, new magnetic tweezers approaches for simultaneously measuring freely fluctuating twist and extension have begun to shed light on the structural dynamics of large nucleoprotein complexes. Related technical advances have facilitated direct measurements of DNA torque, contributing to a better understanding of abrupt structural transitions in mechanically stressed DNA. The new measurements have also been exploited in studies that hint at a developing synergistic relationship between single-molecule manipulation and structural DNA nanotechnology.     

Processing and quality control of DNA array hybridization data

MOTIVATION: The technology of hybridization to DNA arrays is used to obtain the expression levels of many different genes simultaneously. It enables searching for genes that are expressed specifically under certain conditions. However, the technology produces large amounts of data demanding computational methods for their analysis. It is necessary to find ways to compare data from different experiments and to consider the quality and reproducibility of the data. RESULTS: Data analyzed in this paper have been generated by hybridization of radioactively labeled targets to DNA arrays spotted on nylon membranes. We introduce methods to compare the intensity values of several hybridization experiments. This is essential to find differentially expressed genes or to do pattern analysis. We also discuss possibilities for quality control of the acquired data. AVAILABILITY: http://www.dkfz.de/tbi CONTACT: M.Vingron@dkfz-heidelberg.de     

Reconstruction of DNA sequencing by hybridization

MOTIVATION: It is widely recognized that the hybridization process is prone to errors and that the future of DNA sequencing by hybridization is predicated on the ability to successfully cope with such errors. However, the occurrence of hybridization errors results in the computational difficulty of the reconstruction of DNA sequencing by hybridization. The reconstruction problem of DNA sequencing by hybridization with errors is a strongly NP-hard problem. So far the problem has not been solved well. RESULTS: In this paper, a new approach is presented to solve the reconstruction problem of DNA sequencing by hybridization, which realizes the computational part of the SBH experiment. The proposed algorithm accepts both the negative and positive errors. The computational experiments show that the algorithm behaves satisfactorily, especially for the case with k-tuple repetitions and positive errors.     

Quantifying force-dependent and zero-force DNA intercalation by single-molecule stretching

We used single DNA molecule stretching to investigate DNA intercalation by ethidium and three ruthenium complexes. By measuring ligand-induced DNA elongation at different ligand concentrations, we determined the binding constant and site size as a function of force. Both quantities depend strongly on force and, in the limit of zero force, converge to the known bulk solution values, when available. This approach allowed us to distinguish the intercalative mode of ligand binding from other binding modes and allowed characterization of intercalation with binding constants ranging over almost six orders of magnitude, including ligands that do not intercalate under experimentally accessible solution conditions. As ligand concentration increased, the DNA stretching curves saturated at the maximum amount of ligand intercalation. The results showed that the applied force partially relieves normal intercalation constraints. We also characterized the flexibility of intercalator-saturated dsDNA for the first time.     

DnaB helicase dynamics in bacterial DNA replication resolved by single-molecule studies

In Escherichia coli, the DnaB helicase forms the basis for the assembly of the DNA replication complex. The stability of DnaB at the replication fork is likely important for successful replication initiation and progression. Single-molecule experiments have significantly changed the classical model of highly stable replication machines by showing that components exchange with free molecules from the environment. However, due to technical limitations, accurate assessments of DnaB stability in the context of replication are lacking. Using in vitro fluorescence single-molecule imaging, we visualise DnaB loaded on forked DNA templates. That these helicases are highly stable at replication forks, indicated by their observed dwell time of ∼30 min. Addition of the remaining replication factors results in a single DnaB helicase integrated as part of an active replisome. In contrast to the dynamic behaviour of other replisome components, DnaB is maintained within the replisome for the entirety of the replication process. Interestingly, we observe a transient interaction of additional helicases with the replication fork. This interaction is dependent on the τ subunit of the clamp-loader complex. Collectively, our single-molecule observations solidify the role of the DnaB helicase as the stable anchor of the replisome, but also reveal its capacity for dynamic interactions.     

Real-time direct observation of single-molecule DNA hydrolysis by exonuclease III

Single-molecule DNA digestion by exonuclease III, which has 3' to 5' exonuclease activity, was analyzed using a micro-channel with two-layer laminar flow. First, a DNA-bead complex was optically trapped in one layer in the absence of exonuclease III permitted the DNA to be stretched by the laminar flow. The exonuclease III reaction was initiated by moving the trapped DNA-bead complex to another layer of flow, which contained exonuclease III. As the reaction proceeded, the fluorescently-stained DNA was observed to shorten. The process was photographed; examination of the photographs showed that the DNA molecule shortened in a linear fashion with respect to the reaction time. The digestion rate obtained from the single-molecule experiment was compared to that measured from a bulk experiment and was found to be ca. 28 times higher than the bulk digestion rate.     

Folding transition into a loosely collapsed state in plasmid DNA as revealed by single-molecule observation

The conformational transition of a plasmid DNA, pGEG.GL3 (12.5 kbp, circular), induced by spermine(4+) was studied through the observation of individual DNA by fluorescence microscopy. We deduced the change in the hydrodynamic radius R(H) from an analysis of the Brownian motion of single DNA molecules. R(H) decreases in a continuous manner with an increase in spermine(4+), in contrast to the large discrete on/off change for long linear DNA. Just after the transition to the collapsed state, a small number of DNA molecules tend to form an assembly, which disperses in the bulk solution without precipitation.     

Nucleotide discrimination with DNA immobilized in the MspA nanopore

Nanopore sequencing has the potential to become a fast and low-cost DNA sequencing platform. An ionic current passing through a small pore would directly map the sequence of single stranded DNA (ssDNA) driven through the constriction. The pore protein, MspA, derived from Mycobacterium smegmatis, has a short and narrow channel constriction ideally suited for nanopore sequencing. To study MspA's ability to resolve nucleotides, we held ssDNA within the pore using a biotin-NeutrAvidin complex. We show that homopolymers of adenine, cytosine, thymine, and guanine in MspA exhibit much larger current differences than in α-hemolysin. Additionally, methylated cytosine is distinguishable from unmethylated cytosine. We establish that single nucleotide substitutions within homopolymer ssDNA can be detected when held in MspA's constriction. Using genomic single nucleotide polymorphisms, we demonstrate that single nucleotides within random DNA can be identified. Our results indicate that MspA has high signal-to-noise ratio and the single nucleotide sensitivity desired for nanopore sequencing devices.