Handling long targets and errors in sequencing by hybridization.

Sequencing by hybridization (SBH) is a DNA sequencing technique, in which the sequence is reconstructed using its k-mer content. This content, which is called the spectrum of the sequence, is obtained by hybridization to a universal DNA array. Standard universal arrays contain all k-mers for some fixed k, typically 8 to 10. Currently, in spite of its promise and elegance, SBH is not competitive with standard gel-based sequencing methods. This is due to two main reasons: lack of tools to handle realistic levels of hybridization errors and an inherent limitation on the length of uniquely reconstructible sequence by standard universal arrays. In this paper, we deal with both problems. We introduce a simple polynomial reconstruction algorithm which can be applied to spectra from standard arrays and has provable performance in the presence of both false negative and false positive errors. We also propose a novel design of chips containing universal bases that differs from the one proposed by Preparata et al. (1999). We give a simple algorithm that uses spectra from such chips to reconstruct with high probability random sequences of length lower only by a squared log factor compared to the information theoretic bound. Our algorithm is very robust to errors and has a provable performance even if there are both false negative and false positive errors. Simulations indicate that its sensitivity to errors is also very small in practice.     

Dealing with errors in interactive sequencing by hybridization.

MOTIVATION: A realistic approach to sequencing by hybridization must deal with realistic sequencing errors. The results of such a method can surely be applied to similar sequencing tasks. RESULTS: We provide the first algorithms for interactive sequencing by hybridization which are robust in the presence of hybridization errors. Under a strong error model allowing both positive and negative hybridization errors without repeated queries, we demonstrate accurate and efficient reconstruction with error rates up to 7%. Under the weaker traditional error model of Shamir and Tsur (Proceedings of the Fifth International Conference on Computational Molecular Biology (RECOMB-01), pp 269-277, 2000), we obtain accurate reconstructions with up to 20% false negative hybridization errors. Finally, we establish theoretical bounds on the performance of the sequential probing algorithm of Skiena and Sundaram (J. Comput. Biol., 2, 333-353, 1995) under the strong error model. AVAILABILTY: Freely available upon request. CONTACT: skiena@cs.sunysb.edu.     

An algorithm for the DNA sequence generation from k-tuple word contents of the minimal number of random fragments

An algorithm is described for generation of the long sequence written in a four letter alphabet from the constituent k-tuple words in the minimal number of separate, randomly defined fragments of the starting sequence. It is primarily intended for use in sequencing by hybridization (SBH) process- a potential method for sequencing human genome DNA (Drmanac et al., Genomics 4, pp. 114-128, 1989). The algorithm is based on the formerly defined rules and informative entities of the linear sequence. The algorithm requires neither knowledge on the number of appearances of a given k-tuple in sequence fragments, nor the information on which k-tuple words are on the ends of a fragment. It operates with the mixed content of k-tuples of the various lengths. The concept of the algorithm enables operations with the k-tuple sets containing false positive and false negative k-tuples. The content of the false k-tuples primarily affects the completeness of the generated sequence, and its correctness in the specific cases only. The algorithm can be used for the optimization of SBH parameters in the simulation experiments, as well as for the sequence generation in the real SBH experiments on the genomic DNA.     

An Algorithm for the DNA Sequence Generation from k-Tuple Word Contents of the Minimal Number of Random Fragments

Abstract

An algorithm is described for generation of the long sequence written in a four letter alphabet from the constituent k-tuple words in the minimal number of separate, randomly defined fragments of the starting sequence. It is primarily intended for use in sequencing by hybridization (SBH) process- a potential method for sequencing human genome DNA (Drmanac et al., Genomics 4, pp. 114–128, 1989). The algorithm is based on the formerly defined rules and informative entities of the linear sequence.

The algorithm requires neither knowledge on the number of appearances of a given k-tuple in sequence fragments, nor the information on which k-tuple words are on the ends of a fragment. It operates with the mixed content of k-tuples of the various lengths. The concept of the algorithm enables operations with the k-tuple sets containing false positive and false negative k-tuples. The content of the false k-tuples primarily affects the completeness of the generated sequence, and its correctness in the specific cases only. The algorithm can be used for the optimization of SBH parameters in the simulation experiments, as well as for the sequence generation in the real SBH experiments on the genomic DNA.     

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.     

