New Contig Creation Algorithm for the de novo DNA Assembly Problem

DNA assembly is among the most fundamental and difficult problems in bioinformatics. Near optimal assembly solutions are available for bacterial and small genomes, however assembling large and complex genomes especially the human genome using Next-Generation-Sequencing (NGS) technologies is shown to be very difficult because of the highly repetitive and complex nature of the human genome, short read lengths, uneven data coverage and tools that are not specifically built for human genomes. Moreover, many algorithms are not even scalable to human genome datasets containing hundreds of millions of short reads. The DNA assembly problem is usually divided into several subproblems including DNA data error detection and correction, contig creation, scaffolding and contigs orientation; each can be seen as a distinct research area. This thesis specifically focuses on creating contigs from the short reads and combining them with outputs from other tools in order to obtain better results. Three different assemblers including SOAPdenovo [Li09], Velvet [ZB08] and Meraculous [CHS+11] are selected for comparative purposes in this thesis. Obtained results show that this thesis’ work produces comparable results to other assemblers and combining our contigs to outputs from other tools, produces the best results outperforming all other investigated assemblers.

Component Inventory Costs in an Assembly Problem with Uncertain Supplier Lead-Times

We present a generic study of inventory costs in a factory stockroom that supplies component parts to an assembly line. Specifically, we are concerned with the increase in component inventories due to uncertainty in supplier lead-times, and the fact that several different components must be present before assembly can begin. It is assumed that the suppliers of the various components are independent, that the suppliers' operations are in statistical equilibrium, and that the same amount of each type of component is demanded by the assembly line each time a new assembly cycle is scheduled to begin. We use, as a measure of inventory cost, the expected time for which an order of components must be held in the stockroom from the time it is delivered until the time it is consumed by the assembly line. Our work reveals the effects of supplier lead-time variability, the number of different types of components, and their desired service levels, on the inventory cost. In addition, under the assumptions that inventory holding costs and the cost of delaying assembly are linear in time, we study optimal ordering policies and present an interesting characterization that is independent of the supplier lead-time distributions.

The land assembly problem revisited

As in the standard land assembly problem, a developer wants to buy two adjacent blocks of land belonging to two di¤erent owners. The value of the two blocks of land to the developer is greater than the sum of the individual values of the blocks for each owner. Unlike the land assembly literature, however, our focus is on the incentive that each lot owner has to delay the start of negotiations, rather than on the public goods nature of the problem. An incentive for delay exists, for example, when owners perceive that being last to sell will allow them to capture a larger share of the joint surplus from the development. We show that competition at point of sale can cause equilibrium delay, and that cooperation at point of sale will eliminate delay.

Fast assembly of non-thiolated DNA on gold surface at lower pH

In a typical protocol for attaching DNA to a gold electrode, thiolated DNA is incubated with the electrode at neutral pH overnight. Here we report fast adsorption of non-thiolated DNA oligomers on gold electrodes at acidic pH (i.e., pH ~3.0). The peak-to-peak potential difference and the redox peak currents in typical cyclic voltammetry of [Fe(CN)6]3- are investigated to monitor the attachment. Compared with incubation at neutral pH, the lower pH can significantly promote the adsorption processes, enabling efficient adsorption even in 30min. The adsorption rate is DNA concentration-dependent, while the ionic strength shows no influence. Moreover, the adsorption is base-discriminative, with a preferred order of A>C≫G, T, which is attributed to the protonation of A and C at low pH and their higher binding affinity to gold surface. The immobilized DNA is functional and can hybridize with its complementary DNA but not a random DNA. This work is promising to provide a useful time-saving strategy for DNA assembly on gold electrodes, allowing fast fabrication of DNA-based biosensors and devices. © 2013 Elsevier Inc.

Multiplexed DNA-mediated electrochemistry

The aromatic core of double helical DNA possesses the unique and remarkable ability to form a conduit for electrons to travel over exceptionally long molecular distances. This core of π-stacked nucleobases creates an efficient pathway for charge transfer to proceed that is exquisitely sensitive to even subtle perturbations. Ground state electrochemistry of DNA-modified electrodes has been one of the major techniques used both to investigate and to harness the property of DNA-mediated charge transfer. DNA-modified electrodes have been an essential tool for both gaining insights into the fundamental properties of DNA and, due to the exquisite specificity of DNA-mediated charge transfer for the integrity of the π-stack, for use in next generation diagnostic sensing. Here, multiplexed DNA-modified electrodes are used to (i) gain new insights on the electrochemical coupling of metalloproteins to the DNA π-stack with relevance to the fundaments of in vivo DNA-mediated charge transfer and (ii) enhance the overall sensitivity of DNA-mediated reduction for use in the detection of low abundance diagnostic targets.

