Computational experience with a parallel algorithm for tetrangle inequality bound smoothing

Determining molecular structure from interatomic distances is an important and challenging problem. Given a molecule with n atoms, lower and upper bounds on interatomic distances can usually be obtained only for a small subset of the atom pairs, using NMR. Given the bounds so obtained on the distances between some of the atom pairs, it is often useful to compute tighter bounds on all the pairwise distances. This process is referred to as bound smoothing. The initial lower and upper bounds for the pairwise distances not measured are usually assumed to be 0 and ∞. One method for bound smoothing is to use the limits imposed by the triangle inequality. The distance bounds so obtained can often be tightened further by applying the tetrangle inequality—the limits imposed on the six pairwise distances among a set of four atoms (instead of three for the triangle inequalities). The tetrangle inequality is expressed by the Cayley—Menger determinants. For every quadruple of atoms, each pass of the tetrangle inequality bound smoothing procedure finds upper and lower limits on each of the six distances in the quadruple. Applying the tetrangle inequalities to each of the ( ₄ ⁿ ) quadruples requires O(n ⁴) time. Here, we propose a parallel algorithm for bound smoothing employing the tetrangle inequality. Each pass of our algorithm requires O(n ³ log n) time on a CREW PRAM (Concurrent Read Exclusive Write Parallel Random Access Machine) with processors. An implementation of this parallel algorithm on the Intel Paragon XP/S and its performance are also discussed.     

Cluster Analysis via Density Functions: Amelioration of a Lower Bound of the Parameter

This paper refers to an earlier investigation on Cluster Analysis procedures based on general empirical density functions, in which the number of classes is controled by a positive parameter λ: the number of clusters, m, increases as λ →∞. Since there is no functional relationship between m and λ, upper and lower bounds of the parameter are of interest (see KOPP, 1976a). We now give a better value for the lower bound of λ in the case of the multivariate normal distribution.     

Analytical bounding functions for diffusion problems with michaelis-menten kinetics

Pointwise upper and lower bounds for the solution of a class of nonlinear diffusion problems with Michaelis-Menten kinetics are presented. Simple analytical bounding curves are obtained and for an illustrative case the calculated values bound the recent numerical solution of P. Hiltmann and P. Lory, 1983.Bull. math. Biol. 45, 661–664.     

Sensitivity of vertebral compressive strength to endplate loading distribution

The sensitivity of vertebral body strength to the distribution of axial forces along the endplate has not been comprehensively evaluated. Using quantitative computed tomography-based finite element models of 13 vertebral bodies, an optimization analysis was performed to determine the endplate force distributions that minimized (lower bound) and maximized (upper bound) vertebral strength for a given set of externally applied axial compressive loads. Vertebral strength was also evaluated for three generic boundary conditions: uniform displacement, uniform force, and a nonuniform force distribution in which the interior of the endplate was loaded with a force that was 1.5 times greater than the periphery. Our results showed that the relative difference between the upper and lower bounds on vertebral strength was 14.2 +/- 7.0% (mean +/- SD). While there was a weak trend for the magnitude of the strength bounds to be inversely proportional to bone mineral density (R2 = 0.32, p = 0.02), both upper and lower bound vertebral strength measures were well predicted by the strength response under uniform displacement loading conditions (R2 = 0.91 and R2 = 0.99, respectively). All three generic boundary conditions resulted in vertebral strength values that were statistically indistinguishable from the loading condition that resulted in an upper bound on strength. The results of this study indicate that the uncertainty in strength arising from the unknown condition of the disc is dependent on the condition of the bone (whether it is osteoporotic or normal). Although bone mineral density is not a good predictor of strength sensitivity, vertebral strength under generic boundary conditions, i.e., uniform displacement or force, was strongly correlated with the relative magnitude of the strength bounds. Thus, explicit disc modeling may not be necessary.     

Protective Vaccine Efficacy when Vaccine Response is Random

Vaccine induced protection against infection is often random because of primary vaccine failures and variation in the immune systems of hosts. We introduce a concept of protective vaccine efficacy in terms of mean relative susceptibility of vaccinated individuals and derive both a lower and an upper bound for it. These bounds apply for all distributions of the vaccine response and can be estimated from data on the size of a major epidemic. Standard errors are given for estimates of the bounds. Bounds are also given for the vaccination coverage required to prevent epidemics and these are also estimable from data on the size of a major epidemic. The results are applied to data on an outbreak of mumps.     

