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.

Relatedness influences signal reliability in evolving robots.

Communication is an indispensable component of animal societies, yet many open questions remain regarding the factors affecting the evolution and reliability of signalling systems. A potentially important factor is the level of genetic relatedness between signallers and receivers. To quantitatively explore the role of relatedness in the evolution of reliable signals, we conducted artificial evolution over 500 generations in a system of foraging robots that can emit and perceive light signals. By devising a quantitative measure of signal reliability, and comparing independently evolving populations differing in within-group relatedness, we show a strong positive correlation between relatedness and reliability. Unrelated robots produced unreliable signals, whereas highly related robots produced signals that reliably indicated the location of the food source and thereby increased performance. Comparisons across populations also revealed that the frequency for signal production-which is often used as a proxy of signal reliability in empirical studies on animal communication-is a poor predictor of signal reliability and, accordingly, is not consistently correlated with group performance. This has important implications for our understanding of signal evolution and the empirical tools that are used to investigate communication.

Using robots to understand social behaviour.

A major challenge in studying social behaviour stems from the need to disentangle the behaviour of each individual from the resulting collective. One way to overcome this problem is to construct a model of the behaviour of an individual, and observe whether combining many such individuals leads to the predicted outcome. This can be achieved by using robots. In this review we discuss the strengths and weaknesses of such an approach for studies of social behaviour. We find that robots-whether studied in groups of simulated or physical robots, or used to infiltrate and manipulate groups of living organisms-have important advantages over conventional individual-based models and have contributed greatly to the study of social behaviour. In particular, robots have increased our understanding of self-organization and the evolution of cooperative behaviour and communication. However, the resulting findings have not had the desired impact on the biological community. We suggest reasons for why this may be the case, and how the benefits of using robots can be maximized in future research on social behaviour.

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.

Historical contingency affects signaling strategies and competitive abilities in evolving populations of simulated robots.

One of the key innovations during the evolution of life on earth has been the emergence of efficient communication systems, yet little is known about the causes and consequences of the great diversity within and between species. By conducting experimental evolution in 20 independently evolving populations of cooperatively foraging simulated robots, we found that historical contingency in the occurrence order of novel phenotypic traits resulted in the emergence of two distinct communication strategies. The more complex foraging strategy was less efficient than the simpler strategy. However, when the 20 populations were placed in competition with each other, the populations with the more complex strategy outperformed the populations with the less complex strategy. These results demonstrate a tradeoff between communication efficiency and robustness and suggest that stochastic events have important effects on signal evolution and the outcome of competition between distinct populations.

Learning and adaptation in physical heterogeneous teams of robots

In this paper we present a novel approach to assigning roles to robots in a team of physical heterogeneous robots. Its members compete for these roles and get rewards for them. The rewards are used to determine each agent’s preferences and which agents are better adapted to the environment. These aspects are included in the decision making process. Agent interactions are modelled using the concept of an ecosystem in which each robot is a species, resulting in emergent behaviour of the whole set of agents. One of the most important features of this approach is its high adaptability. Unlike some other learning techniques, this approach does not need to start a whole exploitation process when the environment changes. All this is exemplified by means of experiments run on a simulator. In addition, the algorithm developed was applied as applied to several teams of robots in order to analyse the impact of heterogeneity in these systems

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.

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.

Improving Offender Programming, Data Download, Iowa Department of Corrections, June 2012

In 2008, the Iowa Department of Corrections embarked on a comprehensive audit of all institutional andcommunity corrections offender programs that receive corrections funding. The audit focused on the degree towhich each program adheres to evidence-based practices principles (what works best). The audit areas are listedbelow along with some examples of the questions asked about each program:

La convivencia con los cyborgs y los robots: Consideraciones filosóficas, ético-morales y sociopolíticas

In this work, we present the cultural evolution that has allowed to overcome many problems derived from the limitations of the human body. These limitations have been solved by a"cyborization" process that began since early anthropogenesis. Originally, it was envisioned to deal with some diseases, accidents or body malfunctions. Nowadays, augmentations improve common human capabilities; one of the most notable is the increase of brain efficiency by using connections with a computer. A basic social question also addressed is which people will and should have access to these augmentations. Advanced humanoid robots (with human external aspect, artificial intelligence and even emotions) already exist and consequently a number of questions arise. For instance, will robots be considered living organisms? Could they be considered as persons? Will we confer the human status to robots? These questions are discussed. Our conclusions are that the advanced humanoid robots display some actions that may be considered as life-like, yet different to the life associated with living organisms, also, to some extend they could be considered as persons-like, but not humans.

Reflexiones sobre los cyborgs y los robots: evolucion humana y aumentacion

The human being has changed in time due to both, biological and cultural evolution. In a first step, biological evolution was the cornerstone of the changes in our species. However, cultural evolution was also a key element producing adaptations that allowed the evolution of modern human being. These adaptations include aspects as different as clothing, tools, reading and writing, calculation and some forms of rudimentary prosthesis. Technoscience has enhanced these adaptations that conduce to the concept of broad-sense cyborg. Present human society includes a huge proportion of these latter individuals. In this article we discuss this reality and the future of our society based on the interconnections between humans, cyborgs and robots.