Assembling genes from predicted exons in linear time with dynamic programming

In a number of programs for gene structure prediction in higher eukaryotic genomic sequences, exon prediction is decoupled from gene assembly: a large pool of candidate exons is predicted and scored from features located in the query DNA sequence, and candidate genes are assembled from such a pool as sequences of nonoverlapping frame-compatible exons. Genes are scored as a function of the scores of the assembled exons, and the highest scoring candidate gene is assumed to be the most likely gene encoded by the query DNA sequence. Considering additive gene scoring functions, currently available algorithms to determine such a highest scoring candidate gene run in time proportional to the square of the number of predicted exons. Here, we present an algorithm whose running time grows only linearly with the size of the set of predicted exons. Polynomial algorithms rely on the fact that, while scanning the set of predicted exons, the highest scoring gene ending in a given exon can be obtained by appending the exon to the highest scoring among the highest scoring genes ending at each compatible preceding exon. The algorithm here relies on the simple fact that such highest scoring gene can be stored and updated. This requires scanning the set of predicted exons simultaneously by increasing acceptor and donor position. On the other hand, the algorithm described here does not assume an underlying gene structure model. Indeed, the definition of valid gene structures is externally defined in the so-called Gene Model. The Gene Model specifies simply which gene features are allowed immediately upstream which other gene features in valid gene structures. This allows for great flexibility in formulating the gene identification problem. In particular it allows for multiple-gene two-strand predictions and for considering gene features other than coding exons (such as promoter elements) in valid gene structures.

Evolution in structured populations

Cet article est un compte-rendu du colloque "Evolution in Structured Population", tenu du 14 au 16 Septembre 1994 à l'Université de Lausanne. Consacré aux causes écologiques et conséquences évolutives d'horizons divers (zoologie, botanique, anthropologie, mathématiques), utilisant des approches variées, aussi bien empiriques que théoriques. Plusieurs exemples concrets de structurations génétiques de populations naturelles ont été documentés, et leurs causes analysées. Celles-ci sont variées, certaines étant extrinsèques à la biologie des espèces concernées (distances géographique, barrières écologiques, etc), d'autres intrinsèques (stratégies de reproduction, mutations chromosomiques). Les outils quantitatifs les plus largement utilisés pour analyser ces structures restent les F-statistiques de Whright; elles ont néanmoins fait l'objet de plusieurs critiques: d'une part, elles n'exploitent pas toute l'information disponible (certains orateurs ont d'ailleurs proposé diverses améliorations dans ce sens); d'autre part, les hypothèses qui sous-tendent leur interprétation conventionelle (en particulier l'hypothèse de populations à l'équilibre) sont régulièrement violées. Plusieurs des travaux présentés se sont précisément intéressés aux situations de déséquilibre et à leurs conséquences sur la dynamique et l'évolution des populations. Parmi celles ci: l'effet d'extinctions démiques sur les stratégies de dispersion des organismes et la structure génétique de leurs métapopulations, l'inadéquation du modèle classique de métapopulation, dit modèle en île (les modèles de diffusion ou de "pas japonais" (stepping stone) semblent généralement préférables), et le rôle de la "viscosité" des populations, en particulier en relation avec la sélection de parentèle et l'évolution de structures sociales. Le rôle important d'événements historiques sur les structures actuelles a été souligné, notamment dans le cadre de contacts secondaires entre populations hautement différenciées, leur introgression possible et la biogéographie de taxons vicariants. Parmi les problèmes récurrents notés: l'identification de l'unité panmictique, l'échelle de mesure spatiale appropriée, et les difficulté d'estimation des taux de migration et de flux de gènes. Plusieurs auteurs ont relevé la nécessité d'études biologiques de détail: les structures génétiques n'ont d'intérêt que dans la mesure où elles peuvent être situées dans un contexte écologique et évolutif précis. Ce point a été largement illustré dans le cadre des realtions entre structures génétiques et stratégies de reproduction/dispersion.

Cumulative cultural dynamics and the coevolution of cultural innovation and transmission: an ESS model for panmictic and structured populations.