Bounds on the learning capacity of some multi-layer networks

We obtain bounds for the capacity of some multi-layer networks of linear threshold units. In the case of a network having n inputs, a single layer of h hidden units and an output layer of s units, where all the weights in the network are variable and shn, the capacity m satisfies 2nmnt logt, where t=1=h/s. We consider in more detail the case where there is a single output that is a fixed boolean function of the hidden units. In this case our upper bound is of order nh logh but the argument which provided the lower bound of 2n no longer applies. However, by explicit computation in low dimensional cases we show that the capacity exceeds 2n but is substantially less than the upper bound. Finally, we describe a learning algorithm for multi-layer networks with a single output unit. This greatly outperforms back propagation at the task of learning random vectors and provides further empirical evidence that the lower bound of 2n can be exceeded.     

A model for the minimum cost configuration problem in flexible manufacturing systems

This paper presents a mathematical programming model to help select equipment for a flexible manufacturing system, i.e., the selection of the types and numbers of CNC machines, washing stations, load/unload stations, transportation vehicles, and pallets. The objective is to minimize equipment costs and work-in-process inventory cost, while fulfilling production requirements for an average period. Queueing aspects and part flow interactions are considered with the help of a Jacksonian-type closed queueing network model in order to evaluate the system's performance. Since the related decision problem of our model can be shown to be NP-complete, the proposed solution procedure is based on implicit enumeration. Four bounds are provided, two lower and two upper bounds. A tight lower bound is obtained by linearizing the model through the application of asymptotic bound analysis. Furthermore, asymptotic bound analysis allows the calculation of a lower bound for the number of pallets in the system. The first upper bound is given by the best feasible solution and the second is based on the anti-starshaped form of the throughput function.     

Critical Values of ‘Maximum Studentized Residual’ Statistics in Multiple Linear Regression

In multiple linear regression, test for the discordancy of a single outlier in the response variable is usually based on the ‘maximum studentized residual’ statistic. Exact critical values for the test statistic t are not available. Upper bounds for the critical values have been found by SRIKANTAN (1961), PRESCOTT (1975) and LUND (1975). In this note we show that all these upper bounds are algebraically equivalent.     

A quantitative model of cellular elasticity based on tensegrity

A tensegrity structure composed of six struts interconnected with 24 elastic cables is used as a quantitative model of the steady-state elastic response of cells, with the struts and cables representing microtubules and actin filaments, respectively. The model is stretched uniaxially and the Young's modulus (E0) is obtained from the initial slope of the stress versus strain curve of an equivalent continuum. It is found that E0 is directly proportional to the pre-existing tension in the cables (or compression in the struts) and inversely proportional to the cable (or strut) length square. This relationship is used to predict the upper and lower bounds of E0 of cells, assuming that the cable tension equals the yield force of actin (approximately 400 pN) for the upper bound, and that the strut compression equals the critical buckling force of microtubules for the lower bound. The cable (or strut) length is determined from the assumption that model dimensions match the diameter of probes used in standard mechanical tests on cells. Predicted values are compared to reported data for the Young's modulus of various cells. If the probe diameter is greater than or equal to 3 microns, these data are closer to the lower bound than to the upper bound. This, in turn, suggests that microtubules of the CSK carry initial compression that exceeds their critical buckling force (order of 10(0)-10(1) pN), but is much smaller than the yield force of actin. If the probe diameter is less than or equal to 2 microns, experimental data fall outside the region defined by the upper and lower bounds.     

Lower bounds on multiple sequence alignment using exact 3-way alignment

Background  

Multiple sequence alignment is fundamental. Exponential growth in computation time appears to be inevitable when an optimal alignment is required for many sequences. Exact costs of optimum alignments are therefore rarely computed. Consequently much effort has been invested in algorithms for alignment that are heuristic, or explore a restricted class of solutions. These give an upper bound on the alignment cost, but it is equally important to determine the quality of the solution obtained. In the absence of an optimal alignment with which to compare, lower bounds may be calculated to assess the quality of the alignment. As more effort is invested in improving upper bounds (alignment algorithms), it is therefore important to improve lower bounds as well. Although numerous cost metrics can be used to determine the quality of an alignment, many are based on sum-of-pairs (SP) measures and their generalizations.     

