Traversing a Set of Points with a Minimum Number of Turns

Given a finite set of points S in ℝ ^d , consider visiting the points in S with a polygonal path which makes a minimum number of turns, or equivalently, has the minimum number of segments (links). We call this minimization problem the minimum link spanning path problem. This natural problem has appeared several times in the literature under different variants. The simplest one is that in which the allowed paths are axis-aligned. Let L(S) be the minimum number of links of an axis-aligned path for S, and let G _n ^d be an n×…×n grid in ℤ ^d . Kranakis et al. (Ars Comb. 38:177–192, 1994) showed that L(G _n ²)=2n−1 and and conjectured that, for all d≥3, We prove the conjecture for d=3 by showing the lower bound for L(G _n ³). For d=4, we prove that For general d, we give new estimates on L(G _n ^d ) that are very close to the conjectured value. The new lower bound of improves previous result by Collins and Moret (Inf. Process. Lett. 68:317–319, 1998), while the new upper bound of differs from the conjectured value only in the lower order terms. For arbitrary point sets, we include an exact bound on the minimum number of links needed in an axis-aligned path traversing any planar n-point set. We obtain similar tight estimates (within 1) in any number of dimensions d. For the general problem of traversing an arbitrary set of points in ℝ ^d with an axis-aligned spanning path having a minimum number of links, we present a constant ratio (depending on the dimension d) approximation algorithm. Work by A. Dumitrescu was partially supported by NSF CAREER grant CCF-0444188. Work by F. Hurtado was partially supported by projects MECMTM2006-01267 and Gen. Cat. 2005SGR00692. Work by P. Valtr was partially supported by the project 1M0545 of the Ministry of Education of the Czech Republic.     

Braces and symmetric groups with special conditions

We study left braces satisfying special conditions, or identities. We are particularly interested in the impact of conditions like Raut and lri on the properties of the left brace and its associated solution of the Yang–Baxter equation (YBE). We show that the solution $(G,r_G)$ of the YBE associated to the structure group $G=G(X,r)$ (with the natural structure of a left brace) of a nontrivial solution $(X,r)$ of the YBE has multipermutation level 2 if and only if G satisfies lri. It is known that every (left) brace with lri satisfies condition Raut. We prove that for a graded Jacobson radical ring with no elements of additive order two the conditions lri and Raut are equivalent. We construct a finite two-sided brace with condition Raut which does not satisfy lri. We show that a finitely generated two-sided brace which satisfies lri has a finite multipermutation level which is bounded by the number of its generators.     

The Gelfand-Kirillov dimension of quadratic algebras satisfying the cyclic condition

We consider algebras over a field presented by generators and subject to square-free relations of the form with every monomial , appearing in one of the relations. It is shown that for 1$"> the Gelfand-Kirillov dimension of such an algebra is at least two if the algebra satisfies the so-called cyclic condition. It is known that this dimension is an integer not exceeding . For , we construct a family of examples of Gelfand-Kirillov dimension two. We prove that an algebra with the cyclic condition with generators has Gelfand-Kirillov dimension if and only if it is of -type, and this occurs if and only if the multiplicative submonoid generated by is cancellative.

     

Distant collaboration in drug discovery: the LINK3D project

The work describes the development of novel software supporting synchronous distant collaboration between scientists involved in drug discovery and development projects. The program allows to visualize and share data as well as to interact in real time using standard intranets and Internet resources. Direct visualization of 2D and 3D molecular structures is supported and original tools for facilitating remote discussion have been integrated. The software is multiplatform (MS-Windows, SGI-IRIX, Linux), allowing for a seamless integration of heterogeneous working environments. The project aims to support collaboration both within and between academic and industrial institutions. Since confidentiality is very important in some scenarios, special attention has been paid to security aspects. The article presents the research carried out to gather the requirements of collaborative software in the field of drug discovery and development and describes the features of the first fully functional prototype obtained. Real-world testing activities carried out on this prototype in order to guarantee its adequacy in diverse environments are also described and discussed.In addition to the mentioned institutions the LINK3D Consortium is constituted by     

Prefetching and caching strategies for remote and interactive browsing of JPEG2000 images.

This paper considers the issues of scheduling and caching JPEG2000 data in client/server interactive browsing applications, under memory and channel bandwidth constraints. It analyzes how the conveyed data have to be selected at the server and managed within the client cache so as to maximize the reactivity of the browsing application. Formally, to render the dynamic nature of the browsing session, we assume the existence of a reaction model that defines when the user launches a novel command as a function of the image quality displayed at the client. As a main outcome, our work demonstrates that, due to the latency inherent to client/server exchanges, a priori expectation about future navigation commands may help to improve the overall reactivity of the system. In our study, the browsing session is defined by the evolution of a rectangular window of interest (WoI) along the time. At any given time, the WoI defines the position and the resolution of the image data to display at the client. The expectation about future navigation commands is then formalized based on a stochastic navigation model, which defines the probability that a given WoI is requested next, knowing previous WoI requests. Based on that knowledge, several scheduling scenarios are considered. The first scenario is conventional and transmits all the data corresponding to the current WoI before prefetching the most promising data outside the current WoI. Alternative scenarios are then proposed to anticipate prefetching, by scheduling data expected to be requested in the future before all the current WoI data have been sent out. Our results demonstrate that, for predictable navigation commands, anticipated prefetching improves the overall reactivity of the system by up to 30% compared to the conventional scheduling approach. They also reveal that an accurate knowledge of the reaction model is not required to get these significant improvements.     

3D-QSAR methods on the basis of ligand–receptor complexes. Application of COMBINE and GRID/GOLPE methodologies to a series of CYP1A2 ligands

Many heterocyclic amines (HCA) present in cooked food exert a genotoxic activity when they are metabolised (N-oxidated) by the human cytochrome P450 1A2 (CYP1A2h). In order to rationalize the observed differences in activity of this enzyme on a series of 12 HCA, 3D-QSAR methods were applied on the basis of models of HCA–CYP1A2h complexes. The CYP1A2h enzyme model has been previously reported and was built by homology modeling based on cytochrome P450 BM3. The complexes were automatically generated applying the AUTODOCK software and refined using AMBER. A COMBINE analysis on the complexes identified the most important enzyme–ligand interactions that account for the differences in activity within the series. A GRID/GOLPE analysis was then performed on just the ligands, in the conformations and orientations found in the modeled complexes. The results from both methods were concordant and confirmed the advantages of incorporating structural information from series of ligand–receptor complexes into 3D-QSAR methodologies.     

Automatic search for maximum similarity between molecular electrostatic potential distributions

Summary A new computer program has been developed to automatically obtain the relative position of two molecules in which the similarity between molecular electrostatic-potential distributions is greatest. These distributions are considered in a volume around the molecules, and the similarity is measured by the Spearman rank coefficient. The program has been tested using several pairs of molecules: water vs. water; phenylethylamine and phenylpropylamine vs. benzylamine; and methotrexate vs. dihydrofolic acid.     

The maximum condition on annihilators for polynomial rings

For each positive integer , we construct a commutative ring such that the polynomial ring satisfies the maximum condition on annihilators and does not. In particular, there exists a commutative Kerr ring such that is not Kerr. This answers in the negative a question of Faith's.