Refolding of β-galactosidase: microfluidic device for reagent metering and mixing and quantification of refolding yield

We have developed a device that uses microfluidic valves and pumps to meter reagents for subsequent mixing with application to refolding of the protein β-galactosidase. The microfluidic approach offers the potential advantages of automation, cost-effectiveness, compatibility with optical detection, and reduction in sample volumes as opposed to conventional techniques of hand-pipetting or using robotic systems. The device is a multi-layered poly(dimethylsiloxane) on glass device with automated controls for reagent aliquoting and mixing. Refolding experiments have been performed off-chip using existing protocols on the protein β-galactosidase and the refolding yield has been quantified on-chip using fluorescein di-β-d-galactopyranoside, a caged-fluorescent molecule. This work provides the potential to reduce the cost of drug discovery and realization of protein pharmaceuticals.     

Modeling and optimization of a multi-enzyme electrokinetically driven multiplexed microchip for simultaneous detection of sugars

A model-based methodology was developed to optimize microfluidic chips for the simultaneous enzymatic quantification of sucrose, d-glucose and d-fructose in a single microfluidic channel with an integrated optical detection system. The assays were based on measuring the change in concentration of the reaction product NADH, which is stoichiometrically related to the concentration of those components via cascade of specific enzymatic reactions. A reduced order mathematical model that combines species transport, enzyme reaction, and electrokinetic bulk flow was developed to describe the operation of the microfluidic device. Using this model, the device was optimized to minimize sensor response time and maximize signal output by manipulating the process conditions such as sample and reagent volume and flow rate. According to this simulation study, all sugars were quantified within 2.5 min in the optimized microchip. A parallel implementation of the assays can further improve the throughput. In addition, the amount of consumed reagents was drastically reduced compared to microplate format assays. The methodology is generic and can easily be adapted to other enzymatic microfluidic chips.     

Construction and characterisation of a modular microfluidic system: coupling magnetic capture and electrochemical detection

This work presents the fabrication and characterisation of a versatile lab-on-a-chip system that combines magnetic capture and electrochemical detection. The system comprises a silicon chip featuring a series of microband electrodes, a PDMS gasket that incorporates the microfluidic channels, and a polycarbonate base where permanent magnets are hosted; these parts are designed to fit so that wire bonding and encapsulation are avoided. This system can perform bioassays over the surface of magnetic beads and uses only 50 μL of bead suspension per assay. Following detection, captured beads are released simply by sliding a thin iron plate between the magnets and the chip. Particles are captured upstream from the detector and we demonstrate how to take further advantage of the system fluidics to determine enzyme activities or concentrations, as flow velocity can be adjusted to the rate of the reactions under study. We used magnetic particles containing β-galactosidase and monitored the enzyme activity amperometrically by the oxidation of 4-aminophenol, enzymatically produced from 4-aminophenyl-β-d-galactopyranoside. The system is able to detect the presence of enzyme down to approximately 50 ng mL⁻¹.     

A Note on Exact Algorithms for Vertex Ordering Problems on Graphs

In this note, we give a proof that several vertex ordering problems can be solved in O ^∗(2 ⁿ ) time and O ^∗(2 ⁿ ) space, or in O ^∗(4 ⁿ ) time and polynomial space. The algorithms generalize algorithms for the Travelling Salesman Problem by Held and Karp (J. Soc. Ind. Appl. Math. 10:196–210, 1962) and Gurevich and Shelah (SIAM J. Comput. 16:486–502, 1987). We survey a number of vertex ordering problems to which the results apply.     

Graphical scenarios for specifying temporal properties: an automated approach

Temporal logics are commonly used for reasoning about concurrent systems. Model checkers and other finite-state verification techniques allow for automated checking of system model compliance to given temporal properties. These properties are typically specified as linear-time formulae in temporal logics. Unfortunately, the level of inherent sophistication required by these formalisms too often represents an impediment to move these techniques from “research theory” to “industry practice”. The objective of this work is to facilitate the nontrivial and error prone task of specifying, correctly and without expertise in temporal logic, temporal properties. In order to understand the basis of a simple but expressive formalism for specifying temporal properties we critically analyze commonly used in practice visual notations. Then we present a scenario-based visual language called Property Sequence Chart (PSC) that, in our opinion, fixes the highlighted lacks of these notations by extending a subset of UML 2.0 Interaction Sequence Diagrams. We also provide PSC with both denotational and operational semantics. The operational semantics is obtained via translation into Büchi automata and the translation algorithm is implemented as a plugin of our Charmy tool. Expressiveness of PSC has been validated with respect to well known property specification patterns. Preliminary results appeared in (Autili et al. 2006a).     

The Complexity of Counting Eulerian Tours in?4-regular Graphs

