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.

Splitting statistical potentials into meaningful scoring functions: testing the prediction of near-native structures from decoy conformations

Background: Recent advances on high-throughput technologies have produced a vast amount of protein sequences, while the number of high-resolution structures has seen a limited increase. This has impelled the production of many strategies to built protein structures from its sequence, generating a considerable amount of alternative models. The selection of the closest model to the native conformation has thus become crucial for structure prediction. Several methods have been developed to score protein models by energies, knowledge-based potentials and combination of both.Results: Here, we present and demonstrate a theory to split the knowledge-based potentials in scoring terms biologically meaningful and to combine them in new scores to predict near-native structures. Our strategy allows circumventing the problem of defining the reference state. In this approach we give the proof for a simple and linear application that can be further improved by optimizing the combination of Zscores. Using the simplest composite score () we obtained predictions similar to state-of-the-art methods. Besides, our approach has the advantage of identifying the most relevant terms involved in the stability of the protein structure. Finally, we also use the composite Zscores to assess the conformation of models and to detect local errors.Conclusion: We have introduced a method to split knowledge-based potentials and to solve the problem of defining a reference state. The new scores have detected near-native structures as accurately as state-of-art methods and have been successful to identify wrongly modeled regions of many near-native conformations.

Diseño, implementación y evaluación de un juego educativo basado en puzles con scaffolding orientado a la programación

Existe una falta de interés por parte de los estudiantes en el área de las Tecnologías de la Información y la Comunicación (TIC) que se ve reflejada en el descenso de las matriculaciones en este ámbito. El uso de metodologías de aprendizaje basadas en el Constructivismo combinadas con tecnología software, se ha observado que es una buena solución para afrontar dicha falta de interés. Sin embargo, actualmente no existen aplicaciones software que implementen estas metodologías pedagógicas y que proporcionen a los estudiantes los mecanismos de ayuda necesarios (Scaffolding) para darles soporte durante el aprendizaje de conceptos TIC. Una posible solución a este problema es el uso de juegos educativos, los cuáles implementarán técnicas de Scaffolding que den el soporte necesario al estudiante para alcanzarlos objetivos de aprendizaje fijados. Por tanto, en este proyecto se diseñará e implementará un juego educativo basado en puzles orientado a la Programación que estará basado en un método aprendizaje basado en el Constructivismo en el que el estudiante construye su propio conocimiento. Una vez implementado, será evaluado en un centro escolar por parte deestudiantes de últimos cursos de ESO o Bachillerato.

Taajuusmuuttajien suorituskyvyn automaattinen testausympäristö

