PubMed Health⌕ Search

SEARCH · PubMed Health

Results for “Dynamic Programming”

Explore indexed PubMed citations for clinical trials, systematic reviews and public health research. Read source abstracts and follow each citation to its original PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 667 records · Page 37Linked to original sources

Determination of optimal variable-sized multiple-block appointment systems.

The single-block appointment system is the most common method of scheduling ambulatory care clinics today. Several studies have examined various appointment systems ranging from single-block appointments on one extreme to individual appointments on the other, and including mixtures of these such as multiple-block (m-at-a-time) and block/individual systems. In this paper we analyze a general single-server multiple-block system, one permitting blocks of variable size. In the analysis we use a dynamic programming approach, with some modifications to compensate for the non-Markov nature of the problem. Analytical results and approximations which significantly reduce the computational requirements for a solution are obtained. Examples demonstrate that under certain weightings of the criteria of waiting, idle, and overtime, the generality of the system considered here allows performance superior to that of other commonly used systems.

Appointments and Schedules↗

An enhanced branch-and-bound algorithm for a partitioning problem.

This paper focuses on the problem of developing a partition of n objects based on the information in a symmetric, non-negative dissimilarity matrix. The goal is to partition the objects into a set of non-overlapping subsets with the objective of minimizing the sum of the within-subset dissimilarities. Optimal solutions to this problem can be obtained using dynamic programming, branch-and-bound and other mathematical programming methods. An improved branch-and-bound algorithm is shown to be particularly efficient. The improvements include better upper bounds that are obtained via a fast exchange algorithm and, more importantly, sharper lower bounds obtained through sequential solution of submatrices. A modified version of the branch-and-bound algorithm for minimizing the diameter of a partition is also presented. Computational results for both synthetic and empirical dissimilarity matrices reveal the effectiveness of the branch-and-bound methodology.

Algorithms↗

Moiré interferogram phase extraction: a ridge detection algorithm for continuous wavelet transforms.

We present a procedure using continuous wavelet transforms (CWTs) to extract the phase information from moiré interferograms. The relationship between precise ridge detection of the two-dimensional CWT magnitude map and accurate phase extraction is detailed. A cost function is introduced for the adaptive selection of the ridge, and a computationally inexpensive implementation of the cost function ridge detection algorithm is explored with dynamic programming optimization. The results of the proposed ridge detection algorithm on actual interferograms are illustrated. Moreover, the resulting extracted phase is demonstrated to be smooth and accurate. As a result, the sensitivity of the moiré interferometry method is improved to obtain a pixel-by-pixel in-plane strain distribution map.

Journal Article↗

A method for similarity search of genomic positional expression using CAGE.

With the advancement of genome research, it is becoming clear that genes are not distributed on the genome in random order. Clusters of genes distributed at localized genome positions have been reported in several eukaryotes. Various correlations have been observed between the expressions of genes in adjacent or nearby positions along the chromosomes depending on tissue type and developmental stage. Moreover, in several cases, their transcripts, which control epigenetic transcription via processes such as transcriptional interference and genomic imprinting, occur in clusters. It is reasonable that genomic regions that have similar mechanisms show similar expression patterns and that the characteristics of expression in the same genomic regions differ depending on tissue type and developmental stage. In this study, we analyzed gene expression patterns using the cap analysis gene expression (CAGE) method for exploring systematic views of the mouse transcriptome. Counting the number of mapped CAGE tags for fixed-length regions allowed us to determine genomic expression levels. These expression levels were normalized, quantified, and converted into four types of descriptors, allowing the expression patterns along the genome to be represented by character strings. We analyzed them using dynamic programming in the same manner as for sequence analysis. We have developed a novel algorithm that provides a novel view of the genome from the perspective of genomic positional expression. In a similarity search of expression patterns across chromosomes and tissues, we found regions that had clusters of genes that showed expression patterns similar to each other depending on tissue type. Our results suggest the possibility that the regions that have sense-antisense transcription show similar expression patterns between forward and reverse strands.

Algorithms↗

Near-optimal human adaptive control across different noise environments.

