A new solution for maximal clique problem based sticker model

In this paper, we use stickers to construct a solution space of DNA for the maximal clique problem (MCP). Simultaneously, we also apply the DNA operation in the sticker-based model to develop a DNA algorithm. The results of the proposed algorithm show that the MCP is resolved with biological operations in the sticker-based model for the solution space of the sticker. Moreover, this work presents clear evidence of the ability of DNA computing to solve the NP-complete problem. The potential of DNA computing for the MCP is promising given the operational time complexity of O(nxk).     

Mathematical properties and bounds on haplotyping populations by pure parsimony

Although the haplotype data can be used to analyze the function of DNA, due to the significant efforts required in collecting the haplotype data, usually the genotype data is collected and then the population haplotype inference (PHI) problem is solved to infer haplotype data from genotype data for a population. This paper investigates the PHI problem based on the pure parsimony criterion (HIPP), which seeks the minimum number of distinct haplotypes to infer a given genotype data. We analyze the mathematical structure and properties for the HIPP problem, propose techniques to reduce the given genotype data into an equivalent one of much smaller size, and analyze the relations of genotype data using a compatible graph. Based on the mathematical properties in the compatible graph, we propose a maximal clique heuristic to obtain an upper bound, and a new polynomial-sized integer linear programming formulation to obtain a lower bound for the HIPP problem.     

ULS: a versatile method of labeling nucleic acids for FISH based on a monofunctional reaction of cisplatin derivatives with guanine moieties

The broad extension of an existing chemical DNA labeling technique for molecular cytogenetics is described. Called the Universal Linkage System (ULS(TM)), it is based on the capability of monoreactive cisplatin derivatives to react at the N7 position of guanine moieties in DNA. Simple repetitive probes, cosmids, PACs, and chromosome-specific painting probes were labeled by ULS and used in a series of multicolor fluorescence in situ hybridization experiments on interphase and metaphase cells. It is demonstrated that ULS-labeled probes, in general, perform as well as the more conventional enzymatically labeled probes. The advantage of ULS labeling over enzymatic labeling techniques is that it is a fast and simple procedure, and that the labeling can easily be scaled up for bulk probe synthesis. In addition, with ULS labeling it is possible to label degraded DNA, a situation in which enzymatic labeling is known to perform unsatisfactorily.     

Scalability of the surface-based DNA algorithm for 3-SAT

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.     

Predicting Disease-Related Proteins Based on Clique Backbone in Protein-Protein Interaction Network

Network biology integrates different kinds of data, including physical or functional networks and disease gene sets, to interpret human disease. A clique (maximal complete subgraph) in a protein-protein interaction network is a topological module and possesses inherently biological significance. A disease-related clique possibly associates with complex diseases. Fully identifying disease components in a clique is conductive to uncovering disease mechanisms. This paper proposes an approach of predicting disease proteins based on cliques in a protein-protein interaction network. To tolerate false positive and negative interactions in protein networks, extending cliques and scoring predicted disease proteins with gene ontology terms are introduced to the clique-based method. Precisions of predicted disease proteins are verified by disease phenotypes and steadily keep to more than 95%. The predicted disease proteins associated with cliques can partly complement mapping between genotype and phenotype, and provide clues for understanding the pathogenesis of serious diseases.     

Equilibrium Distributions of Populations of Biological Species on Networks of Social Sites

ABSTRACT

We investigate the problem of how a population of biological species would distribute over a given network of social sites so that their social contacts through the connected sites can be maximized (or minimized). This problem has applications in modelling the behaviours of social (or solitary) species such as the development of social groups in human society and the spread of solitary animals in distant habitats. We show that this problem can be formulated as an evolutionary game, with the equilibrium state of the game corresponding to a strategy for choosing the residing sites, each with a certain probability, or equivalently, to a distribution of the population on these sites. The game has a symmetric payoff matrix, and can therefore be analyzed via the solution of a corresponding quadratic programme: An equilibrium strategy of the game is a KKT point of the quadratic programme, which may be a local maximizer, local minimizer, or saddle point, but it is evolutionarily stable if and only if it is a strict local maximizer. In general, with a goal to maximize the social contacts, the species tend to spread on network sites where there are dense connections such as a complete subnetwork or in other words, a network clique. We show that at equilibrium, the population may or may not distribute on a network clique, but the stability of the equilibrium state does depend on the structure of the selected subnetwork. In particular, we show that the distribution of the population on a maximal network clique is evolutionarily stable unless the clique is ‘attached’ to another clique of the same or larger size, when the population may be able to switch or expand to the neighbouring clique to increase or at least maintain its total amount of contacts. However, the distribution of the population on a non-clique subnetwork is always evolutionarily unstable or weakly evolutionarily stable at the very best, for the population can always move away from its current distribution without decreasing its total amount of contacts. We conclude that the strategies to spread on maximal network cliques are not only equilibrium strategies but also evolutionarily more stable than those on non-clique subnetworks, thus theoretically reaffirming the evolutionary advantages of joining social cliques in social networks for social species.     