A molecular beacon DNA microarray system for rapid detection of E. coli O157:H7 that eliminates the risk of a false negative signal

A DNA hybridization based optical detection platform for the detection of foodborne pathogens has been developed with virtually zero probability of the false negative signal. This portable, low-cost and real-time assaying detection platform utilizes the color changing molecular beacon as a probe for the optical detection of the target sequence. The computer-controlled detection platform exploits the target hybridization induced change of fluorescence color due to the F?rster (fluorescence) resonance energy transfer (FRET) between a pair of spectrally shifted fluorophores conjugated to the opposite ends of a beacon (oligonucleotide probe). Unlike the traditional fluorophore-quencher beacon design, the presence of two fluorescence molecules allows to actively visualize both hybridized and unhybridized states of the beacon. This eliminates false negative signal detection characteristic for the fluorophore-quencher beacon where bleaching of the fluorophore or washout of a beacon is indistinguishable from the absence of the target DNA sequence. In perspective, the two-color design allows also to quantify the concentration of the target DNA in a sample down to < =1 ng/microl. The new design is suitable for simultaneous reliable detection of hundreds of DNA target sequences in one test run using a series of beacons immobilized on a single substrate in a spatial format.     

Genome sequences from extinct relatives

Next-generation sequencing methods use massively parallel detection of short sequencing reactions, making them ideal for the analysis of ancient DNA. In this issue, Green et al. (2008) exploit this feature to infer the complete mitochondrial genome sequence of one Neanderthal and place bounds on its time of common ancestry with modern humans.     

Use of Subtractive Hybridization To Design Habitat-Based Oligonucleotide Probes for Investigation of Natural Bacterial Communities

We describe a rapid oligonucleotide probe design strategy based on subtractive hybridization which yields probes for 16S rRNA or rRNA genes of individual members of microbial communities that are specific within the context of those communities. This strategy circumvents the need to sequence many similar or identical clones of dominant members of a community. Radioactively labeled subfragments of a cloned 16S rRNA gene sequence for which a probe is required (target) were hybridized with biotinylated total 16S ribosomal DNA (rDNA) amplified from the microbial community, and the hybrids formed were subsequently discarded. The remaining enriched fragments were used to screen a library consisting of cloned subfragments of the target sequence by colony hybridization in order to identify the variable regions of the 16S rRNA gene with the required specificity. The sequencing of random clones in one 16S rDNA library demonstrated that only those clones with 100% sequence identity with the probe fragment were detected by it. Moreover, sequencing of other, randomly selected, probe-positive clones revealed 100% sequence identity with the probe. Probes developed in this way tended to correspond to more variable regions of the 16S rRNA if the target sequences were similar to the sequences of other clones in the library and to less variable regions if the target sequences were phylogenetically isolated within the clone library. Although the absolute specificity of the latter probes, as assessed by comparison with available database sequences, was lower than the absolute specificity of the probes from the more variable regions, they were specific within the context of the environmental samples from which they were derived.     

1-Tuple DNA sequencing: computer analysis

A new method of DNA reading was proposed at the end of 1988 by Lysov et al. According to the authors' claims it has certain advantages as compared to the Maxam-Gilbert and Sanger methods, which are revealed by automation and rapidity of DNA sequencing. Nevertheless its employment is hampered by a number of biological and mathematical problems. The present study proposes an algorithm that allows to overcome the computational difficulties occurring in the course of the method during reconstruction of the DNA sequence by its l-tuple composition. It is shown also that the biochemical problems connected with the loss of information about the l-tuple DNA composition during hybridization are not crucial and can be overcome by finding the maximal flow of minimal cost in the special graph.     

DNA sequencing with positive and negative errors.

The problem addressed in this paper is concerned with DNA sequencing by hybridization. An algorithm is proposed that solves a computational phase of this approach in the presence of both positive and negative errors resulting from the hybridization experiment. No a priori knowledge of the nature and source of these errors is required. An extensive set of computational experiments showed that the algorithm behaves surprisingly well if only positive errors appear. The general case, where positive and negative errors occur, can be also solved satisfactorily for an error rate up to 10%.     