Upper and lower bounds from the maximum principle. Intracellular diffusion with Michaelis-Menten kinetics

Analytical bounding functions for diffusion problems with Michaelis-Menten kinetics were recently presented by Anderson and Arthurs, 1985 (Bull. math. Biol. 47, 145–153). Their methods, successful to some extent for a small range of parameters, has the disadvantage of providing a weak upper bound. The optimal approach for the use of one-line bounding kinetics is presented. The use of two-line bounding kinetics is also shown, in order to give, sufficient accuracy in those cases where the one-line approach does not provide satisfactory results. The bounding functions provide excellent upper and lower bounds on the true solution for the entire range of kinetic and transport parameters.     

Combinatorial complexity of pathway analysis in metabolic networks

Elementary flux mode analysis is a promising approach for a pathway-oriented perspective of metabolic networks. However, in larger networks it is hampered by the combinatorial explosion of possible routes. In this work we give some estimations on the combinatorial complexity including theoretical upper bounds for the number of elementary flux modes in a network of a given size. In a case study, we computed the elementary modes in the central metabolism of Escherichia coli while utilizing four different substrates. Interestingly, although the number of modes occurring in this complex network can exceed half a million, it is still far below the upper bound. Hence, to a certain extent, pathway analysis of central catabolism is feasible to assess network properties such as flexibility and functionality.     

Dielectric behavior of polyelectrolytes. III. The role of counterion interactions

The role of the Coulomb forces between the counterions on the surface of polyelectrolytes on the dielectric response is analyzed. An estimate of the maximum dielectric increment (as a function of the number of counterions) is found as a function of the molecular length. The minimum-energy configuration of the counterions on a cylinder is found to be a double helix, suggesting the fundamental importance of electrostatic interactions in determining structure. Solutions of the dynamical equations for a few counterions indicate that a single mode dominates the relaxation which is enhanced by the inter-ion repulsions. A lower bound is found for this mode based on analysis of the system response for short lengths. Sum rules for the rates and amplitudes of the dipolar correlation function are derived and lead to an upper bound for the rate of the dominant mode. These bounds approach one another for the parameters characteristic of restriction fragments of DNA. This permits a prediction of the magnitude and time scale of the dielectric response.     

A Note on Variance Bounds for an Inverse Binomial Estimator

BEST (1974) found the variance of the minimum variance unbiased estimator of the Bernoulli parameter with an inverse sample. Noting its intricacy MIKULSKI and SMITH (1976) found bounds on this variance. SATHE (1977) developed closer bounds on it. In this paper still closer upper bound on the variance is achieved using Jensen's inequality.     

Are moment bounds on the recombination fraction between a marker and a disease locus too good to be true? Allelic association mapping revisited for simple genetic diseases in the Finnish population.

In the past several years, allelic association has helped map a number of rare genetic diseases in the human genome. A commonly used upper bound on the recombination fraction between the disease gene and an associated marker is known to be biased downward, so there is the possibility that an investigator could be misled. This upper bound is based on a moment equation that can be derived within the context of a Poisson branching process, so its performance can be compared with a recently proposed likelihood bound. We show that the confidence level of the moment upper bound is much lower than expected, while the confidence level of the likelihood bound is in line with expectation. The effects of mutation at either the marker or disease locus on the upper bounds are also investigated. Results indicate that mutation is not an important force for typical mutation rates, unless the recombination fraction between the marker and disease locus is very small or the disease allele is very rare in the general population. Finally, the impact of sample size on the likelihood bound is investigated. The results are illustrated with data on 10 simple genetic diseased in the Finnish population.     

Theoretical limits on the threshold for the response of long cells to weak extremely low frequency electric fields due to ionic and molecular flux rectification.

