A new algorithm and refined bounds for extended gcd computation

Extended gcd computation is interesting itself. It also plays a fundamental role in other calculations. We present a new algorithm for solving the extended gcd problem. This algorithm has a particularly simple description and is practical. It also provides refined bounds on the size of the multipliers obtained.

The Qu-Prolog unification algorithm: Formalisation and correctness

Qu-Prolog is an extension of Prolog which performs meta-level computations over object languages, such as predicate calculi and lambda-calculi, which have object-level variables, and quantifier or binding symbols creating local scopes for those variables. As in Prolog, the instantiable (meta-level) variables of Qu-Prolog range over object-level terms, and in addition other Qu-Prolog syntax denotes the various components of the object-level syntax, including object-level variables. Further, the meta-level operation of substitution into object-level terms is directly represented by appropriate Qu-Prolog syntax. Again as in Prolog, the driving mechanism in Qu-Prolog computation is a form of unification, but this is substantially more complex than for Prolog because of Qu-Prolog's greater generality, and especially because substitution operations are evaluated during unification. In this paper, the Qu-Prolog unification algorithm is specified, formalised and proved correct. Further, the analysis of the algorithm is carried out in a frame-work which straightforwardly allows the 'completeness' of the algorithm to be proved: though fully explicit answers to unification problems are not always provided, no information is lost in the unification process.

Regulation of CSF-1 receptor expression

Cells of the mononuclear phagocyte lineage possess receptors for macrophage colony-stimulating factor (CSF-1) encoded by the c-fms protooncogene and respond to CSF-1 with increased survival, growth, differentiation, and reversible changes in function. The c-fms gene is itself a macrophage differentiation marker. In whole mount analyses of mRNA expression in embryos, c-fms is expressed at very high levels on placental trophoblasts. It is detectable on individual cells in the yolk sac around 8.5 to 9 days postcoitus, appears on isolated cells in the head of the embryo around 9.5 dpc, and appears on numerous cells throughout the embryo by day 10.5. The extent of c-fms expression is much greater than for other macrophage-specific genes including lysozyme and a macrophage-specific protein tyrosine phosphatase. Our studies of the cis-acting elements of the c-fms promoter have indicated a key role for collaboration between the macrophage-specific transcription factor, Pu.1, which functions in determining the site of transcription initiation, and other members of the Ets transcription factor family. This is emerging as a common pattern in macrophage-specific promoters. We have shown that two PU box elements alone can function as a macrophage-specific promoter. The activity of both the artifical promoter and the c-fms promoter is activated synergistically by coexpression of Pu.1 and another Ets factor, c-Ets-2. A 3.5kb c-fms exon 2 promoter (but not the 300bp proximal promoter) is also active in a wide diversity of tumor cell lines. The interesting exception is the melanoma cell line K1735, in which the promoter is completely shut down and expression of c-fms causes growth arrest and cell death. The activity of the exon 2 promoter in these nonmacrophages is at least as serum responsive as the classic serum-responsive promoter of the c-fos gene. It is further inducible in nonmacrophages by coexpression of the c-fms product. Unlike other CSF-1/c-fms-responsive promoters, the c-fms promoter is not responsive to activated Ras even when c-Ets-2 is coexpressed. In most lines, production of full length c-fms is prevented by a downstream intronic terminator, but in Lewis lung carcinoma, read-through does occur, and expression of both c-fms and other macrophage-specific genes such as lysozyme and urokinase becomes detectable in conditions of serum deprivation. (C) 1997 Wiley-Liss, Inc.

High-breakdown linear discriminant analysis

The classification rules of linear discriminant analysis are defined by the true mean vectors and the common covariance matrix of the populations from which the data come. Because these true parameters are generally unknown, they are commonly estimated by the sample mean vector and covariance matrix of the data in a training sample randomly drawn from each population. However, these sample statistics are notoriously susceptible to contamination by outliers, a problem compounded by the fact that the outliers may be invisible to conventional diagnostics. High-breakdown estimation is a procedure designed to remove this cause for concern by producing estimates that are immune to serious distortion by a minority of outliers, regardless of their severity. In this article we motivate and develop a high-breakdown criterion for linear discriminant analysis and give an algorithm for its implementation. The procedure is intended to supplement rather than replace the usual sample-moment methodology of discriminant analysis either by providing indications that the dataset is not seriously affected by outliers (supporting the usual analysis) or by identifying apparently aberrant points and giving resistant estimators that are not affected by them.

Genes for albicidin biosynthesis and resistance span at least 69 kb in the genome of Xanthomonas albilineans