When individuals in a population can acquire traits through learning, each individual may express a certain number of distinct cultural traits. These traits may have been either invented by the individual himself or acquired from others in the population. Here, we develop a game theoretic model for the accumulation of cultural traits through individual and social learning. We explore how the rates of innovation, decay, and transmission of cultural traits affect the evolutionary stable (ES) levels of individual and social learning and the number of cultural traits expressed by an individual when cultural dynamics are at a steady-state. We explore the evolution of these phenotypes in both panmictic and structured population settings. Our results suggest that in panmictic populations, the ES level of learning and number of traits tend to be independent of the social transmission rate of cultural traits and is mainly affected by the innovation and decay rates. By contrast, in structured populations, where interactions occur between relatives, the ES level of learning and the number of traits per individual can be increased (relative to the panmictic case) and may then markedly depend on the transmission rate of cultural traits. This suggests that kin selection may be one additional solution to Rogers's paradox of nonadaptive culture.

A randomized concave programming method for choice network revenue management

Models incorporating more realistic models of customer behavior, as customers choosing froman offer set, have recently become popular in assortment optimization and revenue management.The dynamic program for these models is intractable and approximated by a deterministiclinear program called the CDLP which has an exponential number of columns. However, whenthe segment consideration sets overlap, the CDLP is difficult to solve. Column generationhas been proposed but finding an entering column has been shown to be NP-hard. In thispaper we propose a new approach called SDCP to solving CDLP based on segments and theirconsideration sets. SDCP is a relaxation of CDLP and hence forms a looser upper bound onthe dynamic program but coincides with CDLP for the case of non-overlapping segments. Ifthe number of elements in a consideration set for a segment is not very large (SDCP) can beapplied to any discrete-choice model of consumer behavior. We tighten the SDCP bound by(i) simulations, called the randomized concave programming (RCP) method, and (ii) by addingcuts to a recent compact formulation of the problem for a latent multinomial-choice model ofdemand (SBLP+). This latter approach turns out to be very effective, essentially obtainingCDLP value, and excellent revenue performance in simulations, even for overlapping segments.By formulating the problem as a separation problem, we give insight into why CDLP is easyfor the MNL with non-overlapping considerations sets and why generalizations of MNL posedifficulties. We perform numerical simulations to determine the revenue performance of all themethods on reference data sets in the literature.

A new compact linear programming formulation for choice network revenue management

The choice network revenue management model incorporates customer purchase behavioras a function of the offered products, and is the appropriate model for airline and hotel networkrevenue management, dynamic sales of bundles, and dynamic assortment optimization.The optimization problem is a stochastic dynamic program and is intractable. A certainty-equivalencerelaxation of the dynamic program, called the choice deterministic linear program(CDLP) is usually used to generate dyamic controls. Recently, a compact linear programmingformulation of this linear program was given for the multi-segment multinomial-logit (MNL)model of customer choice with non-overlapping consideration sets. Our objective is to obtaina tighter bound than this formulation while retaining the appealing properties of a compactlinear programming representation. To this end, it is natural to consider the affine relaxationof the dynamic program. We first show that the affine relaxation is NP-complete even for asingle-segment MNL model. Nevertheless, by analyzing the affine relaxation we derive a newcompact linear program that approximates the dynamic programming value function betterthan CDLP, provably between the CDLP value and the affine relaxation, and often comingclose to the latter in our numerical experiments. When the segment consideration sets overlap,we show that some strong equalities called product cuts developed for the CDLP remain validfor our new formulation. Finally we perform extensive numerical comparisons on the variousbounds to evaluate their performance.

On the throughput-WIP trade-off in queueing systems, diminishing returns and the threshold property: A linear programming approach

