Approximate algorithms for credal networks with binary variables

This paper presents a family of algorithms for approximate inference in credal networks (that is, models based on directed acyclic graphs and set-valued probabilities) that contain only binary variables. Such networks can represent incomplete or vague beliefs, lack of data, and disagreements among experts; they can also encode models based on belief functions and possibilistic measures. All algorithms for approximate inference in this paper rely on exact inferences in credal networks based on polytrees with binary variables, as these inferences have polynomial complexity. We are inspired by approximate algorithms for Bayesian networks; thus the Loopy 2U algorithm resembles Loopy Belief Propagation, while the Iterated Partial Evaluation and Structured Variational 2U algorithms are, respectively, based on Localized Partial Evaluation and variational techniques. (C) 2007 Elsevier Inc. All rights reserved.

Some heuristic algorithms for total tardiness minimization in a flowshop with blocking

The flowshop scheduling problem with blocking in-process is addressed in this paper. In this environment, there are no buffers between successive machines: therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Heuristic approaches are proposed to minimize the total tardiness criterion. A constructive heuristic that explores specific characteristics of the problem is presented. Moreover, a GRASP-based heuristic is proposed and Coupled with a path relinking strategy to search for better outcomes. Computational tests are presented and the comparisons made with an adaptation of the NEH algorithm and with a branch-and-bound algorithm indicate that the new approaches are promising. (c) 2007 Elsevier Ltd. All rights reserved.

Evaluation of algorithms used to order markers on genetic maps

When building genetic maps, it is necessary to choose from several marker ordering algorithms and criteria, and the choice is not always simple. In this study, we evaluate the efficiency of algorithms try (TRY), seriation (SER), rapid chain delineation (RCD), recombination counting and ordering (RECORD) and unidirectional growth (UG), as well as the criteria PARF (product of adjacent recombination fractions), SARF (sum of adjacent recombination fractions), SALOD (sum of adjacent LOD scores) and LHMC (likelihood through hidden Markov chains), used with the RIPPLE algorithm for error verification, in the construction of genetic linkage maps. A linkage map of a hypothetical diploid and monoecious plant species was simulated containing one linkage group and 21 markers with fixed distance of 3 cM between them. In all, 700 F(2) populations were randomly simulated with and 400 individuals with different combinations of dominant and co-dominant markers, as well as 10 and 20% of missing data. The simulations showed that, in the presence of co-dominant markers only, any combination of algorithm and criteria may be used, even for a reduced population size. In the case of a smaller proportion of dominant markers, any of the algorithms and criteria (except SALOD) investigated may be used. In the presence of high proportions of dominant markers and smaller samples (around 100), the probability of repulsion linkage increases between them and, in this case, use of the algorithms TRY and SER associated to RIPPLE with criterion LHMC would provide better results. Heredity (2009) 103, 494-502; doi:10.1038/hdy.2009.96; published online 29 July 2009

Malnourished mice display an impaired hematologic response to granulocyte colony-stimulating factor administration

The aim of this Study was to determine if protein-energy malnutrition Could affect the hematologic response to granulocyte colony-stimulating factor (G-CSF). Swiss mice were fled a low-protein diet containing 4% protein, whereas control mice were fed a 20% protein-containing diet. After the malnourished group lost 20% of their original body weight, the mice were subdivided in 2 treatment groups, and hematopoietic parameters were studied. Mice were injected with either 8 mu g/kg per day of G-CSF or saline twice daily for 4 days. Malnourished mice developed anemia with reticulopenia and leukopenia with depletion of granulocytes and lymphocytes. Both malnourished and control mice treated with G-CSF showed a significant increase in neutrophils; however, in the control group, this increase was more pronounced compared to the malnourished group (4.5-fold and 3.4-fold, respectively). Granulocyte colony-stimulating factor administration increased bone marrow blastic (P < .001) and granulocytic (P < .01) compartments in the controls bill had no significant effect oil these hematopoietic compartments in the Malnourished animals (P = .08 and P = .62, respectively). We report that malnourished mice display an impaired response to G-CSF, which contributes to the decreased production of leukocytes in protein-energy malnutrition. (C) 2008 Elsevier Inc. All rights reserved.

Algorithms for sequence analysis via mutagenesis

Despite many successes of conventional DNA sequencing methods, some DNAs remain difficult or impossible to sequence. Unsequenceable regions occur in the genomes of many biologically important organisms, including the human genome. Such regions range in length from tens to millions of bases, and may contain valuable information such as the sequences of important genes. The authors have recently developed a technique that renders a wide range of problematic DNAs amenable to sequencing. The technique is known as sequence analysis via mutagenesis (SAM). This paper presents a number of algorithms for analysing and interpreting data generated by this technique.