First, Methylene Blue (MB′) was covalently attached to DNA through a flexible C12 alkyl linker to yield a new redox reporter for DNA electrochemistry measurements with enhanced sensitivity. Tethered, intercalated MB′ was reduced through DNA-mediated charge transport. The redox signal intensity for MB′-dT-C12-DNA was found to be at least 3 fold larger than that of previously used Nile Blue (NB)-dT-DNA, which is coupled to the base stack via direct conjugation. The signal attenuation, due to an intervening mismatch, and therefore the degree of DNA-mediated reduction, does, however, depend on the DNA film morphology and the backfilling agent used to passivate the surface. These results highlight two possible mechanisms for the reduction of MB′ on the DNA-modified electrode that are distinguishable by their kinetics: reduction mediated by the DNA base pair stack and direct surface reduction of MB′ at the electrode. The extent of direct reduction at the surface can be minimized by overall DNA assembly conditions.

Next, a series of intercalation-based DNA-mediated electrochemical reporters were developed, using a flexible alkane linkage to validate and explore their DNA-mediated reduction. The general mechanism for the reduction of distally bound redox active species, covalently tethered to DNA through flexible alkyl linkages, was established to be an intraduplex DNA-mediated pathway. MB, NB, and anthraquinone were covalently tethered to DNA with three different covalent linkages. The extent of electronic coupling of the reporter was shown to correlate with the DNA binding affinity of the redox active species, supporting an intercalative mechanism. These electrochemical signals were shown to be exceptionally sensitive to a single intervening π-stack perturbation, an AC mismatch, in a densely packed DNA monolayer, which further supports that the reduction is DNA-mediated. Finally, this DNA-mediated reduction of MB occurs primarily via intra- rather than inter duplex intercalation, as probed through varying the proximity and integrity of the neighboring duplex DNA. Further gains to electrochemical sensitivity of our DNA-modified devices were then achieved through the application of electrocatalytic signal amplification using these solvent accessible intercalative reporters, MB-dT-C8, and hemoglobin as a novel electron sink. Electrocatalysis offers an excellent means of electrochemical signal amplification, yet in DNA based sensors, its application has been limited due to strict assembly conditions. We describe the use of hemoglobin as a robust and effective electron sink for electrocatalysis in DNA sensing on low density DNA films. Protein shielding of the heme redox center minimizes direct reduction at the electrode surface and permits assays on low density DNA films. Electrocatalysis of MB that is covalently tethered to the DNA by a flexible alkyl linkage allows for efficient interactions with both the base stack and hemoglobin. Consistent suppression of the redox signal upon incorporation of single CA mismatch in the DNA oligomer demonstrates that both the unamplified and the electrocatalytically amplified redox signals are generated through DNA-mediated charge transport. Electrocatalysis with hemoglobin is robust: it is stable to pH and temperature variations. The utility and applicability of electrocatalysis with hemoglobin is demonstrated through restriction enzyme detection, and an enhancement in sensitivity permits femtomole DNA sampling.

Finally, we expanded the application of our multiplexed DNA-modified electrodes to the electrochemical characterization of DNA-bound proteins containing [4Fe-4S] clusters. DNA-modified electrodes have become an essential tool for the characterization of the redox chemistry of DNA repair proteins that contain redox cofactors. Multiplexed analysis of EndonucleaseIII (EndoIII), a DNA repair protein containing a [4Fe-4S] cluster known to be accessible via DNA-mediated charge transport, elucidated subtle differences in the electrochemical behavior as a function of DNA morphology. DNA-bound EndoIII is seen to have two different electron transfer pathways for reduction, either through the DNA base stack or through direct surface reduction. Closely packed DNA films, where the protein has limited surface accessibility, produce electrochemical signals reflecting electron transfer that is DNA-mediated. The electrochemical comparison of EndoIII mutants, including a new family of mutations altering the electrostatics surrounding the [4Fe-4S] cluster, was able to be quantitatively performed. While little change in the midpoint potential was found for this family of mutants, significant variations in the efficiency of DNA-mediated electron transfer were apparent. Based on the stability of these proteins, examined by circular dichroism, we propose that the electron transfer pathway can be perturbed not only by the removal of aromatic residues, but also through changes in solvation near the cluster.

The Design of a Mechanical Assembly System