A person learning to control a complex system needs to learn about both the dynamics and the noise of the system. We evaluated human subjects' abilities to learn to control a stochastic dynamic system under different noise conditions. These conditions were created by corrupting the forces applied to the system with noise whose magnitudes were either proportional or inversely proportional to the sizes of subjects' control signals. We also used dynamic programming to calculate the mathematically optimal control laws of an "ideal actor" for each noise condition. The results suggest that people learned control strategies tailored to the specific noise characteristics of their training conditions. In particular, as predicted by the ideal actors, they learned to use smaller control signals when forces were corrupted by proportional noise and to use larger signals when forces were corrupted by inversely proportional noise, thereby achieving levels of performance near the information-theoretic upper bounds. We conclude that subjects learned to behave in a near-optimal manner, meaning that they learned to efficiently use all available information to plan and execute control policies that maximized performances on their tasks.

Acclimatization↗

Computed pore potentials of the nicotinic acetylcholine receptor.

Electrostatic surface potentials in the vestibule of the nicotinic acetylcholine receptor (nAChR) were computed from structural models using the University of Houston Brownian Dynamics program to determine their effect on ion conduction and ionic selectivity. To further determine whether computed potentials accurately reflect the electrostatic environment of the channel, the potentials were used to predict the rate constants for diffusion-enhanced fluorescence energy transfer; the calculated energy transfer rates are directly comparable with those determined experimentally (see companion article by Meltzer et al. in this issue). To include any effects on the local potentials by the bound acceptor fluorophore crystal violet, its binding site was first localized within the pore by fluorescence energy transfer measurements from dansyl-C6-choline bound to the agonist sites and also by simulations of binding using Autodock. To compare the computed potentials with those determined experimentally, we used the predicted energy transfer rates from Tb3+ chelates of varying charge to calculate an expected potential using the Boltzmann relationship. This expected potential (from -20 to -40 mV) overestimates the values determined experimentally (from -10 to -25 mV) by two- to fourfold at similar conditions of ionic strength. Although the results indicate a basic discrepancy between experimental and computed surface potentials, both methods demonstrate that the vestibular potential has a relatively small effect on conduction and selectivity.

Cell Membrane↗

Family income and the impact of a children's health insurance program on reported need for health services and unmet health need.