Tämä insinöörityö tehtiin ABB Oy, Drivesin Product AC -tulosyksikön tuotekehitysosastolle Helsingissä. Työssä kehitettiin taajuusmuuttajien suorituskyvyn automaattinen testausympäristö. ABB:n taajuusmuuttajien suorituskykytestejä ei ole aikaisemmin automatisoitu. Testit on tehty käsin ja niiden suorittamiseen ja tulosten käsittelyyn on kulunut paljon aikaa. Automaattisella testauksella pyrittiin testien suorittamiseen ja tulosten käsittelyyn kuluvan ajan huomattavaan pienentymiseen. Työssä ei ollut tarkoituksena tehdä suorituskykytestejä vaan kehittää automaattinen testausympäristö eli suorituskykytestipenkki, jossa suorituskykytestit on mahdollista suorittaa. Työssä keskityttiin taajuusmuuttajan nopeus- ja momenttisäätäjien suorituskykyyn. Työ toteutettiin suunnittelu- ja ohjelmointityönä. Testausympäristön laitteisto perustuu ABB:n tuotekehityslaboratorioiden olemassaoleviin testipaikkoihin. Testausympäristössä käytetään taajuusmuuttajien lisäksi pääasiassa kolmivaiheisia oikosulkumoottoreita. Lisäksi laitteistoon kuuluu ACS800-sarjan taajuusmuuttaja kuormakäyttönä, momenttianturi ja takometri eli kierrosnopeusmittari. Ohjelmointi tehtiin National Instrumentsin LabVIEW-ohjelmointiympäristön versiolla 8.0. Testausympäristön käyttöliittymänä toimii saman yrityksen TestStand-testausohjelmiston versio 3.5. Testattavien taajuusmuuttajien ohjausta ja momenttianturin lukemista varten ohjelmoitiin virtuaali-instrumentteja. Virtuaali-instrumentteja kutsutaan TestStand-testisekvensseistä. Testisekvenssit luodaan TestStandin sekvenssieditorilla ja suoritetaan sekvenssieditorissa tai operaattorin käyttöliittymässä. Työn tuloksena syntyi taajuusmuuttajien suorituskyvyn automaattinen testausympäristö. Testausympäristöä voidaan hyödyntää sekä nykyisen että seuraavan sukupolven taajuusmuuttajien testauksessa. Sillä on mahdollista suorittaa yleisimmät taajuusmuuttajien suorituskykytestit, kuten nopeus- ja momenttisäätöjen staattinen ja dynaaminen tarkkuus, hyvin kattavasti. Testit voidaan automaattisesti suorittaa koko testikäytön sallimalla pyörimisnopeus- ja kuormitusalueella. Näytteenottotaajuus voi olla enintään 1 kHz luettaessa pyörimisnopeutta ACS800-sarjan taajuusmuuttajan kautta ja momenttianturia samanaikaisesti. Virtuaali-instrumenteista koostuvia testisekvenssejä voidaan vapaasti muokata ja kehittää testejä edelleen tai luoda kokonaan uusia testejä. Testausympäristö perustuu teollisuudessa yleisesti käytettyihin ohjelmistoihin ja tarjoaa hyvät mahdollisuudet jatkokehitykselle.

Testing the predictive adaptive response in a host-parasite system

1. Harsh environmental conditions experienced during development can reduce the performance of the same individuals in adulthood. However, the 'predictive adaptive response' hypothesis postulates that if individuals adapt their phenotype during development to the environments where they are likely to live in the future, individuals exposed to harsh conditions in early life perform better when encountering the same harsh conditions in adulthood compared to those never exposed to these conditions before. 2. Using the common vole (Microtus arvalis) as study organism, we tested how exposure to flea parasitism during the juvenile stage affects the physiology (haematocrit, resistance to oxidative stress, resting metabolism, spleen mass, and testosterone), morphology (body mass, testis mass) and motor performance (open field activity and swimming speed) of the same individuals when infested with fleas in adulthood. According to the 'predictive adaptive response' hypothesis, we predicted that voles parasitized at the adult stage would perform better if they had already been parasitized with fleas at the juvenile stage. 3. We found that voles exposed to fleas in adulthood had a higher metabolic rate if already exposed to fleas when juvenile, compared to voles free of fleas when juvenile and voles free of fleas in adulthood. Independently of juvenile parasitism, adult parasitism impaired adult haematocrit and motor performances. Independently of adult parasitism, juvenile parasitism slowed down crawling speed in adult female voles. 4. Our results suggest that juvenile parasitism has long-term effects that do not protect from the detrimental effects of adult parasitism. On the contrary, experiencing parasitism in early-life incurs additional costs upon adult parasitism measured in terms of higher energy expenditure, rather than inducing an adaptive shift in the developmental trajectory. 5. Hence, our study provides experimental evidence for long term costs of parasitism. We found no support for a predictive adaptive response in this host-parasite system.

Cognitive stimulation through task-oriented telerobotics

The project presented, iCognos, consists of a flexible platform to assist end-users in performing a series of mental tasks with a sensitized mobile telerobotic platform aimed at mitigating the problems associated to cognitive disorders with an ecological cognition approach.

Testing new identity models and processes in French-speaking adolescents and emerging adults students