This thesis describes a mechanical assembly system called LAMA (Language for Automatic Mechanical Assembly). The goal of the work was to create a mechanical assembly system that transforms a high-level description of an automatic assembly operation into a program or execution by a computer controlled manipulator. This system allows the initial description of the assembly to be in terms of the desired effects on the parts being assembled. Languages such as WAVE [Bolles & Paul] and MINI [Silver] fail to meet this goal by requiring the assembly operation to be described in terms of manipulator motions. This research concentrates on the spatial complexity of mechanical assembly operations. The assembly problem is seen as the problem of achieving a certain set of geometrical constraints between basic objects while avoiding unwanted collisions. The thesis explores how these two facets, desired constraints and unwanted collisions, affect the primitive operations of the domain.

Hierarchical self-assembly of nucleotide-appended oligopyrenotides into defined supramolecular objects

Supramolecular DNA assembly blends DNA building blocks with synthetic organic and inorganic molecules giving structural and functional advantages both to the initial self-assembly process and to the final construct. Synthetic molecules can bring a number of additional interactions into DNA nanotechnology. Incorporating extended aromatic molecules as connectors of DNA strands allows folding of these strands through π-π stacking (DNA “foldamers”). In previous work it was shown that short oligopyrenotides (phosphodiester-linked pyrene oligomers) behave as staircase-like foldamers, which cooperatively self-assemble into two-dimensional supramolecular polymers in aqueous medium. Herein, we demonstrate that a 10-mer DNA-sequence modified with 7 pyrene units (see illustration) forms dimensionally-defined supramolecular polymers under thermodynamic conditions in water. We present the self-assembly behavior, morphological studies, and the spectroscopic properties of the investigated DNA-sequences (illustrative AFM picture shown below).

Hierarchical self-assembly of nucleotide-appended oligopyrenotides into defined supramolecular objects

Supramolecular DNA assembly blends DNA building blocks with synthetic organic molecules giving structural and functional advantages. Incorporating extended aromatic molecules as connectors of DNA strands allows folding of these strands through π-π stacking (DNA 'foldamers'). In previous work it was shown that short oligopyrenotides behave as staircase-like foldamers, which cooperatively self-assemble into 2D supramolecular polymers in aqueous medium. Herein, we demonstrate that 10-mer DNA-sequence conjugated with seven pyrene unites forms dimensionally-defined supramolecular polymers under thermodynamic conditions in water. We present the self-assembly behavior, morphologycal studies (AFM and TEM), and the spectroscopic properties (UV/vis, CD) of the investigated pyrene - conjugated DNA-sequence.

Two-stage no-wait scheduling models with setup and removal times separated

This paper studies two models of two-stage processing with no-wait in process. The first model is the two-machine flow shop, and the other is the assembly model. For both models we consider the problem of minimizing the makespan, provided that the setup and removal times are separated from the processing times. Each of these scheduling problems is reduced to the Traveling Salesman Problem (TSP). We show that, in general, the assembly problem is NP-hard in the strong sense. On the other hand, the two-machine flow shop problem reduces to the Gilmore-Gomory TSP, and is solvable in polynomial time. The same holds for the assembly problem under some reasonable assumptions. Using these and existing results, we provide a complete complexity classification of the relevant two-stage no-wait scheduling models.

Sequence-specific reconstruction from fragmentary databases using seed sequences: implementation and validation on SAGE, proteome and generic sequencing data

Motivation: DNA assembly programs classically perform an all-against-all comparison of reads to identify overlaps, followed by a multiple sequence alignment and generation of a consensus sequence. If the aim is to assemble a particular segment, instead of a whole genome or transcriptome, a target-specific assembly is a more sensible approach. GenSeed is a Perl program that implements a seed-driven recursive assembly consisting of cycles comprising a similarity search, read selection and assembly. The iterative process results in a progressive extension of the original seed sequence. GenSeed was tested and validated on many applications, including the reconstruction of nuclear genes or segments, full-length transcripts, and extrachromosomal genomes. The robustness of the method was confirmed through the use of a variety of DNA and protein seeds, including short sequences derived from SAGE and proteome projects.

Steps Ahead in the Few-Group CRoss-Section Library Generation at the Pin Level