Comparison of BR and QR Eigenvalue Algorithms for Power System Small Signal Stability Analysis

The BR algorithm is a novel and efficient method to find all eigenvalues of upper Hessenberg matrices and has never been applied to eigenanalysis for power system small signal stability. This paper analyzes differences between the BR and the QR algorithms with performance comparison in terms of CPU time based on stopping criteria and storage requirement. The BR algorithm utilizes accelerating strategies to improve its performance when computing eigenvalues of narrowly banded, nearly tridiagonal upper Hessenberg matrices. These strategies significantly reduce the computation time at a reasonable level of precision. Compared with the QR algorithm, the BR algorithm requires fewer iteration steps and less storage space without depriving of appropriate precision in solving eigenvalue problems of large-scale power systems. Numerical examples demonstrate the efficiency of the BR algorithm in pursuing eigenanalysis tasks of 39-, 68-, 115-, 300-, and 600-bus systems. Experiment results suggest that the BR algorithm is a more efficient algorithm for large-scale power system small signal stability eigenanalysis.

A study of the stability of subcycling algorithms in structural dynamics

Algorithms for explicit integration of structural dynamics problems with multiple time steps (subcycling) are investigated. Only one such algorithm, due to Smolinski and Sleith has proved to be stable in a classical sense. A simplified version of this algorithm that retains its stability is presented. However, as with the original version, it can be shown to sacrifice accuracy to achieve stability. Another algorithm in use is shown to be only statistically stable, in that a probability of stability can be assigned if appropriate time step limits are observed. This probability improves rapidly with the number of degrees of freedom in a finite element model. The stability problems are shown to be a property of the central difference method itself, which is modified to give the subcycling algorithm. A related problem is shown to arise when a constraint equation in time is introduced into a time-continuous space-time finite element model. (C) 1998 Elsevier Science S.A.

Extended GCD and Hermite normal form algorithms via lattice basis reduction

Extended gcd calculation has a long history and plays an important role in computational number theory and linear algebra. Recent results have shown that finding optimal multipliers in extended gcd calculations is difficult. We present an algorithm which uses lattice basis reduction to produce small integer multipliers x(1), ..., x(m) for the equation s = gcd (s(1), ..., s(m)) = x(1)s(1) + ... + x(m)s(m), where s1, ... , s(m) are given integers. The method generalises to produce small unimodular transformation matrices for computing the Hermite normal form of an integer matrix.

Saturation mutagenesis of the beta subunit of the human granulocyte-macrophage colony-stimulating factor receptor shows clustering of constitutive mutations, activation of ERK MAP kinase and STAT pathways, and differential beta subunit tyrosine phosphoryl

The high-affinity receptors for human granulocyte-macrophage colony-stimulating factor (GM-CSF), interleukin-1 (IL-3), and IL-5 are heterodimeric complexes consisting of cytokine-specific alpha subunits and a common signal-transducing beta subunit (h beta c). We have previously demonstrated the oncogenic potential of this group of receptors by identifying constitutively activating point mutations in the extracellular and transmembrane domains of h beta c. We report here a comprehensive screen of the entire h beta c molecule that has led to the identification of additional constitutive point mutations by virtue of their ability to confer factor independence on murine FDC-P1 cells. These mutations were clustered exclusively in a central region of h beta c that encompasses the extracellular membrane-proximal domain, transmembrane domain, and membrane-proximal region of the cytoplasmic domain. Interestingly, most h beta c mutants exhibited cell type-specific constitutive activity, with only two transmembrane domain mutants able to confer factor independence on both murine FDC-P1 and BAF-B03 cells. Examination of the biochemical properties of these mutants in FDC-P1 cells indicated that MAP kinase (ERK1/2), STAT, and JAK2 signaling molecules were constitutively activated. In contrast, only some of the mutant beta subunits were constitutively tyrosine phosphorylated. Taken together; these results highlight key regions involved in h beta c activation, dissociate h beta c tyrosine phosphorylation from MAP kinase and STAT activation, and suggest the involvement of distinct mechanisms by which proliferative signals can be generated by h beta c. (C) 1998 by The American Society of Hematology.

A cell type-specific constitutive point mutant of the common beta-subunit of the human granulocyte-macrophage colony-stimulating factor (GM-CSF), interleukin (IL)-3, and IL-5 receptors requires the GM-CSF receptor alpha-subunit for activation

