首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Scalability of the surface-based DNA algorithm for 3-SAT   总被引:3,自引:0,他引:3  
Li D  Li X  Huang H  Li X 《Bio Systems》2006,85(2):95-98
Since Adleman first proposed DNA computing for the Hamiltonian path problem, several authors have reported DNA computing for 3-SAT. Previous research presented DNA computing on surfaces and demonstrated how to solve a four-variable four-clause instance of 3-SAT, and claimed that the surface-based approach was designed to scale up to larger problems. In this paper we establish an error model for the incomplete "mark" and imperfect "destroy" operations. By using the error model we argue that no matter how large the "mark" and "destroy" rates are we can always give satisfiable instances of 3-SAT such that no DNA strands remain on the surface at the end of the computation. By the surface-based approach the satisfiable instances of 3-SAT would be misdetermined to be unsatisfiable. Thus, the error leads to an incorrect result of the SAT computation. Furthermore, given the "mark" rate p and the "not-destroy" rate rho, we find that the approach can only solve at most N-variable instances of 3-SAT problems, where N=[(2+beta(2)+2+2 square root beta (2))/beta(2)] in which beta=1-1/(p+rhoq) and q=1-p and [a] is the greatest integer less than a or equal to a.  相似文献   

2.
We develop a quantitative method for analyzing repetitions of identical short oligomers in coding and noncoding DNA sequences. We analyze sequences presently available in the GenBank separately for primate, mammal, vertebrate, rodent, invertebrate and plant taxonomic partitions. We find that some oligomers "cluster" more than they would if randomly distributed, while other oligomers "repel" each other. To quantify this degree of clustering, we define clustering measures. We find that (i) clustering significantly differs in coding and noncoding DNA; (ii) in most cases, monomers, dimers and tetramers cluster in noncoding DNA but appear to repel each other in coding DNA. (iii) The degree of clustering for different sources (primates, invertebrates, and plants) is more conserved among these sources in the case of coding DNA than in the case of noncoding DNA. (iv) In contrast to other oligomers, we find that trimers always prefer to cluster. (v) Clustering of each particular oligomer is conserved within the same organism.  相似文献   

3.
'Stacking hybridization reactions' wherein two or more short DNA oligomers hybridize in a contiguous tandem orientation onto a longer complementary DNA single strand have been employed to enhance a variety of analytical oligonucleotide hybridization schemes. If the short oligomers anneal in perfect head-to-tail register the resulting duplex contains a nick at every boundary between hybridized oligomers. Alternatively, if the short oligomers do not hybridize precisely in register, i.e. single strand regions on the longer strand are left unbound, gaps are formed between regions where short oligomers bind. The resulting gapped DNA duplexes are considerably less stable than their nicked duplex analogs. Formation of base pair stacking interactions between neighboring oligomers at the nicks that do not occur in gapped duplexes has been proposed as the source of the observed added stability. However, quantitative evidence supporting this hypothesis for DNA has not been reported. Until now, a direct comparison of the thermodynamics of DNA nicks versus DNA gaps has not been performed. In this communication we report such a comparison. Analysis of optical melting experiments in a well defined molecular context enabled quantitative evaluations of the relative thermodynamic difference between nicked and gapped DNA duplexes. Results of the analysis reveal that a nick may be energetically favored over a gap by at least 1.4 kcal/mol and perhaps as much as 2.4 kcal/mol. The presence of a 5'phosphate at a nick or gap fails to significantly affect their stabilities.  相似文献   

4.
Prediction of 1H NMR chemical shifts of DNA oligomers   总被引:2,自引:1,他引:1       下载免费PDF全文
A set of parameters, devised for the prediction of 1H NMR chemical shifts of heterobase and anomeric protons in the high temperature (greater than 70 degrees C) spectra of RNA oligomers has been found to be applicable to the corresponding DNA oligomers. Fifteen examples of DNA oligomers that have had high temperature spectra recorded and assigned show a mean absolute difference between predicted and assigned shifts of 0.045 ppm. The parameters for uridine H-5 are applied to the calculation of thymidine methyl group shifts and give excellent agreement with experimental assigned shifts. The RNA parameter set is a practical means of assigning heterobase and anomeric protons in DNA oligomers. A programme using the RNA parameter set has been written which enables the sequence of short DNA oligomers to be predicted from their 1H NMR spectra.  相似文献   