Understanding exposure thresholds for the response of biological systems to extremely low frequency (ELF) electric and magnetic fields is a fundamental problem of long-standing interest. We consider a two-state model for voltage-gated channels in the membrane of an isolated elongated cell (Lcell = 1 mm; rcell = 25 micron) and use a previously described process of ionic and molecular flux rectification to set lower bounds for a threshold exposure. A key assumption is that it is the ability of weak physical fields to alter biochemistry that is limiting, not the ability of a small number of molecules to alter biological systems. Moreover, molecular shot noise, not thermal voltage noise, is the basis of threshold estimates. Models with and without stochastic resonance are used, with a long exposure time, texp = 10(4) s. We also determined the dependence of the threshold on the basal transport rate. By considering both spherical and elongated cells, we find that the lowest bound for the threshold is Emin approximately 9 x 10(-3) V m-1 (9 x 10(-5) V cm-1). Using a conservative value for the loop radius rloop = 0.3 m for induced current, the corresponding lower bound in the human body for a magnetic field exposure is Bmin approximately 6 x 10(-4) T (6 G). Unless large, organized, and electrically amplifying multicellular systems such as the ampullae of Lorenzini of elasmobranch fish are involved, these results strongly suggest that the biophysical mechanism of voltage-gated macromolecules in the membranes of cells can be ruled out as a basis of possible effects of weak ELF electric and magnetic fields in humans.     

On the probability of reaching a threshold in a stochastic mammillary system

The multivariate distribution over time of a particular stochastic mammillary compartmental model is obtained for any point in time. The maximum expectation of the peripheral compartments is then derived and used to determine lower bounds on the probability that the maximum of the peripheral compartments reaches any arbitrary threshold level. A bound on the probability is illustrated by an example and some of its implications are explored.     

Retinal and cortical nonlinearities combine to produce masking in V1 responses to plaids

The visual response of a cell in the primary visual cortex (V1) to a drifting grating stimulus at the cell’s preferred orientation decreases when a second, perpendicular, grating is superimposed. This effect is called masking. To understand the nonlinear masking effect, we model the response of Macaque V1 simple cells in layer 4Cα to input from magnocellular Lateral Geniculate Nucleus (LGN) cells. The cortical model network is a coarse-grained reduction of an integrate-and-fire network with excitation from LGN input and inhibition from other cortical neurons. The input is modeled as a sum of LGN cell responses. Each LGN cell is modeled as the convolution of a spatio-temporal filter with the visual stimulus, normalized by a retinal contrast gain control, and followed by rectification representing the LGN spike threshold. In our model, the experimentally observed masking arises at the level of LGN input to the cortex. The cortical network effectively induces a dynamic threshold that forces the test grating to have high contrast before it can overcome the masking provided by the perpendicular grating. The subcortical nonlinearities and the cortical network together account for the masking effect. Melinda Koelling is formerly from Center for Neural Science and Courant Institute, New York University.     

Automatic control for fed-batch culture of single cell protein

Candida utilis was cultivated in a 5-liter jar fermentor using ethanol as sole carbon source. Control of ethanol in the cultivation broth was performed by using an ethanol vapor monitoring instrument and an oxygen electrode coupled with two control circuits. By setting upper and lower bounds according to the predetermined conditions, a signal from a gas monitoring sensor switched the lower or higher bound relay governing the actuating or switch-off of the motor; this maintained a proper concentration of ethanol in the cultivation of ethanol in the system. The growth of cells was found to be satisfactory. Cell concentration reached 64 g/liter during a 20-hr cultivation. As the results of comparative experiments, the control mode using the gas monitoring instrument was found to be superior to that using dissolved oxygen as a controlling signal, especially at high cell concentration.     

Postoperative cataract cases among atomic bomb survivors: radiation dose response and threshold

Recent evidence argues against a high threshold dose for vision-impairing radiation-induced cataractogenesis. We conducted logistic regression analysis to estimate the dose response and used a likelihood profile procedure to determine the best-fitting threshold model among 3761 A-bomb survivors who underwent medical examinations during 2000-2002 for whom radiation dose estimates were available, including 479 postoperative cataract cases. The analyses indicated a statistically significant dose-response increase in the prevalence of postoperative cataracts [odds ratio (OR), 1.39; 95% confidence interval (CI), 1.24-1.55] at 1 Gy, with no indication of upward curvature in the dose response. The dose response was suggestive when the restricted dose range of 0 to 1 Gy was examined. A nonsignificant dose threshold of 0.1 Gy (95% CI, <0-0.8) was found. The prevalence of postoperative cataracts in A-bomb survivors increased significantly with A-bomb radiation dose. The estimate (0.1 Gy) and upper bound (0.8 Gy) of the dose threshold for operative cataract prevalence was much lower than the threshold of 2-5 Gy usually assumed by the radiation protection community and was statistically compatible with no threshold at all.