OBJECTIVE: In an era when expanding publicly funded health insurance to children in higher income families has been the major strategy to increase access to health care for children, it is important to determine if the benefits to higher income children attributable to the receipt of health coverage are similar to those observed for lower income children. This study investigated how the likely impact of child health insurance expansions varies with family income. METHODS: We surveyed parents or guardians of children who were enrolled in a state-sponsored health insurance program (Massachusetts Children's Medical Security Plan [CMSP]) that, before the implementation of the State Children's Health Insurance Plan (SCHIP), was open to all children regardless of income. A stratified sample of children was drawn from administrative files. We grouped children by income category (low-income [LI]: < or =133% of the federal poverty limit [FPL], middle-income [MI]: 134%-200% of the FPL, high-income [HI]: >200% of the FPL) that corresponded to eligibility for public health insurance programs in the state (Medicaid-eligible, SCHIP-eligible, and income that exceeded SCHIP eligibility). The majority of telephone interviews were conducted between November 1998 and March 1999. The overall response rate was 61.8%, yielding a sample of 996 children. The CSMP benefit package included comprehensive coverage for preventive and specialty care and limited coverage for ancillary services. Children enrolled in CMSP were not covered for inpatient hospital stays but those whose family income was <400% of the FPL were eligible to receive full or partial coverage for inpatient care through the state's free care pool. Although the CMSP benefit package did not meet the standards for a SCHIP, it is an approximate equivalent for children with incomes <200% of the FPL, who have full coverage for hospitalization through the state's free care pool. We used survey responses to develop 2 sets of indicators: the first for reported need for services and the second for unmet need or delays in care among children whose parents reported a need for the service. Within each set, we created indicators for 5 types of service (medical care, dental care, prescription drugs, vision services, and mental health care) and an additional composite indicator. The composite indicator aggregated all categories of services covered under CMSP in a single measure; it included all services except dental services, which, at the time of the study, were not covered by the program. The composite indicator served as the dependent variable in regression models. We used weighted chi2 tests to identify statistically significant differences in reported need and unmet need for the 5 types of medical services and the aggregate measure of all services covered by CMSP. We examined differences across income groups at 2 points in time: during the period children were uninsured before enrollment and while enrolled. We used weighted logistic regression to assess the independent association of family income with our dependent variables: reported need for health services and the presence of unmet need, controlling for other covariates. To evaluate the impact of participation in a child health insurance program, we examined unmet need before and after program enrollment, testing for statistical significance using McNemar's test for within-subject changes. RESULTS: During the period of uninsurance before enrollment, prescription drugs (70%) was the health service needed most frequently, followed by medical (65%) and dental (57%) care. For the composite measure of services covered by CMSP, reported need for services was not significantly different by income. Need for medical care, dental care, and prescription drugs were significantly greater among children who had been uninsured for >6 months before enrollment. In addition, a significantly greater proportion of adolescent participants needed dental, vision, and mental health services than younger enrollees. While enrolled, among recently enrolled children, 77% need medical services, 68% prescription drugs, and 59% dental. In unadjusted models MI and HI children were more than 2 times as likely to report need for covered services as LI children. After adjusting for possible confounders, the effect of income was no longer significant. Instead, nonadolescents (odds ratio [OR]: 2.44; 95% confidence interval [CI]: 1.25-4.76) and children with white ethnicity (OR: 3.03; 95% CI: 1.43-6.67) were significantly more likely to report need for services. Before enrollment, unmet need among those who reported need for services was 5% for medical, 4% prescription drugs, 31% dental, 30% vision, and 33% mental health. For the composite measure of services covered by CMSP, LI children were significantly more likely to have had unmet need before enrollment than MI and HI children (20%, 10%, 7% by income). As compared with younger children, adolescents also had significantly greater unmet need for the composite measure (19% vs 10%). In multivariate models, not having a usual site of care was a highly significant predictor of unmet need or delayed care (OR: 3.41; 95% CI: 1.28-9.11). Ninety-eight percent of parents cited cost as the reason they had difficulty obtaining needed care. After enrollment, the proportion of children who needed care and had difficulty obtaining it decreased for all categories of care. Less than 1% of enrollees reported unmet need or delays in care for medical services and 3% for prescription drugs. Children who needed vision and mental health services continued to experience difficulty obtaining these services (17% for each category of care), although they were covered as part of the benefit package. Unmet need or delays in care for dental services, which at the time of the study were not covered under CMSP, remained high (27%). We found a significant reduction in unmet need among children in all income groups and no significant differences in unmet need by income. Controlling for other covariates, adolescents (OR: 3.11; 95% CI: 1.58-6.12) and children with compromised health (OR: 3.20; 95% CI: 1.35-7.58) were more likely to have had difficulty obtaining needed services while enrolled in the program. Children in larger families (OR: 0.40; 95% CI: 0.17-0.96) and who were previously uninsured for >6 months (OR: 0.45; 95% CI: 0.22-7.58) were less likely to have difficulty obtaining care. CONCLUSION: Our findings demonstrate the positive impact of providing health insurance coverage to children regardless of income. The HI children who enrolled in the program looked similar to children with incomes that meet current SCHIP eligibility guidelines, suggesting that expansions of SCHIPs to HI children should not qualitatively change the program dynamics.

Child↗

Foraging in a tidally structured environment by Red Knots (Calidris canutus): ideal, but not free.

Besides the "normal" challenge of obtaining adequate intake rates in a patchy and dangerous world, shorebirds foraging in intertidal habitats face additional environmental hurdles. The tide forces them to commute between a roosting site and feeding grounds, twice a day. Moreover, because intertidal food patches are not all available at the same time, shorebirds should follow itineraries along the best patches available at a given time. Finally, shorebirds need additional energy stores in order to survive unpredictable periods of bad weather, during which food patches are covered by extreme tides. In order to model such tide-specific decisions, we applied stochastic dynamic programming in a spatially explicit context. Two assumptions were varied, leading to four models. First, birds had either perfect (ideal) or no (non-ideal) information about the intake rate at each site. Second, traveling between sites was either for free or incurred time and energy costs (non-free). Predictions were generated for three aspects of foraging: area use, foraging routines, and energy stores. In general, non-ideal foragers should feed most intensely and should maintain low energy stores. If traveling for such birds is free, they should feed at a random site; otherwise, they should feed close to their roost. Ideal foragers should concentrate their feeding around low tide (especially when free) and should maintain larger energy stores (especially when non-free). If traveling for such birds is free, they should feed at the site offering the highest intake rate; otherwise, they should trade off travel costs and intake rate. Models were parameterized for Red Knots (Calidris canutus) living in the Dutch Wadden Sea in late summer, an area for which detailed, spatially explicit data on prey densities and tidal heights are available. Observations of radio-marked knots (area use) and unmarked knots (foraging routines, energy stores) showed the closest match with the ideal/non-free model. We conclude that knots make state-dependent decisions by trading off starvation against foraging-associated risks, including predation. Presumably, knots share public information about resource quality that enables them to behave in a more or less ideal manner. We suggest that our modeling approach may be applicable in other systems where resources fluctuate in space and time.

Animals↗

Optimal assignment of treatments to health states using a Markov decision model: an introduction to basic concepts.

Assessing the cost effectiveness of a new health intervention often requires modelling to estimate the impact of the intervention on cost, survival and quality of life over the lifetime of a cohort of patients. Markov modelling is a methodology that is commonly employed to estimate these long-term costs and benefits. As commonly used, these models assume that the patients continue to get the treatments assigned regardless of the change in health states. In this paper, we describe an extension to the Markov modelling approach, called Markov decision modelling. Such a model starts with a set of health states and treatments and optimally assigns treatments to each of the health states. A Markov decision model can be used to identify the optimal treatment strategy not just for the initial disease state, but also as the disease state changes over time. We present a dynamic programming approach to identifying the optimal assignment of treatments, and illustrate this methodology using an example. The Markov decision modelling approach provides an efficient way of identifying optimal assignment of treatments to health states, but, like the standard Markov model, may be of limited use when probabilities of future events depend on past history in a complex fashion. Even with its limitations, Markov decision models offer an opportunity for health economists to inform healthcare decision-makers on how to modify current treatment pathways to incorporate new treatments as they become available.

CD4 Lymphocyte Count↗

Constructing sequence alignments from a Markov decision model with estimated parameter values.

Current methods for aligning biological sequences are based on dynamic programming algorithms. If large numbers of sequences or a number of long sequences are to be aligned, the required computations are expensive in memory and central processing unit (CPU) time. In an attempt to bring the tools of large-scale linear programming (LP) methods to bear on this problem, we formulate the alignment process as a controlled Markov chain and construct a suggested alignment based on policies that minimise the expected total cost of the alignment. We discuss the LP associated with the total expected discounted cost and show the results of a solution of the problem based on a primal-dual interior point method. Model parameters, estimated from aligned sequences, along with cost function parameters are used to construct the objective and constraint conditions of the LP problem. This article concludes with a discussion of some alignments obtained from the LP solutions of problems with various cost function parameter values.

Algorithms↗

Optimization of dairy heifer management decisions based on production conditions of Pennsylvania.

We used a dynamic programming model to determine optimum rearing decisions of dairy replacements. Heifers were described in the model by age, season, body weight, pregnancy state, and prepubertal growth rate. Prices and parameters were chosen to represent the dairy population of Pennsylvania. We calculated monthly costs and revenues from calf value, feed costs, veterinary costs, semen costs, carcass value, and full-grown heifer value. The model considered a stochastic variation in the onset of puberty, conception, involuntary disposal, and a seasonal variation in the prices of calves, heifers, and feed. Based on a critical prepubertal average daily gain of 0.9 kg/d and a maximum achievable postpubertal growth rate of 1.1 kg/d, the optimum practice resulted in an average age at first calving of 20.5 mo at a body weight of 563 kg. Discounted net returns equaled $107 per heifer per year. The optimum rearing practice was not sensitive to seasonal variation in prices. Nevertheless, the economic results per season of birth varied considerably; the highest income per heifer was obtained from heifers born in December ($142/yr), whereas those born in May yielded the lowest ($100/yr). Sensitivity analyses demonstrated a considerable influence of growth rate restrictions and variation in reproductive performance on both the optimal rearing practices as the expected net returns.

Animal Feed↗

Economics of delayed replacement when cow performance is seasonal.

An optimal dairy cow culling and replacement model was developed; it included the option to delay entering heifers into the herd after cows were culled. The objective was to investigate whether leaving a slot temporarily vacant, to enter a heifer at a more favorable time of the year, could be economically advantageous when cow performance is seasonal. The goal of the optimization was therefore to maximize net return per slot per year. The model consisted of 3 modules: 1) a bioeconomic module to enter and calculate cow performance data and prices, 2) a replacement policy module based on dynamic programming to calculate optimal culling decisions for individual cows and when to enter heifers, and 3) a herd performance module based on Markov chains to calculate summary results for the herd. Results for the optimal culling policy under typical conditions in Florida showed that immediate replacement was economically advantageous throughout the year. However, for a nonoptimal culling policy, cows culled in May, June, and July would not be replaced by heifers until August. Realistic increases in seasonality or heifer prices, or lower milk prices, showed economic advantages of delayed over immediate replacement for both culling policies. The maximum advantage of delayed replacement of 486 price scenarios was 88 US dollars per slot per year; cows that left the herd in the early summer and spring were not replaced by heifers until the late summer. Delayed replacement was economically advantageous when fixed costs and net returns per slot were low and seasonality was high, which is the case for a portion of Florida dairy producers.