5.
The sequencing of the genomes of a variety of species and the growing databases containing expressed sequence tags (ESTs) and complementary DNAs (cDNAs) facilitate the design of highly specific oligomers for use as genomic markers, PCR primers, or DNA oligo microarrays. The first step in evaluating the specificity of short oligomers of about 20 units in length is to determine the frequencies at which the oligomers occur. However, for oligomers longer than about fifty units this is not efficient, as they usually have a frequency of only 1. A more suitable procedure is to consider the mismatch tolerance of an oligomer, that is, the minimum number of mismatches that allows a given oligomer to match a substring other than the target sequence anywhere in the genome or the EST database. However, calculating the exact value of mismatch tolerance is computationally costly and impractical. Therefore, we studied the problem of checking whether an oligomer meets the constraint that its mismatch tolerance is no less than a given threshold. Here, we present an efficient dynamic programming algorithm solution that utilizes suffix and height arrays. We demonstrated the effectiveness of this algorithm by efficiently computing a dense list of numerous oligo-markers applicable to the human genome. Experimental results show that the algorithm runs faster than well-known Abrahamson's algorithm by orders of magnitude and is able to enumerate 65% approximately 76% of qualified oligomers.  相似文献   

6.
Cloud computing is an emerging technology and is being widely considered for resource utilization in various research areas. One of the main advantages of cloud computing is its flexibility in computing resource allocations. Many computing cycles can be ready in very short time and can be smoothly reallocated between tasks. Because of this, there are many private companies entering the new business of reselling their idle computing cycles. Research institutes have also started building their own cloud systems for their various research purposes. In this paper, we introduce a framework for virtual cluster system called vcluster which is capable of utilizing computing resources from heterogeneous clouds and provides a uniform view in computing resource management. vcluster is an IaaS (Infrastructure as a Service) based cloud resource management system. It distributes batch jobs to multiple clouds depending on the status of queue and system pool. The main design philosophy behind vcluster is cloud and batch system agnostic and it is achieved through plugins. This feature mitigates the complexity of integrating heterogeneous clouds. In the pilot system development, we use FermiCloud and Amazon EC2, which are a private and a public cloud system, respectively. In this paper, we also discuss the features and functionalities that must be considered in virtual cluster systems.  相似文献   

7.
Zhang H  Liu X 《Bio Systems》2011,105(1):73-82
DNA computing has been applied in broad fields such as graph theory, finite state problems, and combinatorial problem. DNA computing approaches are more suitable used to solve many combinatorial problems because of the vast parallelism and high-density storage. The CLIQUE algorithm is one of the gird-based clustering techniques for spatial data. It is the combinatorial problem of the density cells. Therefore we utilize DNA computing using the closed-circle DNA sequences to execute the CLIQUE algorithm for the two-dimensional data. In our study, the process of clustering becomes a parallel bio-chemical reaction and the DNA sequences representing the marked cells can be combined to form a closed-circle DNA sequences. This strategy is a new application of DNA computing. Although the strategy is only for the two-dimensional data, it provides a new idea to consider the grids to be vertexes in a graph and transform the search problem into a combinatorial problem.  相似文献   

8.
Genome-scale design of PCR primers and long oligomers for DNA microarrays   总被引:2,自引:0,他引:2  
During the last years, the demand for custom-made cDNA chips/arrays as well as whole genome chips is increasing rapidly. The efficient selection of gene-specific primers/oligomers is of the utmost importance for the successful production of such chips. We developed GenomePRIDE, a highly flexible and scalable software for designing primers/oligomers for large-scale projects. The program is able to generate either long oligomers (40–70 bases), or PCR primers for the amplification of gene-specific DNA fragments of user-defined length. Additionally, primers can be designed in-frame in order to facilitate large-scale cloning into expression vectors. Furthermore, GenomePRIDE can be adapted to specific applications such as the generation of genomic amplicon arrays or the design of fragments specific for alternative splice isoforms. We tested the performance of GenomePRIDE on the entire genomes of Listeria monocytogenes (1584 gene-specific PCRs, 48 long oligomers) as well as of eukaryotes such as Schizosaccharomyces pombe (5006 gene-specific PCRs), and Drosophila melanogaster (21 306 gene-specific PCRs). With its computing speed of 1000 primer pairs per hour and a PCR amplification success of 99%, GenomePRIDE represents an extremely cost- and time-effective program.  相似文献   