A flexible annealing chaotic neural network to maximum clique problem

Based on the analysis and comparison of several annealing strategies, we present a flexible annealing chaotic neural network which has flexible controlling ability and quick convergence rate to optimization problem. The proposed network has rich and adjustable chaotic dynamics at the beginning, and then can converge quickly to stable states. We test the network on the maximum clique problem by some graphs of the DIMACS clique instances, p-random and k random graphs. The simulations show that the flexible annealing chaotic neural network can get satisfactory solutions at very little time and few steps. The comparison between our proposed network and other chaotic neural networks denotes that the proposed network has superior executive efficiency and better ability to get optimal or near-optimal solution.     

Find Pairs: The Module for Protein Quantification of the PeakQuant Software Suite

Abstract Accurate quantification of proteins is one of the major tasks in current proteomics research. To address this issue, a wide range of stable isotope labeling techniques have been developed, allowing one to quantitatively study thousands of proteins by means of mass spectrometry. In this article, the FindPairs module of the PeakQuant software suite is detailed. It facilitates the automatic determination of protein abundance ratios based on the automated analysis of stable isotope-coded mass spectrometric data. Furthermore, it implements statistical methods to determine outliers due to biological as well as technical variance of proteome data obtained in replicate experiments. This provides an important means to evaluate the significance in obtained protein expression data. For demonstrating the high applicability of FindPairs, we focused on the quantitative analysis of proteome data acquired in (14)N/(15)N labeling experiments. We further provide a comprehensive overview of the features of the FindPairs software, and compare these with existing quantification packages. The software presented here supports a wide range of proteomics applications, allowing one to quantitatively assess data derived from different stable isotope labeling approaches, such as (14)N/(15)N labeling, SILAC, and iTRAQ. The software is publicly available at http://www.medizinisches-proteom-center.de/software and free for academic use.     

Sequence tagged microsatellite profiling (STMP): improved isolation of DNA sequence flanking target SSRs

Sequence tagged microsatellite profiling (STMP) enables the rapid development of large numbers of co-dominant DNA markers, known as sequence tagged microsatellites (STMs). Each STM is amplified by PCR using a single primer specific to the conserved DNA sequence flanking the microsatellite repeat in combination with a universal primer that anchors to the 5′-ends of the microsatellites. It is also possible to convert STMs into conventional microsatellite, or simple sequence repeat (SSR), markers that are amplified using a pair of primers flanking the repeat sequence. Here, we describe a modification of the STMP procedure to significantly improve the capacity to convert STMs into conventional SSRs and, therefore, facilitate the development of highly specific DNA markers for purposes such as marker-assisted breeding. The usefulness of this technique was demonstrated in bread wheat.     

Optimized amplification and fluorescent labeling of small cell samples for genomic array-CGH.

BACKGROUND: Whole genome amplification (WGA) is usually needed in the genetic analysis of samples containing a low number of cells. In genome-wide analysis of DNA copy numbers by array comparative genomic hybridization (array-CGH) it is very important that the genome is evenly represented throughout the amplified product. All currently available WGA techniques are generating some degree of bias. METHODS: A way to compensate for this is using a reference sample which is similarly amplified, as the introduced amplification bias will be leveled out. Additionally, direct labeling of the amplified DNA is performed to bypass the currently widely applied random primed labeling, which involves an additional amplification of the product and is introducing extra bias. RESULTS: In this article it is shown that equal processing of the test and reference sample is indeed crucial to generate an optimal array-CGH profile of amplified DNA samples. Also presented here is that the labeling method may significantly effect the array-CGH result, it is shown that with direct chemical labeling using platinum derivates (ULS labeling) optimal array-CGH results are obtained. CONCLUSIONS: We show that an optimized WGA strategy for both test and reference sample in combination with direct chemical labeling results in a reliable array-CGH profile of samples as low as a 30 cell equivalent.     

Immunofluorescent flow cytometry in N dimensions. The multiplex labeling approach

The problem of the simultaneous use in flow cytometry of N greater than 2 antibodies in conjunction with two fluorochromes was investigated. Theoretical analysis led to a labeling procedure and reconstruction formula that allow N-dimensional labeling distributions to be obtained from two-dimensional fluorescence distributions. The general problem of M greater than or equal to 2 fluorochromes and N greater than M antibodies was shown to be reducible to the case of two fluorochromes. The method was tested by a triple labeling analysis of murine thymocytes.     

An improved transiently chaotic neural network for the maximum independent set problem