Animals↗

Optimal replacement of mastitic cows determined by a hierarchic Markov process.

Farmers frequently have to decide whether to keep or to replace cows that suffer from clinical mastitis. A dynamic programming model was developed to optimize these decisions for individual cows within the herd, using the hierarchic Markov process technique. This technique provides a method to model a wide variety of cows, differing in age, productive performance, reproductive status, and clinical mastitis occurrence. The model presented was able to support decisions related to 63% of all replacements. Results--for Dutch conditions--showed the considerable impact of mastitis on expected income of affected cows. Nevertheless, in most cases, the optimal decision was to keep and to treat rather than to replace the cow. Clinical mastitis occurring in the previous lactation negligibly influence expected income. Clinical mastitis in current lactation, especially in the current month, however, had a significant effect on expected income. Total losses caused by clinical mastitis were US$83/yr per cow. Farm level treatment, which reduced incidence by 25%, on a farm with 10 clinical quarter cases per 10,000 cow days, may cost at maximum US$27/yr per cow.

Animals↗

Present and future uses of selection index methodology in dairy cattle.

Selection indexes have been extensively applied in the estimation of breeding value of dairy cattle for single traits as well as for combinations of traits for selection purposes. Milestones in methodology, such as multiple-trait evaluation procedures by BLUP, (co)variance component estimation, nonlinear models, discounted gene flow, dynamic programming, and international sire evaluations, together with increased computing power and the development of integrated AI and recording schemes, have contributed to efficient implementation of selection indexes and are reviewed in this article. Results of an international survey on evaluation practices and breeding programs are presented, demonstrating wide adoption of index selection for total merit and the need for further applications. Results from a simulation study on the efficiency of index selection for total merit are also presented; when the breeding goal includes, in addition to production traits, functional nonproduction traits such as mastitis resistance and fertility, failure to consider these traits in the selection index decreases efficiency 15 to 25%. Future applications are also discussed in view of advances in the areas of genome mapping, marker detection, and international comparisons. Further research should focus on functional nonproduction traits.