We present a new unifying framework for investigating throughput-WIP(Work-in-Process) optimal control problems in queueing systems,based on reformulating them as linear programming (LP) problems withspecial structure: We show that if a throughput-WIP performance pairin a stochastic system satisfies the Threshold Property we introducein this paper, then we can reformulate the problem of optimizing alinear objective of throughput-WIP performance as a (semi-infinite)LP problem over a polygon with special structure (a thresholdpolygon). The strong structural properties of such polygones explainthe optimality of threshold policies for optimizing linearperformance objectives: their vertices correspond to the performancepairs of threshold policies. We analyze in this framework theversatile input-output queueing intensity control model introduced byChen and Yao (1990), obtaining a variety of new results, including (a)an exact reformulation of the control problem as an LP problem over athreshold polygon; (b) an analytical characterization of the Min WIPfunction (giving the minimum WIP level required to attain a targetthroughput level); (c) an LP Value Decomposition Theorem that relatesthe objective value under an arbitrary policy with that of a giventhreshold policy (thus revealing the LP interpretation of Chen andYao's optimality conditions); (d) diminishing returns and invarianceproperties of throughput-WIP performance, which underlie thresholdoptimality; (e) a unified treatment of the time-discounted andtime-average cases.

Implementing TURF analysis through binary linear programming

This paper introduces the approach of using Total Unduplicated Reach and Frequency analysis (TURF) to design a product line through a binary linear programming model. This improves the efficiency of the search for the solution to the problem compared to the algorithms that have been used to date. The results obtained through our exact algorithm are presented, and this method shows to be extremely efficient both in obtaining optimal solutions and in computing time for very large instances of the problem at hand. Furthermore, the proposed technique enables the model to be improved in order to overcome the main drawbacks presented by TURF analysis in practice.

Restless bandits, linear programming relaxations and a primal-dual index heuristic

We develop a mathematical programming approach for the classicalPSPACE - hard restless bandit problem in stochastic optimization.We introduce a hierarchy of n (where n is the number of bandits)increasingly stronger linear programming relaxations, the lastof which is exact and corresponds to the (exponential size)formulation of the problem as a Markov decision chain, while theother relaxations provide bounds and are efficiently computed. Wealso propose a priority-index heuristic scheduling policy fromthe solution to the first-order relaxation, where the indices aredefined in terms of optimal dual variables. In this way wepropose a policy and a suboptimality guarantee. We report resultsof computational experiments that suggest that the proposedheuristic policy is nearly optimal. Moreover, the second-orderrelaxation is found to provide strong bounds on the optimalvalue.

Geographical and temporal body size variation in a reptile: roles of sex, ecology, phylogeny and ecology structured in phylogeny.

Geographical body size variation has long interested evolutionary biologists, and a range of mechanisms have been proposed to explain the observed patterns. It is considered to be more puzzling in ectotherms than in endotherms, and integrative approaches are necessary for testing non-exclusive alternative mechanisms. Using lacertid lizards as a model, we adopted an integrative approach, testing different hypotheses for both sexes while incorporating temporal, spatial, and phylogenetic autocorrelation at the individual level. We used data on the Spanish Sand Racer species group from a field survey to disentangle different sources of body size variation through environmental and individual genetic data, while accounting for temporal and spatial autocorrelation. A variation partitioning method was applied to separate independent and shared components of ecology and phylogeny, and estimated their significance. Then, we fed-back our models by controlling for relevant independent components. The pattern was consistent with the geographical Bergmann's cline and the experimental temperature-size rule: adults were larger at lower temperatures (and/or higher elevations). This result was confirmed with additional multi-year independent data-set derived from the literature. Variation partitioning showed no sex differences in phylogenetic inertia but showed sex differences in the independent component of ecology; primarily due to growth differences. Interestingly, only after controlling for independent components did primary productivity also emerge as an important predictor explaining size variation in both sexes. This study highlights the importance of integrating individual-based genetic information, relevant ecological parameters, and temporal and spatial autocorrelation in sex-specific models to detect potentially important hidden effects. Our individual-based approach devoted to extract and control for independent components was useful to reveal hidden effects linked with alternative non-exclusive hypothesis, such as those of primary productivity. Also, including measurement date allowed disentangling and controlling for short-term temporal autocorrelation reflecting sex-specific growth plasticity.

Evolutionary branching in deme-structured populations.

Adaptive dynamics shows that a continuous trait under frequency dependent selection may first converge to a singular point followed by spontaneous transition from a unimodal trait distribution into a bimodal one, which is called "evolutionary branching". Here, we study evolutionary branching in a deme-structured population by constructing a quantitative genetic model for the trait variance dynamics, which allows us to obtain an analytic condition for evolutionary branching. This is first shown to agree with previous conditions for branching expressed in terms of relatedness between interacting individuals within demes and obtained from mutant-resident systems. We then show this branching condition can be markedly simplified when the evolving trait affect fecundity and/or survival, as opposed to affecting population structure, which would occur in the case of the evolution of dispersal. As an application of our model, we evaluate the threshold migration rate below which evolutionary branching cannot occur in a pairwise interaction game. This agrees very well with the individual-based simulation results.

Fever in neutropenic cancer patients : a structured approach

Infectious complications related to acquired neutropenia have become a major medical issue, often requiring intensive care management. These infections may be lethal if empirical broad-spectrum treatment is not rapidly started at the first sign of infection (i.e., fever), and this concept is now widely recognized a standard practice. However, the choice of antibiotics has generated considerable controversy for nearly 25 years. After reviewing some particularities of infection in neutropenic patients, this paper will discuss the options and present comprehensive algorithm for non-infectious diseases specialist, including recent advances about early IV-oral switch and the selection of low risk patients for outpatient management.

Programming and analysing measurement experiments using the PicoCricket system

The aim of this project is to get used to another kind of programming. Since now, I used very complex programming languages to develop applications or even to program microcontrollers, but PicoCricket system is the evidence that we don’t need so complex development tools to get functional devices. PicoCricket system is the clear example of simple programming to make devices work the way we programmed it. There’s an easy but effective way to program small, devices just saying what we want them to do. We cannot do complex algorithms and mathematical operations but we can program them in a short time. Nowadays, the easier and faster we produce, the more we earn. So the tendency is to develop fast, cheap and easy, and PicoCricket system can do it.

The stationary distribution of a continuously varying strategy in a class-structured population under mutation-selection-drift balance.

Many traits and/or strategies expressed by organisms are quantitative phenotypes. Because populations are of finite size and genomes are subject to mutations, these continuously varying phenotypes are under the joint pressure of mutation, natural selection and random genetic drift. This article derives the stationary distribution for such a phenotype under a mutation-selection-drift balance in a class-structured population allowing for demographically varying class sizes and/or changing environmental conditions. The salient feature of the stationary distribution is that it can be entirely characterized in terms of the average size of the gene pool and Hamilton's inclusive fitness effect. The exploration of the phenotypic space varies exponentially with the cumulative inclusive fitness effect over state space, which determines an adaptive landscape. The peaks of the landscapes are those phenotypes that are candidate evolutionary stable strategies and can be determined by standard phenotypic selection gradient methods (e.g. evolutionary game theory, kin selection theory, adaptive dynamics). The curvature of the stationary distribution provides a measure of the stability by convergence of candidate evolutionary stable strategies, and it is evaluated explicitly for two biological scenarios: first, a coordination game, which illustrates that, for a multipeaked adaptive landscape, stochastically stable strategies can be singled out by letting the size of the gene pool grow large; second, a sex-allocation game for diploids and haplo-diploids, which suggests that the equilibrium sex ratio follows a Beta distribution with parameters depending on the features of the genetic system.

Report to the Governor and General Assembly on the Status of Out-of School Arts Programming for Youth, December 2006

In the 2006 Iowa General Assembly, House File 2797 called for a study on the status of afterschool arts programs and appropriated $5,000 for the study. In accordance with the legislation, the Iowa Arts Council, who received the charge, contracted with the Iowa Afterschool Alliance to form a Resource Group of out-of-school arts providers and experts to develop and oversee the study, review its results, and make recommendations for the expansion of arts programs that operate outside the normal school day. As a part of its charge in HF 2797, the Iowa Arts Council also documented a sampling of out-of-school arts programs statewide. Five are featured in this report.