Hematopoietic gene promoters subjected to a group-combinatorial study of DNA samples: identification of a megakaryocytic selective DNA signature

Identification of common sub-sequences for a group of functionally related DNA sequences can shed light on the role of such elements in cell-specific gene expression. In the megakaryocytic lineage, no one single unique transcription factor was described as linage specific, raising the possibility that a cluster of gene promoter sequences presents a unique signature. Here, the megakaryocytic gene promoter group, which consists of both human and mouse 5' non-coding regions, served as a case study. A methodology for group-combinatorial search has been implemented as a customized software platform. It extracts the longest common sequences for a group of related DNA sequences and allows for single gaps of varying length, as well as double- and multiple-gap sequences. The results point to common DNA sequences in a group of genes that is selectively expressed in megakaryocytes, and which does not appear in a large group of control, random and specific sequences. This suggests a role for a combination of these sequences in cell-specific gene expression in the megakaryocytic lineage. The data also point to an intrinsic cross-species difference in the organization of 5' non-coding sequences within the mammalian genomes. This methodology may be used for the identification of regulatory sequences in other lineages.

On the Effectiveness of Genetic Search in Combinatorial Optimization

In this paper, we study the efficacy of genetic algorithms in the context of combinatorial optimization. In particular, we isolate the effects of cross-over, treated as the central component of genetic search. We show that for problems of nontrivial size and difficulty, the contribution of cross-over search is marginal, both synergistically when run in conjunction with mutation and selection, or when run with selection alone, the reference point being the search procedure consisting of just mutation and selection. The latter can be viewed as another manifestation of the Metropolis process. Considering the high computational cost of maintaining a population to facilitate cross-over search, its marginal benefit renders genetic search inferior to its singleton-population counterpart, the Metropolis process, and by extension, simulated annealing. This is further compounded by the fact that many problems arising in practice may inherently require a large number of state transitions for a near-optimal solution to be found, making genetic search infeasible given the high cost of computing a single iteration in the enlarged state-space.

Anisotropic Interpolation on Graphs: The Combinatorial Dirichlet Problem

The combinatorial Dirichlet problem is formulated, and an algorithm for solving it is presented. This provides an effective method for interpolating missing data on weighted graphs of arbitrary connectivity. Image processing examples are shown, and the relation to anistropic diffusion is discussed.

Latest development of the combinatorial model of nuclear level densities

The combinatorial model of nuclear level densities has now reached a level of accuracy comparable to that of the best global analytical expressions without suffering from the limits imposed by the statistical hypothesis on which the latter expressions rely. In particular, it provides, naturally, non-Gaussian spin distribution as well as non-equipartition of parities which are known to have an impact on cross section predictions at low energies [1, 2, 3]. Our previous global models developed in Refs. [1, 2] suffered from deficiencies, in particular in the way the collective effects - both vibrational and rotational - were treated. We have recently improved this treatment using simultaneously the single-particle levels and collective properties predicted by a newly derived Gogny interaction [4], therefore enabling a microscopic description of energy-dependent shell, pairing and deformation effects. In addition for deformed nuclei, the transition to sphericity is coherently taken into account on the basis of a temperature-dependent Hartree-Fock calculation which provides at each temperature the structure properties needed to build the level densities. This new method is described and shown to give promising results with respect to available experimental data.

Preface [Special Issue: International Symposium on Combinatorial Optimisation (CO2000)]