Animal Husbandry↗

Optimal replacement and insemination policies for Holstein cattle in the southeastern region of Brazil: the effect of selling animals for production.

Dynamic programming was used to determine optimal replacement and insemination policies for Holstein-Friesian cattle in the southeastern region of Brazil. Optimal insemination and replacement decisions were determined for two disposal alternatives: selling all cows exclusively for slaughter (A) or selling the cows either for slaughter or to other farmers for production (B). Disposal alternative B reflects the common practice among dairy farmers to sell some of their cows to other farmers at a higher price than the carcass price. In the model, cows were described in terms of lactation number, stage of lactation, calving interval, and milk produced during present and previous lactation. For disposal alternative A, the optimal average herd life was 54.9 mo, corresponding to annual replacement and voluntary culling rates of 21.8 and 4.1%, respectively. For disposal alternative B, the optimal average herd life was 44.0 mo, which corresponded to annual replacement and voluntary culling rates of 27.3 and 10.0%, respectively. In this case, from the total of voluntarily culled cows, 70% were sold to other farmers for production. Sensitivity analyses showed that changes in the disposal value of cows and replacement heifer prices strongly influenced the optimal insemination and replacement policy.

Abattoirs↗

Analysis of ribosomal RNA sequences by combinatorial clustering.

We present an analysis of multi-aligned eukaryotic and procaryotic small subunit rRNA sequences using a novel segmentation and clustering procedure capable of extracting subsets of sequences that share common sequence features. This procedure consists of: i) segmentation of aligned sequences using a dynamic programming procedure, and subsequent identification of likely conserved segments; ii) for each putative conserved segment, extraction of a locall homogeneous cluster using a novel polynomial procedure; and iii) intersection of clusters associated with each conserved segment. Aside from their utilit in processing large gap-filled multi-alignments, these algorithms can be applied to a broad spectrum of rRNA analysis functions such as subalignment, phylogenetic subtree extraction and construction, and organism tree-placement, and can serve as a framework to organize sequence data in an efficient and easily searchable manner. The sequence classification we obtained using the method presented here shows a remarkable consistency with the independently constructed eukaryotic phylogenetic tree.