By analyzing the dynamic behaviors of the transiently chaotic neural network and greedy heuristic for the maximum independent set (MIS) problem, we present an improved transiently chaotic neural network for the MIS problem in this paper. Extensive simulations are performed and the results show that this proposed transiently chaotic neural network can yield better solutions to p-random graphs than other existing algorithms. The efficiency of the new model is also confirmed by the results on the complement graphs of some DIMACS clique instances in the second DIMACS challenge. Moreover, the improved model uses fewer steps to converge to stable state in comparison with the original transiently chaotic neural network.     

cWINNOWER algorithm for finding fuzzy dna motifs

The cWINNOWER algorithm detects fuzzy motifs in DNA sequences rich in protein-binding signals. A signal is defined as any short nucleotide pattern having up to d mutations differing from a motif of length l. The algorithm finds such motifs if a clique consisting of a sufficiently large number of mutated copies of the motif (i.e., the signals) is present in the DNA sequence. The cWINNOWER algorithm substantially improves the sensitivity of the winnower method of Pevzner and Sze by imposing a consensus constraint, enabling it to detect much weaker signals. We studied the minimum detectable clique size qc as a function of sequence length N for random sequences. We found that qc increases linearly with N for a fast version of the algorithm based on counting three-member sub-cliques. Imposing consensus constraints reduces qc by a factor of three in this case, which makes the algorithm dramatically more sensitive. Our most sensitive algorithm, which counts four-member sub-cliques, needs a minimum of only 13 signals to detect motifs in a sequence of length N = 12,000 for (l, d) = (15, 4).     

Solving the set cover problem and the problem of exact cover by 3-sets in the Adleman-Lipton model

Adleman wrote the first paper in which it is shown that deoxyribonucleic acid (DNA) strands could be employed towards calculating solutions to an instance of the NP-complete Hamiltonian path problem (HPP). Lipton also demonstrated that Adleman's techniques could be used to solve the NP-complete satisfiability (SAT) problem (the first NP-complete problem). In this paper, it is proved how the DNA operations presented by Adleman and Lipton can be used for developing DNA algorithms to resolving the set cover problem and the problem of exact cover by 3-sets.     

DNA synthesis rate and unlabeled cells with S-phase DNA content in P388 leukemic cells in vivo studied by flow cytometry and cell sorting

DNA synthesis kinetics of P388 leukemic cells growing in ascites form in BDF1 hybrid mice were investigated during the periods of exponential growth and growth restriction. Incorporation of tritiated thymidine, and in some instances tritiated uridine, was studied by autoradiography in cells sorted from S-phase fractions during DNA flow cytometry. During exponential growth continuous labeling with tritiated thymidine indicated a growth fraction of unity, whereas the growth fraction was about 30% during growth restriction. At this growth phase the majority of cells with S phase DNA content remained unlabeled after pulse labeling with tritiated thymidine or uridine, indicating that both the "salvage" and the "de novo" DNA synthesis pathways were blocked in most S-phase cells. After pulse labeling with tritiated thymidine the DNA synthesis rate pattern was investigated by sorting of consecutive fractions of cells throughout the S phase followed by quantitative autoradiography. With exception of a reduced rate in the middle of S phase, the DNA synthesis rate increased as the cells progressed through S phase during exponential growth. In contrast, the DNA synthesis rate pattern had a relative peak in the middle of S phase during growth restriction, which is otherwise characterized by a low mean DNA synthesis rate.     

Multiplexed, particle-based detection of DNA using flow cytometry with 3DNA dendrimers for signal amplification.

BACKGROUND: Complex mixtures of DNA may be found in environmental and medical samples. There is a need for techniques that can measure low concentrations of target DNAs. For a multiplexed, flow cytometric assay, we show that the signal-to-noise ratio for fluorescence detection may be increased with the use of 3DNA dendrimers. A single fluorescent DNA molecule per bead could be detected with conventional flow cytometry instrumentation. METHODS: The analyte consisted of single-stranded (ss) DNA amplicons that were hybridized to capture probes on the surface of fluorescent polystyrene microspheres (beads) and initially labeled with streptavidin-R-phycoerythrin (single-step labeling). These beads have a low reporter fluorescence background and high efficiency of DNA hybridization. The DNA/SA-RPE complex was then labeled with 3DNA dendrimers and SA-RPE. The bead complexes were detected with a Luminex 100 flow cytometer. Bead standards were developed to convert the intensity to the number of SA-RPE labels per bead and the number of dendrimers per bead. RESULTS: The dendrimer assay resulted in 10-fold fluorescence amplification compared with single-step SA-RPE labeling. Based on concentration curves of pure target ss-amplicons, the signal-to-noise ratio of the dendrimer assay was greater by a factor of 8.5 over single-step SA-RPE labeling. The dendrimer assay was tested on 16S ribosomal DNA amplified from filter retentates of contaminated groundwater. Multiplexed detection of a single dendrimer-labeled DNA molecule per bead was demonstrated. CONCLUSIONS: Multiplexed detection of DNA hybridization on a single molecule level per bead was achieved with conventional flow cytometry instrumentation. This assay is useful for detecting target DNAs at low concentrations.     