All Tn5 insertion mutants of Xanthomonas albilineans, the cause of leaf scald disease of sugar cane, which failed to produce albicidin antibiotics failed to cause chlorosis in inoculated sugar cane but- remained resistant to albicidin. Southern analysis revealed that mutants deficient in albicidin production carried the transposon on different chromosomal restriction fragments spanning at least: 50 kb in the X. albilineans genome, which is larger than any reported cluster of genes involved in the production of a bacterial phytotoxin. Albicidin-resistant cosmid clones from a Tox(-) Tn5 insertion mutant did not carry the transposon, and the subcloned albicidin resistance gene did not hybridize to any of the restriction fragments carrying Tn5 in the Tox(-) mutants, indicating that the albicidin biosynthesis and resistance genes are not closely linked in X. albilineans.

Analysis and implementation of a new constant acceleration subcycling algorithm

An algorithm for explicit integration of structural dynamics problems with multiple time steps is proposed that averages accelerations to obtain subcycle states at a nodal interface between regions integrated with different time steps. With integer time step ratios, the resulting subcycle updates at the interface sum to give the same effect as a central difference update over a major cycle. The algorithm is shown to have good accuracy, and stability properties in linear elastic analysis similar to those of constant velocity subcycling algorithms. The implementation of a generalised form of the algorithm with non-integer time step ratios is presented. (C) 1997 by John Wiley & Sons, Ltd.

Expression of activated mutants of the human interleukin-3/interleukin-5 granulocyte-macrophage colony-stimulating factor receptor common beta subunit in primary hematopoietic cells induces factor-independent proliferation and differentiation

To date, several activating mutations have been discovered in the common signal-transducing subunit (h beta c) of the receptors for human granulocyte-macrophage colony-stimulating factor, interleukin-3, and interleukin-5. Two of these, Fl Delta and 1374N, result in a 37 amino acid duplication and a single amino acid substitution in the extracellular domain of h beta c, respectively. A third, V449E, results in a single amino acid substitution in the transmembrane domain, Previous studies comparing the activity of these mutants in different hematopoietic cell lines imply that the transmembrane and extracellular mutations act by different mechanisms and suggest the requirement for cell type-specific molecules in signalling. To characterize the ability of these mutant hpc subunits to mediate growth and differentiation of primary cells and hence investigate their oncogenic potential, we have expressed all three mutants in primary murine hematopoietic cells using retroviral transduction. It is shown that, whereas expression of either extracellular hpc mutant confers factor-independent proliferation and differentiation on cells of the neutrophil and monocyte lineages only, expression of the transmembrane mutant does so on these lineages as well as the eosinophil, basophil, megakaryocyte, and erythroid lineages, Factor-independent myeloid precursors expressing the transmembrane mutant display extended proliferation in liquid culture and in some cases yielded immortalized cell lines. (C) 1997 by The American Society of Hematology.

The subcycled Newmark algorithm

The popular Newmark algorithm, used for implicit direct integration of structural dynamics, is extended by means of a nodal partition to permit use of different timesteps in different regions of a structural model. The algorithm developed has as a special case an explicit-explicit subcycling algorithm previously reported by Belytschko, Yen and Mullen. That algorithm has been shown, in the absence of damping or other energy dissipation, to exhibit instability over narrow timestep ranges that become narrower as the number of degrees of freedom increases, making them unlikely to be encountered in practice. The present algorithm avoids such instabilities in the case of a one to two timestep ratio (two subcycles), achieving unconditional stability in an exponential sense for a linear problem. However, with three or more subcycles, the trapezoidal rule exhibits stability that becomes conditional, falling towards that of the central difference method as the number of subcycles increases. Instabilities over narrow timestep ranges, that become narrower as the model size increases, also appear with three or more subcycles. However by moving the partition between timesteps one row of elements into the region suitable for integration with the larger timestep these the unstable timestep ranges become extremely narrow, even in simple systems with a few degrees of freedom. As well, accuracy is improved. Use of a version of the Newmark algorithm that dissipates high frequencies minimises or eliminates these narrow bands of instability. Viscous damping is also shown to remove these instabilities, at the expense of having more effect on the low frequency response.

Simulated-annealing-based genetic algorithm for modeling the optical constants of solids

We propose a simulated-annealing-based genetic algorithm for solving model parameter estimation problems. The algorithm incorporates advantages of both genetic algorithms and simulated annealing. Tests on computer-generated synthetic data that closely resemble optical constants of a metal were performed to compare the efficiency of plain genetic algorithms against the simulated-annealing-based genetic algorithms. These tests assess the ability of the algorithms to and the global minimum and the accuracy of values obtained for model parameters. Finally, the algorithm with the best performance is used to fit the model dielectric function to data for platinum and aluminum. (C) 1997 Optical Society of America.