Algorithms↗

Key residues approach to the definition of protein families and analysis of sparse family signatures.

We extend the concept of the motif as a tool for characterizing protein families and explore the feasibility of a sparse "motif" that is the length of the protein sequence itself. The type of motif discussed is a sparse family signature consisting of a set of N key residue positions (A1, A2...AN) preceded by gaps (G) thus G1A1G2A2. ...GNAN. Both a residue and gap can be variable. A signature is matched to a protein sequence and scored using a dynamic programming algorithm which permits variability in gap distance and residue type. Generating a signature involves identifying residues associated with points of contact in interactions between secondary structure elements. A raw signature consists of a set of positions with potential key structural roles sampled from a sequence alignment constructed with reference to this contact data. Raw signatures are refined by sampling different gap-residue pairs until the specificity of a signature for the family cannot be further improved. We summarize signatures for nine families of protein of diverse fold and function and present results of scans against the OWL protein sequence database. The implications of such signatures are discussed.

Algorithms↗

Optimizing breeding decisions for Finnish dairy herds.

The purpose of this study was to determine the effect of reproductive performance on profitability and optimal breeding decisions for Finnish dairy herds. We used a dynamic programming model to optimize dairy cow insemination and replacement decisions. This optimization model maximizes the expected net revenues from a given cow and her replacements over a decision horizon. Input values and prices reflecting the situation in 1998 in Finland were used in the study. Reproductive performance was reflected in the model by overall pregnancy rate, which was a function of heat detection and conception rate. Seasonality was included in conception rate. The base run had a pregnancy rate of 0.49 (both heat detection and conception rate of 0.7). Different scenarios were modeled by changing levels of conception rate, heat detection, and seasonality in fertility. Reproductive performance had a considerable impact on profitability of a herd; good heat detection and conception rates provided an opportunity for management control. When heat detection rate decreased from 0.7 to 0.5, and everything else was held constant, net revenues decreased approximately 2.6%. If the conception rate also decreased to 0.5 (resulting in a pregnancy rate of 0.25), net revenues were approximately 5% lower than with a pregnancy rate of 0.49. With lower fertility, replacement percentage was higher and the financial losses were mainly from higher replacement costs. Under Finnish conditions, it is not optimal to start breeding cows calving in spring and early summer immediately after the voluntary waiting period. Instead, it is preferable to allow the calving interval to lengthen for these cows so that their next calving is in the fall. However, cows calving in the fall should be bred immediately after the voluntary waiting period. Across all scenarios, optimal solutions predicted most calvings should occur in fall and the most profitable time to bring a replacement heifer into a herd was in the fall. It was economically justifiable to keep breeding high producing cows longer than low producing cows.

Animal Husbandry↗