We investigate the complexity of counting Eulerian tours (#ET) and its variations from two perspectives—the complexity of exact counting and the complexity w.r.t. approximation-preserving reductions (AP-reductions, Dyer et al., Algorithmica 38(3):471–500, 2004). We prove that #ET is #P-complete even for planar 4-regular graphs.     

On body shapes providing maximum depth of penetration

The problem of maximization of the depth of penetration of rigid impactor into semi-infinite solid media (concrete shield) is investigated analytically and numerically using two-stage model and experimental data of Forrestal and Tzou (Int J Solids Struct 34(31–32):4127–4146, 1997). The shape of the axisymmetric rigid impactor has been taken as an unknown design variable. To solve the formulated optimization problem for nonadditive functional, we expressed the depth of penetration (DOP) under some isoperimetric constraints. We apply approaches based on analytical and qualitative variational methods and numerical optimization algorithm of global search. Basic attention for considered optimization problem was given to constraints on the mass of penetrated bodies, expressed by the volume in the case of penetrated solid body and by the surface area in the case of penetrated thin-walled rigid shell. As a result of performed investigation, based on two-term and three-term two stage models proposed by Forrestal et al. (Int J Impact Eng 15(4):396–405, 1994), Forrestal and Tzou (Int J Solids Struct 34(31–32):4127–4146, 1997) and effectively developed by Ben-Dor et al. (Comp Struct 56:243–248, 2002, Comput Struct 81(1):9–14, 2003a, Int J Solids Struct 40(17):4487–4500, 2003b, Mech Des Struct Mach 34(2): 139–156, 2006), we found analytical and numerical solutions and analyzed singularities of optimal forms.     

Absolute approximation ratios for packing rectangles into bins

We consider the problem of packing rectangles into bins that are unit squares, where the goal is to minimize the number of bins used. All rectangles have to be packed non-overlapping and orthogonal, i.e., axis-parallel. We present an algorithm with an absolute worst-case ratio of 2 for the case where the rectangles can be rotated by 90 degrees. This is optimal provided P 1 NP\mathcal{P}\not=\mathcal{NP} . For the case where rotation is not allowed, we prove an approximation ratio of 3 for the algorithm Hybrid First Fit which was introduced by Chung et al. (SIAM J. Algebr. Discrete Methods 3(1):66–76, 1982) and whose running time is slightly better than the running time of Zhang’s previously known 3-approximation algorithm (Zhang in Oper. Res. Lett. 33(2):121–126, 2005).     

Finding Total Unimodularity in Optimization Problems Solved by Linear Programs

A popular approach in combinatorial optimization is to model problems as integer linear programs. Ideally, the relaxed linear program would have only integer solutions, which happens for instance when the constraint matrix is totally unimodular. Still, sometimes it is possible to build an integer solution with the same cost from the fractional solution. Examples are two scheduling problems (Baptiste and Schieber, J. Sched. 6(4):395–404, 2003; Brucker and Kravchenko, J. Sched. 11(4):229–237, 2008) and the single disk prefetching/caching problem (Albers et al., J. ACM 47:969–986, 2000). We show that problems such as the three previously mentioned can be separated into two subproblems: (1) finding an optimal feasible set of slots, and (2) assigning the jobs or pages to the slots. It is straigthforward to show that the latter can be solved greedily. We are able to solve the former with a totally unimodular linear program, from which we obtain simple combinatorial algorithms with improved worst case running time.     

Topology optimization of 2D continua for minimum compliance using parallel computing

Topology optimization is often used in the conceptual design stage as a preprocessing tool to obtain overall material distribution in the solution domain. The resulting topology is then used as an initial guess for shape optimization. It is always desirable to use fine computational grids to obtain high-resolution layouts that minimize the need for shape optimization and postprocessing (Bendsoe and Sigmund, Topology optimization theory, methods and applications. Springer, Berlin Heidelberg New York 2003), but this approach results in high computation cost and is prohibitive for large structures. In the present work, parallel computing in combination with domain decomposition is proposed to reduce the computation time of such problems. The power law approach is used as the material distribution method, and an optimality criteria-based optimizer is used for locating the optimum solution [Sigmund (2001)21:120–127; Rozvany and Olhoff, Topology optimization of structures and composites continua. Kluwer, Norwell 2000]. The equilibrium equations are solved using a preconditioned conjugate gradient algorithm. These calculations have been done using a master–slave programming paradigm on a coarse-grain, multiple instruction multiple data, shared-memory architecture. In this study, by avoiding the assembly of the global stiffness matrix, the memory requirement and computation time has been reduced. The results of the current study show that the parallel computing technique is a valuable tool for solving computationally intensive topology optimization problems.