Sequencing-by-hybridization at the information-theory bound: an optimal algorithm.

In a recent paper (Preparata et aL, 1999) we introduced a novel probing scheme for DNA sequencing by hybridization (SBH). The new gapped-probe scheme combines natural and universal bases in a well-defined periodic pattern. It has been shown (Preparata et al, 1999) that the performance of the gapped-probe scheme (in terms of the length of a sequence that can be uniquely reconstructed using a given size library of probes) is significantly better than the standard scheme based on oligomer probes. In this paper we present and analyze a new, more powerful, sequencing algorithm for the gapped-probe scheme. We prove that the new algorithm exploits the full potential of the SBH technology with high-confidence performance that comes within a small constant factor (about 2) of the information-theory bound. Moreover, this performance is achieved while maintaining running time linear in the target sequence length.     

HRP-HBVDNA探针在临检应用中的研究

本文介绍了一种简便的检测血清ＨＢＶＤＮＡ的方法。参照Ｒｅｎｚ等人的标记方法,构建了直接酶标ＨＲＰ ＨＢＶＤＮＡ探针。此探针经与固定在硝酸纤维素滤膜上的血清靶ＤＮＡ杂交后,可通过化学发光自显影检测技术观察结果。敏感度可检测０－１ｐｇ靶ＤＮＡ,相当于同位素探针的灵敏度。对６３份ＨＢｓＡｇＨＢｅＡｇ和Ａｎｔｉ ＨＢｃＥＬＩＳＡ阳性血清以及２４份ＨＢｓＡｇＡｎｔｉ ＨＢｃ阳性,ＨｂｅＡｇ阴性血清用ＨＲＰ ＨＢＶＤＮＡ探针进行检测,结果探针ＨＢＶＤＮＡ阳性率分别为１００％（６３）和５８％（１４）;对５０份ＨＢｓＡｇ,ＥＬＩＳＡ阴性和ＡＬＴ正常的血清,探针ＨＢＶＤＮＡ全部阴性。实验结果表明本方法具有很大的推广应用价值。     

DNA Sequencing by Hybridization to Oligonucleotide Matrix. Calculation of Continuous Stacking Hybridization Efficiency

Abstract

In this paper we consider the efficiency of additional rounds of “continuous stacking” hybridization in DNA sequence reconstruction by hybridization with oligonucleotide matrix (SHOM). After the initial hybridization of target DNA with the matrix of oligonucleotides of fixed length L some additional hybridizations should be carried out in the presence of fluorescently labeled oligonucleotides of another length l. These additional oligonucleotides can hybridize in tandem with matrix tuples (continuous stacking hybridization) thus forming an extended duplex with the target DNA strand. The additional data obtained allows resolutions of branching points arising in the reconstruction procedure. Multiple rounds of continuous stacking hybridization considerably increase the efficiency of the sequencing method, eventually approaching the power of (L+l)-matrix. We develop here an algorithm that allows us to minimize the number of additional hybridization steps, by assembling sets of l-tuples to be added together in each round of continuous stacking hybridization. For SHOM using a matrix of octanucleotides, continuous stacking hybridization with pen- tanucleotides increases the length of unambiguously sequenced DNA from 200 to several thousands of base pairs.     

Sequencing by hybridization by cooperating direct and reverse spectra.

DNA sequencing by hybridization, potentially a powerful alternative to standard wet lab techniques, has received renewed interest after a novel probing scheme has been recently proposed whose performance for the first time asymptotically meets the information theory bound. After settlement of the question of asymptotic performance, there remains the issue of algorithmic fine tunings aimed at improving the performance "constants," with substantial practical implications. In this paper, we show that a probing scheme based on the joint use of direct and reverse spectra (tandem spectra) for a given gapped probing pattern achieves a performance improvement per unit of microarray area of about 5/4 and does not appear to be susceptible to further improvement by increasing the number of cooperating spectra. In other words, tandem-spectrum reconstruction is the best known technique for sequencing by hybridization.     