There exists an interest in performing pin-by-pin calculations coupled with thermal hydraulics so as to improve the accuracy of nuclear reactor analysis. In the framework of the EU NURISP project, INRNE and UPM have generated an experimental version of a few group diffusion cross sections library with discontinuity factors intended for VVER analysis at the pin level with the COBAYA3 code. The transport code APOLLO2 was used to perform the branching calculations. As a first proof of principle the library was created for fresh fuel and covers almost the full parameter space of steady state and transient conditions. The main objective is to test the calculation schemes and post-processing procedures, including multi-pin branching calculations. Two library options are being studied: one based on linear table interpolation and another one using a functional fitting of the cross sections. The libraries generated with APOLLO2 have been tested with the pin-by-pin diffusion model in COBAYA3 including discontinuity factors; first comparing 2D results against the APOLLO2 reference solutions and afterwards using the libraries to compute a 3D assembly problem coupled with a simplified thermal-hydraulic model.

Prediction of peptide and protein propensity for amyloid formation

This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

A Study of Ordered Gene Problems Featuring DNA Error Correction and DNA Fragment Assembly with a Variety of Heuristics, Genetic Algorithm Variations, and Dynamic Representations

Ordered gene problems are a very common classification of optimization problems. Because of their popularity countless algorithms have been developed in an attempt to find high quality solutions to the problems. It is also common to see many different types of problems reduced to ordered gene style problems as there are many popular heuristics and metaheuristics for them due to their popularity. Multiple ordered gene problems are studied, namely, the travelling salesman problem, bin packing problem, and graph colouring problem. In addition, two bioinformatics problems not traditionally seen as ordered gene problems are studied: DNA error correction and DNA fragment assembly. These problems are studied with multiple variations and combinations of heuristics and metaheuristics with two distinct types or representations. The majority of the algorithms are built around the Recentering- Restarting Genetic Algorithm. The algorithm variations were successful on all problems studied, and particularly for the two bioinformatics problems. For DNA Error Correction multiple cases were found with 100% of the codes being corrected. The algorithm variations were also able to beat all other state-of-the-art DNA Fragment Assemblers on 13 out of 16 benchmark problem instances.

Core-Shell Assisted Bimetallic Assembly of Pt and Ru Nanoparticles by DNA Hybridization

We have discovered that the current protocols to assemble Au nanoparticles based on DNA hybridization do not work well with the small metal nanoparticles (e.g. 5 nm Au, 3.6 nm Pt and 3.2 nm Ru particles). Further investigations revealed the presence of strong interaction between the oligonucleotide backbone and the surface of the small metal nanoparticles. The oligonucleotides in this case are recumbent on the particle surface and are therefore not optimally oriented for hybridization. The nonspecific adsorption of oligonucleotides on small metal nanoparticles must be overcome before DNA hybridization can be accepted as a general assembly method. Two methods have been suggested as possible solutions to this problem. One is based on the use of stabilizer molecules which compete with the oligonucleotides for adsorption on the metal nanoparticle surface. Unfortunately, the reported success of this approach in small Au nanoparticles (using K₂BSPP) and Au films (using 6-mercapto-1-hexanol) could not be extended to the assembly of Pt and Ru nanoparticles by DNA hybridization. The second approach is to simply use larger metal particles. Indeed most reports on the DNA hybridization induced assembly of Au nanoparticles have made use of relatively large particles (>10 nm), hinting at a weaker non-specific interaction between the oligonucleotides and large Au nanoparticles. However, most current methods of nanoparticle synthesis are optimized to produce metal nanoparticles only within a narrow size range. We find that core-shell nanoparticles formed by the seeded growth method may be used to artificially enlarge the size of the metal particles to reduce the nonspecific binding of oligonucleotides. We demonstrate herein a core-shell assisted growth method to assemble Pt and Ru nanoparticles by DNA hybridization. This method involves firstly synthesizing approximately 16 nm core-shell Ag-Pt and 21 nm core-shell Au-Ru nanoparticles from 9.6 nm Ag seeds and 17.2 nm Au seeds respectively by the seed-mediated growth method. The core-shell nanoparticles were then functionalized by complementary thiolated oligonucleotides followed by aging in 0.2 M PBS buffer for 6 hours. The DNA hybridization induced bimetallic assembly of Pt and Ru nanoparticles could then be carried out in 0.3 M PBS buffer for 10 hours.

Icosahedral DNA Nanocapsules by Modular Assembly

The construction of well-defined 3D architectures is one of the greatest challenges of self-assembly. Nanofabrication through molecular self-assembly has resulted in the formation of DNA polyhedra with the connectivities of cubes,[1] tetrahedra,[2,3] octahedra,[4, 5] dodecahedra,[3] and buckminsterfullerene.[ 3] DNA polyhedra could also function as nanocapsules and thereby enable the targeted delivery of entities encapsulated from solution. Key to realizing this envisaged function is the construction of complex polyhedra that maximize encapsulation volumes while preserving small. pore size.