9.
The preparation and physical properties of short DNA duplexes that contain a N(4)C-ethyl-N(4)C interstrand cross-link are described. Duplexes that contain an interstrand cross-link between mismatched C-C residues and duplexes in which the C residues of a -CG- or -GC- step are linked to give "staggered" interstrand cross-links were prepared using a novel N(4)C-ethyl-N(4)C phosphoramidite reagent. Duplexes with the C-C mismatch cross-link have UV thermal transition temperatures that are 25 degrees C higher than the melting temperatures of control duplexes in which the cross-link is replaced with a G-C base pair. It appears that this cross-link stabilizes adjacent base pairs and does not perturb the structure of the helix, a conclusion that is supported by the CD spectrum of this duplex and by molecular models. An even higher level of stabilization, 49 degrees C, is seen with the duplex that contains a -CG- staggered cross-link. Molecular models suggest that this cross-link may induce propeller twisting in the cross-linked base pairs, and the CD spectrum of this duplex exhibits an unusual negative band at 298 nm, although the remainder of the spectrum is similar to that of B-form DNA. Mismatched C-C or -CG- staggered cross-linked duplexes that have complementary overhanging ends can undergo self-ligation catalyzed by T4 DNA ligase. Analysis of the ligated oligomers by nondenaturing polyacrylamide gel electrophoresis shows that the resulting oligomers migrate in a manner similar to that of a mixture of non-cross-linked control oligomers and suggests that these cross-links do not result in significant bending of the helix. However, the orientation of the staggered cross-link can have a significant effect on the structure and stability of the cross-linked duplex. Thus, the thermal stability of the duplex that contains a -GC- staggered cross-link is 10 degrees C lower than the melting temperature of the control, non-cross-linked duplex. Unlike the -CG- staggered cross-link, in which the cross-linked base pairs can still maintain hydrogen bond contacts, molecular models suggest that formation of the -GC- staggered cross-link disrupts hydrogen bonding and may also perturb adjacent base pairs leading to an overall reduction in helix stability. Duplexes with specifically positioned and oriented cross-links can be used as substrates to study DNA repair mechanisms.  相似文献   

10.

Background

The extracellular nuclease from Alteromonas espejiana, BAL 31 catalyzes the degradation of single-stranded and linear duplex DNA to 5′-mononucleotides, cleaves negatively supercoiled DNA to the linear duplex form, and cleaves duplex DNA in response to the presence of apurinic sites.

Principal Findings

In this work we demonstrate that BAL 31 activity is affected by the presence of guanine in single-stranded DNA oligomers. Specifically, nuclease activity is shown to be affected by guanine''s presence in minimal homopolymeric tracts in the middle of short oligomer substrates and also by its presence at the 3′ end of ten and twenty base oligomers. G•C rich regions in dsDNA are known to cause a decrease in the enzyme''s nuclease activity which has been attributed to the increased thermal stability of these regions, thus making it more difficult to unwind the strands required for enzyme access. Our results indicate that an additional phenomenon could be wholly or partly responsible for the loss of activity in these G•C rich regions. Thus the presence of a guanine tract per se impairs the enzyme''s functionality, possibly due to the tract''s bulky nature and preventing efficient progression through the active site.

Conclusions

This study has revealed that the general purpose BAL 31 nuclease commonly used in molecular genetics exhibits a hithertofore non-characterized degree of substrate specificity with respect to single-stranded DNA (ssDNA) oligomers. Specifically, BAL 31 nuclease activity was found to be affected by the presence of guanine in ssDNA oligomers.  相似文献   

11.

Background

Bacteria show a bias in their genomic oligonucleotide composition far beyond that dictated by G+C content. Patterns of over- and underrepresented oligonucleotides carry a phylogenetic signal and are thus diagnostic for individual species. Patterns of short oligomers have been investigated by multiple groups in large numbers of bacteria genomes. However, global distributions of the most highly overrepresented mid-sized oligomers have not been assessed across all prokaryotes to date. We surveyed overrepresented mid-length oligomers across all prokaryotes and normalised for base composition and embedded oligomers using zero and second order Markov models.