Preface [Special Issue containing a selection of papers presented at the International Symposium on Combinatorial Optimisation (CO2000) held at the University of Greenwich, London, from 12-14 July 2000.

Multilevel refinement for combinatorial optimisation problems

We consider the multilevel paradigm and its potential to aid the solution of combinatorial optimisation problems. The multilevel paradigm is a simple one, which involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found (sometimes for the original problem, sometimes the coarsest) and then iteratively refined at each level. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (most notably in the form of multigrid techniques). However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial optimisation problems. In this paper we address the issue of multilevel refinement for such problems and, with the aid of examples and results in graph partitioning, graph colouring and the travelling salesman problem, make a case for its use as a metaheuristic. The results provide compelling evidence that, although the multilevel framework cannot be considered as a panacea for combinatorial problems, it can provide an extremely useful addition to the combinatorial optimisation toolkit. We also give a possible explanation for the underlying process and extract some generic guidelines for its future use on other combinatorial problems.

Multilevel refinement for combinatorial optimisation: boosting metaheuristic performance

The multilevel paradigm as applied to combinatorial optimisation problems is a simple one, which at its most basic involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found, usually at the coarsest level, and then iteratively refined at each level, coarsest to finest, typically by using some kind of heuristic optimisation algorithm (either a problem-specific local search scheme or a metaheuristic). Solution extension (or projection) operators can transfer the solution from one level to another. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (for example multigrid techniques can be viewed as a prime example of the paradigm). Overview papers such as [] attest to its efficacy. However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial problems and in this chapter we discuss recent developments. In this chapter we survey the use of multilevel combinatorial techniques and consider their ability to boost the performance of (meta)heuristic optimisation algorithms.

The Use of Electrospray Mass Spectrometry to Determine Speciation in a Dynamic Combinatorial Library for Anion Recognition

The composition of a dynamic mixture of similar 2,2'-bipyridine complexes of iron(II) bearing either an amide (5-benzylamido-2,2'-bipyridine and 5-(2-methoxyethane)amido-2,2'-bipyridine) or an ester (2,2'-bipyridine-5-carboxylic acid benzylester and 2,2'-bipyridine-5-carboxylic acid 2-methoxyethane ester) side chain have been evaluated by electrospray mass spectroscopy in acetonitrile. The time taken for the complexes to come to equilibrium appears to be dependent on the counteranion, with chloride causing a rapid redistribution of two preformed heteroleptic complexes (of the order of 1 hour), whereas the time it takes in the presence of tetrafluoroborate salts is in excess of 24^^h. Similarly the final distribution of products is dependent on the anion present, with the presence of chloride, and to a lesser extent bromide, preferring three amide-functionalized ligands, and a slight preference for an appended benzyl over a methoxyethyl group. Furthermore, for the first time, this study shows that the distribution of a dynamic library of metal complexes monitored by ESI-MS can adapt following the introduction of a different anion, in this case tetrabutylammonium chloride to give the most favoured heteroleptic complex despite the increasing ionic strength of the solution. 

Characterisation of pavement profile heights using accelerometer readings and a combinatorial optimisation technique

Pavement surface profiles induce dynamic ride responses in vehicles which can potentially be used to classify road surface roughness. A novel method is proposed for the characterisation of pavement roughness through an analysis of vehicle accelerations. A combinatorial optimisation technique is applied to the determination of pavement profile heights based on measured accelerations at and above the vehicle axle. Such an approach, using low-cost inertial sensors, would provide an inexpensive alternative to the costly laser-based profile measurement vehicles. The concept is numerically validated using a half-car roll dynamic model to infer measurements of road profiles in both the left and right wheel paths.

Combinatorial Frequency Generation in Quasi-Periodic Stacks of Nonlinear Dielectric Layers

Three-wave mixing in quasi-periodic structures (QPSs) composed of nonlinear anisotropic dielectric layers, stacked in Fibonacci and Thue-Morse sequences, has been explored at illumination by a pair of pump waves with dissimilar frequencies and incidence angles. A new formulation of the nonlinear scattering problem has enabled the QPS analysis as a perturbed periodic structure with defects. The obtained solutions have revealed the effects of stack composition and constituent layer parameters, including losses, on the properties of combinatorial frequency generation (CFG). The CFG features illustrated by the simulation results are discussed. It is demonstrated that quasi-periodic stacks can achieve a higher efficiency of CFG than regular periodic multilayers.

Quasi-periodic stacks of semiconductor layers: Combinatorial frequency generation

The nonlinear scattering and combinatorial frequency generation by the quasi-periodic Fibonacci and Thue-Morse stacks of semiconductor layers have been investigated taking into account the nonlinear charge dynamics. It has been shown that the mixing processes in passive semiconductor structures are driven by the competitive effects of the collision of charges and resonance interactions of carriers with pump waves. The effects of the stack arrangements and constituent layer parameters on the efficiency of the combinatorial frequency generation are discussed.