The high affinity receptor for human granulocyte-macrophage colony-stimulating factor (GM-CSF) consists of a cytokine-specific alpha-subunit (hGMR alpha) and a common signal-transducing beta-subunit (hpc) that is shared with the interleukin-3 and -5 receptors, We have previously identified a constitutively active extracellular point mutant of hpc, I374N, that can confer factor independence on murine FDC-P1 cells but not BAF-B03 or CTLL-2 cells (Jenkins, B. J., D'Andrea, R. J., and Gonda, T. J. (1995) EMBO J. 14, 4276-4287), This restricted activity suggested the involvement of cell type-specific signaling molecules in the activation of this mutant. We report here that one such molecule is the mouse GMR alpha (mGMR alpha) subunit, since introduction of mGMR alpha, but not hGMR alpha, into BAF-B03 or CTLL-2 cells expressing the I374N mutant conferred factor independence, Experiments utilizing mouse/human chimeric GMR alpha subunits indicated that the species specificity lies in the extracellular domain of GMRa. Importantly, the requirement for mGMR alpha correlated with the ability of I374N (but not wild-type hpc) to constitutively associate with mGMRa. Expression of I374N in human factor-dependent UT7 cells also led to factor-independent proliferation, with concomitant up-regulation of hGMR alpha surface expression. Taken together, these findings suggest a critical role for association with GMR alpha in the constitutive activity of I374N.

Effects of data characteristics on the results of reserve selection algorithms

We tested the effects of four data characteristics on the results of reserve selection algorithms. The data characteristics were nestedness of features (land types in this case), rarity of features, size variation of sites (potential reserves) and size of data sets (numbers of sites and features). We manipulated data sets to produce three levels, with replication, of each of these data characteristics while holding the other three characteristics constant. We then used an optimizing algorithm and three heuristic algorithms to select sites to solve several reservation problems. We measured efficiency as the number or total area of selected sites, indicating the relative cost of a reserve system. Higher nestedness increased the efficiency of all algorithms (reduced the total cost of new reserves). Higher rarity reduced the efficiency of all algorithms (increased the total cost of new reserves). More variation in site size increased the efficiency of all algorithms expressed in terms of total area of selected sites. We measured the suboptimality of heuristic algorithms as the percentage increase of their results over optimal (minimum possible) results. Suboptimality is a measure of the reliability of heuristics as indicative costing analyses. Higher rarity reduced the suboptimality of heuristics (increased their reliability) and there is some evidence that more size variation did the same for the total area of selected sites. We discuss the implications of these results for the use of reserve selection algorithms as indicative and real-world planning tools.

Genetic algorithms for design of liquid retaining structure

In this paper, genetic algorithm (GA) is applied to the optimum design of reinforced concrete liquid retaining structures, which comprise three discrete design variables, including slab thickness, reinforcement diameter and reinforcement spacing. GA, being a search technique based on the mechanics of natural genetics, couples a Darwinian survival-of-the-fittest principle with a random yet structured information exchange amongst a population of artificial chromosomes. As a first step, a penalty-based strategy is entailed to transform the constrained design problem into an unconstrained problem, which is appropriate for GA application. A numerical example is then used to demonstrate strength and capability of the GA in this domain problem. It is shown that, only after the exploration of a minute portion of the search space, near-optimal solutions are obtained at an extremely converging speed. The method can be extended to application of even more complex optimization problems in other domains.

Worker demography in a large-colony, swarm-founding wasp

Neotropical swarm-founding wasps build nests enclosed in a covering envelope, which makes it difficult to count individual births and deaths. Thus, knowledge of worker demography is very limited for swarm-founding species compared with that for independent-founding species. In this study, we explored the worker demography of the swarm-founding wasp Polybia paulista, the colony size of which usually exceeds several thousand adults. We considered each wasp colony as an open-population and estimated the survival probability, recruitment rate, and population size of workers using the developments of the Cormack-Jolly-Seber model. We found that capture probability varied considerably among the workers, probably due to age polyethism and/or task specialization. The daily survival rate of workers was high (around 0.97) throughout the season and was not related to the phase of colony development. On the other hand, the recruitment rate ranged from 0 to 0.37, suggesting that worker production was substantially less important than worker survival in determining worker population fluctuations. When we compared survival rates among worker groups of one colony, the mean daily survival rate was lower for founding workers than for progeny workers and tended to be higher in progeny workers that emerged in winter. These differences in survivorship patterns among worker cohorts would be related to worker foraging activity and/or level of parasitism.