Principal Findings

Here we report a presumably ancient set of oligomers conserved and overrepresented in nearly all branches of prokaryotic life, including Archaea. These oligomers are either adenine rich homopurines with one to three guanine nucleosides, or homopyridimines with one to four cytosine nucleosides. They do not show a consistent preference for coding or non-coding regions or aggregate in any coding frame, implying a role in DNA structure and as polypeptide binding sites. Structural parameters indicate these oligonucleotides to be an extreme and rigid form of B-DNA prone to forming triple stranded helices under common physiological conditions. Moreover, the narrow minor grooves of these structures are recognised by DNA binding and nucleoid associated proteins such as HU.

Conclusion

Homopurine and homopyrimidine oligomers exhibit distinct and unusual structural features and are present at high copy number in nearly all prokaryotic lineages. This fact suggests a non-neutral role of these oligonucleotides for bacterial genome organization that has been maintained throughout evolution.  相似文献   

12.
Li D  Li X  Huang H  Li X 《Bio Systems》2005,82(1):20-25
Previous research presented DNA computing on surfaces, which applied to each clause three operations:"mark","destroy", and "unmark", and demonstrated how to solve a four-variable four-clause instance of the 3-SAT. It was claimed that only the strands satisfying the problem remained on the surface at the end of the computation and the surface-based approach was capable of scaling up to larger 3-SAT problems. Accordingly, the identities of the strands were only determined in the"readout" step for the correct solutions to the problem without checking if the strands really satisfied the problem. Thus, based on the claim above, the surface-based approach became a polynomial-time algorithm. In this paper, we show that for some instance of SAT, at the end of the computation all the remaining strands falsify the instance. However, by the previous claim all the strands falsifying the problems would be regarded as the correct solutions to the problems. Therefore, the DNA computing on surfaces is unreliable. For this reason, it is necessary to add a "verify" step after the "readout" step to check if the strands remaining on the surface at the end of the computation really satisfy the problem.  相似文献   

13.
DNA library design for molecular computation.   总被引:1,自引:0,他引:1  
A novel approach to designing a DNA library for molecular computation is presented. The method is employed for encoding binary information in DNA molecules. It aims to achieve a practical discrimination between perfectly matched DNA oligomers and those with mismatches in a large pool of different molecules. The approach takes into account the ability of DNA strands to hybridize in complex structures like hairpins, internal loops, or bulge loops and computes the stability of the hybrids formed based on thermodynamic data. A dynamic programming algorithm is applied to calculate the partition function for the ensemble of structures, which play a role in the hybridization reaction. The applicability of the method is demonstrated by the design of a twelve-bit DNA library. The library is constructed and experimentally tested using molecular biology tools. The results show a high level of specific hybridization achieved for all library words under identical conditions. The method is also applicable for the design of primers for PCR, DNA sequences for isothermal amplification reactions, and capture probes in DNA-chip arrays. The library could be applied for integrated DNA computing of twelve-bit instances of NP-complete combinatorial problems by multi-step DNA selection in microflow reactors.  相似文献   

14.
The mouse DNA primase-DNA polymerase alpha complex can be resolved with buffer containing 50% ethylene glycol (Suzuki, M., Enomoto, T., Hanaoka, F., and Yamada, M. (1985) J. Biochem. (Tokyo) 98, 581-584). The dissociated primase and DNA polymerase alpha have been purified sufficiently that there was no cross-contamination with each other. By the use of thus isolated DNA primase and DNA polymerase alpha in addition to DNA primase-DNA polymerase alpha complex, we have studied primer RNA synthesis and DNA elongation separately as well as the coupled reaction of the initiation and elongation of DNA chains. In the absence of deoxyribonucleoside triphosphates, the isolated primase synthesized oligoribonucleotides of an apparent length of 7-11 nucleotides (monomeric oligomer) and multiples of a modal length of 9-10 nucleotides (multimeric oligomer) and fd phage single-stranded circular DNA. Monomeric and dimeric oligomers were synthesized processively, and trimeric and larger oligomers were produced by repeated cycles of processive synthesis. The primase complexed with DNA polymerase alpha mainly synthesized monomeric and a small amount of dimeric oligomers. In the presence of deoxyribonucleoside triphosphates at concentrations above 10 microM, the DNA primase-DNA polymerase alpha complex exclusively synthesized monomeric oligomers only, which were utilized as primers for DNA synthesis. On the other hand, the products synthesized by the isolated primase were qualitatively unchanged as compared with those synthesized in the absence of DNA precursors. When the synthesis of oligomers by the isolated primase was coupled with DNA elongation by the addition of the primase-free DNA polymerase alpha, the synthesis of dimeric oligomers was inhibited as a result of efficient DNA elongation from monomeric oligomers.  相似文献   