Developing a sense of identity is a crucial psychosocial task for young people. The purpose of this study was to evaluate identity development in French-speaking adolescents and emerging adults (in France and Switzerland) using a process-oriented model of identity formation including five dimensions (i.e., exploration in breadth, commitment making, exploration in depth, identification with commitment, and ruminative exploration). The study included participants from three different samples (total N = 2239, 66.7% women): two samples of emerging adult student and one sample of adolescents. Results confirmed the hypothesized five-factor dimensional model of identity in our three samples and provided evidence for convergent validity of the model. The results also indicated that exploration in depth might be subdivided in two aspects: a first form of exploration in depth leading to a better understanding and to an increase of the strength of current commitments and a second form of exploration in depth leading to a re-evaluation and a reconsideration of current commitments. Further, the identity status cluster solution that emerged is globally in line with previous literature (i.e., achievement, foreclosure, moratorium, carefree diffusion, diffused diffusion, undifferentiated). However, despite a structural similarity, we found variations in identity profiles because identity development is shaped by cultural context. These specific variations are discussed in light of social, educational and economic differences between France and the French-speaking part of Switzerland. Implications and suggestions for future research are offered.

Stepwise multiple testing as formalized data snooping

It is common in econometric applications that several hypothesis tests arecarried out at the same time. The problem then becomes how to decide whichhypotheses to reject, accounting for the multitude of tests. In this paper,we suggest a stepwise multiple testing procedure which asymptoticallycontrols the familywise error rate at a desired level. Compared to relatedsingle-step methods, our procedure is more powerful in the sense that itoften will reject more false hypotheses. In addition, we advocate the useof studentization when it is feasible. Unlike some stepwise methods, ourmethod implicitly captures the joint dependence structure of the teststatistics, which results in increased ability to detect alternativehypotheses. We prove our method asymptotically controls the familywise errorrate under minimal assumptions. We present our methodology in the context ofcomparing several strategies to a common benchmark and deciding whichstrategies actually beat the benchmark. However, our ideas can easily beextended and/or modied to other contexts, such as making inference for theindividual regression coecients in a multiple regression framework. Somesimulation studies show the improvements of our methods over previous proposals. We also provide an application to a set of real data.

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.

Exact and approximate stepdown methods for multiple hypothesis testing

Consider the problem of testing k hypotheses simultaneously. In this paper,we discuss finite and large sample theory of stepdown methods that providecontrol of the familywise error rate (FWE). In order to improve upon theBonferroni method or Holm's (1979) stepdown method, Westfall and Young(1993) make eective use of resampling to construct stepdown methods thatimplicitly estimate the dependence structure of the test statistics. However,their methods depend on an assumption called subset pivotality. The goalof this paper is to construct general stepdown methods that do not requiresuch an assumption. In order to accomplish this, we take a close look atwhat makes stepdown procedures work, and a key component is a monotonicityrequirement of critical values. By imposing such monotonicity on estimatedcritical values (which is not an assumption on the model but an assumptionon the method), it is demonstrated that the problem of constructing a validmultiple test procedure which controls the FWE can be reduced to the problemof contructing a single test which controls the usual probability of a Type 1error. This reduction allows us to draw upon an enormous resamplingliterature as a general means of test contruction.

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.

Metaheuristics for the bus-driver scheduling problem

We present new metaheuristics for solving real crew scheduling problemsin a public transportation bus company. Since the crews of thesecompanies are drivers, we will designate the problem by the bus-driverscheduling problem. Crew scheduling problems are well known and severalmathematical programming based techniques have been proposed to solvethem, in particular using the set-covering formulation. However, inpractice, there exists the need for improvement in terms of computationalefficiency and capacity of solving large-scale instances. Moreover, thereal bus-driver scheduling problems that we consider can present variantaspects of the set covering, as for example a different objectivefunction, implying that alternative solutions methods have to bedeveloped. We propose metaheuristics based on the following approaches:GRASP (greedy randomized adaptive search procedure), tabu search andgenetic algorithms. These metaheuristics also present some innovationfeatures based on and genetic algorithms. These metaheuristics alsopresent some innovation features based on the structure of the crewscheduling problem, that guide the search efficiently and able them tofind good solutions. Some of these new features can also be applied inthe development of heuristics to other combinatorial optimizationproblems. A summary of computational results with real-data problems ispresented.