Direct sequencing of PCR-amplified DNA

This article describes the direct sequencing of PCR-amplified DNA, a technique that bypasses the problem of replication errors sometimes associated with other PCR procedures. The direct sequencing procedure produces an “average sequence” of all the copies of the target. Any miscopied molecule usually represents only a small proportion of the total. The technique described here is based on the “traditional” ddNTP sequencing method of Sanger et al.     

Cadmium sulfide-modified GCE for direct signal-amplified sensing of DNA hybridization

A novel DNA hybridization sensor based on nanoparticle CdS modified glass carbon electrode (GCE) was constructed and characterized coupled with Cyclic Voltammogram (CV) and Differential Pulse Voltammogram (DPV) techniques. The mercapto group-linked probe DNA was covalently immobilized onto the CdS layer and exposed to oligonucleotide (ODN) target for hybridization. The structure of DNA sensor was characterized by X-ray diffraction (XRD), field-emission microscopy (FESEM) and X-ray photoelectron spectra (XPS). Sensitive electrical readout achieved by CV and DPV techniques shown that when the target DNA hybridized with probe CdS-ODN conjugates and the double helix formed on the modified electrode, a significant increased response was observed comparing with the bare electrodes. The selectivity of the sensor was tested using a series of matched and certain-point mismatched sequences with concentration grads ranging from 10(-6) microM to 10(1) microM. The signal was in good linear with the minus logarithm of target oligonucleotide concentration with detection limit <1 pM and the optimized target DNA concentration was 10(-6) microM for the signal amplification. Due to great surface properties, the additional negative charges and space resistance of as-prepared CdS nanoparticles, the sensor was able to robustly discriminate the DNA hybridization responses with good sensitivity and stability.     

A DNA target of 30 bp is sufficient for RNA-directed DNA methylation

In higher plants, RNA-DNA interactions can trigger de novo methylation of genomic sequences via a process that is termed RNA-directed DNA methylation (RdDM). In potato spindle tuber viroid (PSTVd)-infected tobacco plants, this process can potentially lead to methylation of all C residues at symmetrical and nonsymmetrical sites within chromosomal inserts that consist of multimers of the 359-bp-long PSTVd cDNA. Using PSTVd cDNA subfragments, we found that genomic targets with as few as 30 nt of sequence complementarity to the viroid RNA are detected and methylated. Genomic sequencing analyses of genome-integrated 30- and 60-bp-long PSTVd subfragments demonstrated that de novo cytosine methylation is not limited to the canonical CpG, CpNpG sites. Sixty-base-pair-long PSTVd cDNA constructs appeared to be densely methylated in nearly all tobacco leaf cells. With the 30-bp-long PSTVd-specific construct, the proportion of cells displaying dense transgene methylation was significantly reduced, suggesting that a minimal target size of about 30 bp is necessary for RdDM. The methylation patterns observed for two different 60-bp constructs further suggested that the sequence identity of the target may influence the methylation mechanism. Finally, a link between viroid pathogenicity and PSTVd RNA-directed methylation of host sequences is proposed.     

Optimal reconstruction of a sequence from its probes.

An important combinatorial problem, motivated by DNA sequencing in molecular biology, is the reconstruction of a sequence over a small finite alphabet from the collection of its probes (the sequence spectrum), obtained by sliding a fixed sampling pattern over the sequence. Such construction is required for Sequencing-by-Hybridization (SBH), a novel DNA sequencing technique based on an array (SBH chip) of short nucleotide sequences (probes). Once the sequence spectrum is biochemically obtained, a combinatorial method is used to reconstruct the DNA sequence from its spectrum. Since technology limits the number of probes on the SBH chip, a challenging combinatorial question is the design of a smallest set of probes that can sequence an arbitrary DNA string of a given length. We present in this work a novel probe design, crucially based on the use of universal bases [bases that bind to any nucleotide (Loakes and Brown, 1994)] that drastically improves the performance of the SBH process and asymptotically approaches the information-theoretic bound up to a constant factor. Furthermore, the sequencing algorithm we propose is substantially simpler than the Eulerian path method used in previous solutions of this problem.