15.
An improved surface-based method for DNA computation   总被引:36,自引:0,他引:36  
Wu H 《Bio Systems》2001,59(1):1-5
DNA computing is a novel method for solving a class of intractable computational problems, in which the computing time can grow exponentially with problem size. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability, among which a surface-based method is an efficient candidate. In this paper, the surface-based approach proposed by Liu, Q., Wang, L., Frutos, A.G., Condon, A.E., Corn, R.M., and Smith, L.M., 2000, DNA computing on surfaces. Nature 403, 175-179 is analyzed and an improved surface-based method for DNA computation (i.e. the hybrid DNA/optical computing method) is proposed. Compared with Liu et al.'s approach, our method has some significant advantages such as low cost, short operating time, reusable surface and simple experimental steps. Moreover, the concept of combining easily patterned DNA computing steps with equally parallel, but generally uniform and not easily patterned optical computing steps is an important new direction.  相似文献   

16.
Growing evidence suggests that DNA repair capacity is an important factor in cancer risk and is therefore essential to assess. Immunochemical assays are amenable to the detection of repair products in complex matrices, such as urine, facilitating noninvasive measurements, although diet and extra-DNA sources of lesion can confound interpretation. The production of single-stranded, lesion-containing DNA oligomers characterises nucleotide excision repair (NER) and hence defines the repair pathway from which a lesion may be derived. Herein we describe the characterisation of a monoclonal antibody which recognises guanine moieties in single-stranded DNA. Application of this antibody in ELISA, demonstrated such oligomers in supernatants from repair-proficient cells post-insult. Testing of urine samples from volunteers demonstrated a relationship between oligomer levels and two urinary DNA damage products, thymine dimers and 8-oxo-2'-deoxyguanosine, supporting our hypothesis that NER gives rise to lesion-containing oligomers which are specific targets for the investigation of DNA repair.  相似文献   

17.
The cytotoxicity, mutagenicity, and carcinogenicity of DNA base lesions are largely determined by the responses of cellular DNA repair proteins, DNA polymerases, and signaling pathways. Elucidation of these processes is thus of high biochemical interest. Such studies increasingly rely on DNA substrates containing specific lesions at defined locations. Although short synthetic DNA oligomers have frequently proved useful, circular plasmid substrates are preferable for much biochemical work, and essential for in vivo studies. However, the complexity of current approaches for preparing such substrates and limitations inherent in the procedures have posed problems. We present here a simple, highly versatile procedure for preparing gapped duplex plasmids, into which oligomers incorporating specific lesions can easily be inserted. Endonuclease N.BstNBI was used to nick twice the same strand of a pUC19-derived plasmid (pUC19HBDa), at two GAGTCNNNN sequences separated by 22 bases. Removal of the 22-nt oligomer and further purification produced a highly pure gapped plasmid. To illustrate application of this procedure, 22-nt oligonucleotides containing a single uracil residue were ligated into the gapped molecules. The pUC19HB(Da) plasmid can be modified to accept almost any DNA-lesion-containing oligomer. Using this new approach to incorporate specific DNA lesions into popular reporter genes will facilitate in vivo study of cellular responses to DNA damage.  相似文献   