Identification of close contacts between the sigma N (sigma 54) protein and promoter DNA in closed promoter complexes.

The complexes forming between the alternative sigma factor protein sigma N (sigma 54), its holoenzyme and promoter DNA were analysed using the hydroxyl radical probe and by photochemical footprinting of bromouridine-substituted DNA. Close contacts between the promoter, sigma N and its holoenzyme appear to be restricted predominantly to one face of the DNA helix, extending from -31 to -5. They all appear attributable to sigma N and no extra close contacts from the core RNA polymerase subunits in the holoenzyme-promoter DNA complex were detected. We suggest that the apparent absence of close core RNA polymerase contacts in the region of the promoter DNA to be melted during open complex formation is important for maintaining the closed complex. Results of the hydroxyl radical footprinting imply that sigma N makes multiple DNA backbone contacts across and beyond the -12, -24 consensus promoter elements, and the photochemical footprints indicate that consensus thymidine residues contribute important major groove contacts to sigma N. Formation of the open complex is shown to involve a major structural transition in the DNA contacted by sigma N, establishing a direct role for sigma N in formation of the activated promoter complex.     

A DNA biosensor based on peptide nucleic acids on gold surfaces

We present a DNA biosensor based on self-assembled monolayers (SAMs) of thiol-derivatized peptide nucleic acid (PNA) molecules adsorbed on gold surfaces. Previous works have shown that PNA molecules at an optimal concentration can be self-assembled with their molecular axes normal to the surface. In such structural configuration BioSAMs of PNAs maintain their capability for recognizing complementary DNA. We describe the combined use of PM-RAIRS and synchrotron radiation XPS for the detection and spectroscopic characterization of PNA-DNA hybridization process on gold surfaces. RAIRS and XPS are powerful techniques for surface characterization and molecular detection, which do not require a fluorescence labeling of the target. We present a characterization of the spectroscopic IR and XPS features, some of them associated to the phosphate groups of the DNA backbone, as an unambiguous signature of the PNA-DNA heteroduplex formation. The N(1s) XPS core level peak after DNA hybridization is decomposed in curves components, and every component assigned to different chemical species. Therefore, the results obtained by means of two complementary structural characterization techniques encourage the use of PNA-based biosensors for the detection of DNA molecules on natural samples.     

Biosynthetic preparation of L-[13C]- and [15N]glutamate by Brevibacterium flavum.

The biosynthesis of isotopically labeled L-glutamic acid by the microorganism Brevibacterium flavum was studied with a variety of carbon-13-enriched precursors. The purpose of this study was twofold: to develop techniques for the efficient preparation of labeled L-glutamate with a variety of useful labeling patterns which can be used for other metabolic studies, and to better understand the metabolic events leading to label scrambling in these strains. B. flavum, which is used commercially for the production of monosodium glutamate, has the capability of utilizing glucose or acetate as a sole carbon source, an important criterion from the standpoint of developing labeling strategies. Unfortunately, singly labeled glucose precursors lead to excessive isotopic dilution which reduces their usefulness. Studies with [3-13C]pyruvate indicate that this problem can in principle be overcome by using labeled three-carbon precursors; however, conditions could not be found which would lead to an acceptable yield of isotopically labeled L-glutamate. In contrast, [1-13C]- or [2-13C]acetate provides relatively inexpensive, readily available precursors for the production of selectively labeled, highly enriched L-glutamate. The preparation of L-[15N]glutamate from [15N]ammonium sulfate was carried out and is a very effective labeling strategy. Analysis of the isotopic distribution in labeled glutamate provides details about the metabolic pathways in these interesting organisms.     

Effect of photoreactivating light on survival of ultraviolet-light-irradiatedStreptomyces lividans 66

Summary Biological systems can repair damage induced in their DNA by ultraviolet light (UV). Most cells contain at least three DNA repair pathways, each of which has a marked effect on UV survival. Excision repair and recombinational (postreplication) repair are light-independent whereas photoreactivation (PR), whether enzyzmatic or photochemical, is light-dependent. The specificity of photoreactivation for UV-induced DNA damage allows it to be used as a tool for examining whether premutational DNA lesions are preferred sites for photoreversal; it therefore plays an important role in mutagenesis studies. Evidence is presented here that PR occurs in a time-dependent fashion in three strains ofStreptomyces lividans 66. The effect appears to be independent of temperature and is observed only when PR treatment is given after UV irradiation. The present experiments do not discriminate between enzymatic and photochemical protection.