18.
The formation of oligomers of simian virus 40 (SV40) large T antigen in SV40-infected and -transformed monkey cells was analyzed by sucrose density gradient centrifugation. The overall distribution of total T antigen during lytic infection showed mainly low-molecular-weight forms (monomers and dimers) in the early phase (10 h postinfection) and an increase in the number of oligomers in the late phase of the lytic cycle (36 h postinfection), indicating an accumulation of these final products. In contrast, studying the conversion of newly synthesized T antigen into oligomers by appropriate pulse-chase radiolabeling of infected cells revealed that this processing decelerates considerably during the late phase of infection. This mechanism can be reaccelerated by blocking DNA replication with aphidicolin. Since none of these results could be obtained by using synchronized SV40-transformed monkey cells (COS-1), these observations are compatible with the idea that the process of T antigen oligomerization may be involved in viral, but not in cellular, DNA synthesis.  相似文献   

19.
Molecular dynamics (MD) simulations including water and counterions on B-DNA oligomers containing all 136 unique tetranucleotide basepair steps are reported. The objective is to obtain the calculated dynamical structure for at least two copies of each case, use the results to examine issues with regard to convergence and dynamical stability of MD on DNA, and determine the significance of sequence context effects on all unique dinucleotide steps. This information is essential to understand sequence effects on DNA structure and has implications on diverse problems in the structural biology of DNA. Calculations were carried out on the 136 cases embedded in 39 DNA oligomers with repeating tetranucleotide sequences, capped on both ends by GC pairs and each having a total length of 15 nucleotide pairs. All simulations were carried out using a well-defined state-of-the-art MD protocol, the AMBER suite of programs, and the parm94 force field. In a previous article (Beveridge et al. 2004. Biophysical Journal. 87:3799-3813), the research design, details of the simulation protocol, and informatics issues were described. Preliminary results from 15 ns MD trajectories were presented for the d(CpG) step in all 10 unique sequence contexts. The results indicated the sequence context effects to be small for this step, but revealed that MD on DNA at this length of trajectory is subject to surprisingly persistent cooperative transitions of the sugar-phosphate backbone torsion angles alpha and gamma. In this article, we report detailed analysis of the entire trajectory database and occurrence of various conformational substates and its impact on studies of context effects. The analysis reveals a possible direct correspondence between the sequence-dependent dynamical tendencies of DNA structure and the tendency to undergo transitions that "trap" them in nonstandard conformational substates. The difference in mean of the observed basepair step helicoidal parameter distribution with different flanking sequence sometimes differs by as much as one standard deviation, indicating that the extent of sequence effects could be significant. The observations reveal that the impact of a flexible dinucleotide such as CpG could extend beyond the immediate basepair neighbors. The results in general provide new insight into MD on DNA and the sequence-dependent dynamical structural characteristics of DNA.  相似文献   

20.
ABSTRACT: BACKGROUND: The molecular recognition based on the complementary base pairing of deoxyribonucleicacid (DNA) is the fundamental principle in the fields of genetics, DNA nanotechnologyand DNA computing. We present an exhaustive DNA sequence design algorithm thatallows to generate sets containing a maximum number of sequences with definedproperties. EGNAS (Exhaustive Generation of Nucleic Acid Sequences) offers thepossibility of controlling both interstrand and intrastrand properties. The guanine-cytosinecontent can be adjusted. Sequences can be forced to start and end with guanine orcytosine. This option reduces the risk of "fraying" of DNA strands. It is possible to limitcross hybridizations of a defined length, and to adjust the uniqueness of sequences.Self-complementarity and hairpin structures of certain length can be avoided. Sequencesand subsequences can optionally be forbidden. Furthermore, sequences can be designed tohave minimum interactions with predefined strands and neighboring sequences. RESULTS: The algorithm is realized in a C++ program. TAG sequences can be generated andcombined with primers for single-base extension reactions, which were described formultiplexed genotyping of single nucleotide polymorphisms. Thereby, possible foldbackthrough intrastrand interaction of TAG-primer pairs can be limited. The design ofsequences for specific attachment of molecular constructs to DNA origami is presented. CONCLUSIONS: We developed a new software tool called EGNAS for the design of unique nucleic acidsequences. The presented exhaustive algorithm allows to generate greater sets ofsequences than with previous software and equal constraints. EGNAS is freely availablefor noncommercial use at http://www.chm.tu-dresden.de/pc6/EGNAS.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号