Research in the last few decades has revealed the great capacity of the RNA molecule. RNA, which previously was assumed to play a main role only as an intermediate in the translation of genes to proteins, is today known to play many important roles in the cell in addition to that as a messenger RNA and transfer RNA, including the ability to catalyze reactions and gene regulations at various levels. This thesis investigates several computational aspects of RNA. We will discuss identification of novel RNAs and RNAs that are known to exist in related species, RNA secondary structure prediction, as well as more general tools for analyzing, visualizing and classifying RNA sequences. We present two benchmark studies concerning RNA identification, both de novo identification/characterization of single RNA sequences and homology search methods. We develope a novel algorithm for analysis of the RNA folding landscape that is based on the nearest neighbor energy model adopted in many secondary structure prediction programs. We implement this algorithm, which computes structural neighbors of a given RNA secondary structure, in the program RNAbor, which is accessible on a web server. Furthermore, we combine a mutual information based structure prediction algorithm with a sequence logo visualization to create a novel visualization tool for analyzing an RNA alignment and identifying covarying sites. Finally, we present extensions to sequence logos for the purpose of tRNA identity analysis. We introduce function logos, which display features that distinguish functional subclasses within a large set of structurally related sequences, as well as the inverse logos, which display underrepresented features. For the purpose of comparing tRNA identity elements between different taxa we introduce two contrasting logos, the information difference and the Kullback-Leibler divergence difference logos.

Trucks are responsible for the major part of inland freight and so, they are a backbone of the modern economy but they are also a large consumer of energy. In this context, a dominating vehicle is a truck with heavy load on a long trip. The aim with look-ahead control is to reduce the energy consumption of heavy vehicles by utilizing information about future conditions focusing on the road topography ahead of the vehicle. The possible gains with look-ahead control are evaluated by performing experiments with a truck on highway. A real-time control system based on receding horizon control (RHC) is set up where the optimization problem is solved repeatedly on-line for a certain horizon ahead of the vehicle. The experimental results show that significant reductions of the fuel consumption are achieved, and that the controller structure, where the algorithm calculates set points fed to lower level controllers, has satisfactory robustness to perform well on-board in a real environment. Moreover, the controller behavior has the preferred property of being intuitive, and the behavior is perceived as comfortable and natural by participating drivers and passengers. A well-behaved and efficient algorithm is developed, based on dynamic programing, for the mixed-integer nonlinear minimum-fuel problem. A modeling framework is formulated where special attention is given to properly include gear shifting with physical models. Fuel equivalents are used to reformulate the problem into a tractable form and to construct a residual cost enabling the use of a shorter horizon ahead of the vehicle. Analysis of errors due to discretization of the continuous dynamics and due to interpolation shows that an energy formulation is beneficial for reducing both error sources. The result is an algorithm giving accurate solutions with low computational effort for use in an on-board controller for a fuel-optimal velocity profile and gear selection. The prevailing approach for the look-ahead problem is RHC where main topics are the approximation of the residual cost and the choice of the horizon length. These two topics are given a thorough investigation independent of the method of solving the optimal control problem in each time step. The basis for the fuel equivalents and the residual cost is formed from physical intuition as well as mathematical interpretations in terms of the Lagrange multipliers used in optimization theory. Measures for suboptimality are introduced that enables choosing horizon length with the appropriate compromise between fuel consumption and trip time. Control of a hybrid electric powertrain is put in the framework together with control of velocity and gear. For an efficient solution of the minimum-fuel problem in this case, more fuel equivalence factors and an energy formulation are employed. An application is demonstrated in a design study where it is shown how the optimal trade-off between size and capacity of the electrical system depends on road characteristics, and also that a modestly sized electrical system achieves most of the gain. The contributions develop algorithms, create associated design tools, and carry out experiments. Altogether, a feasible framework is achieved that pave the way for on-board fuel-optimal look-ahead control.

Stochastic dynamic programming is a recursive method for solving sequential or multistage decision problems. It helps economists and mathematicians construct and solve a huge variety of sequential decision making problems in stochastic cases. Research on stochastic dynamic programming is important and meaningful because stochastic dynamic programming reflects the behavior of the decision maker without risk aversion; i.e., decision making under uncertainty. In the solution process, it is extremely difficult to represent the existing or future state precisely since uncertainty is a state of having limited knowledge. Indeed, compared to the deterministic case, which is decision making under certainty, the stochastic case is more realistic and gives more accurate results because the majority of problems in reality inevitably have many unknown parameters. In addition, time scale calculus theory is applicable to any field in which a dynamic process can be described with discrete or continuous models. Many stochastic dynamic models are discrete or continuous, so the results of time scale calculus are directly applicable to them as well. The aim of this thesis is to introduce a general form of a stochastic dynamic sequence problem on complex discrete time domains and to find the optimal sequence which maximizes the sequence problem.

This thesis studies the interaction between new and used durable goods without physical depreciation. In product categories such as CDs/DVDs and video games, the competition from used goods markets has been viewed as a serious problem by producers. These products physically depreciate negligibly, but owners' consumption values could depreciate quickly due to satiation. Consequently, used goods that are almost identical to new goods may become available immediately after a new product release. However, the existence of used goods markets also provides consumers with a selling opportunity. If consumers are forward-looking and account for the future resale value of a product in their buying decision, used goods markets could increase the sales of new goods. Thus, whether used good markets are harmful or beneficial to new-good producers is an empirical question. To tackle this question, I extend the previous literature in three ways. First, I assemble a new data set from the Japanese video game market. This unique data set includes not only the sales and prices of new and used goods, but also the resale value of used copies, the quantity of used copies retailers purchased from consumers, and the inventory level of used copies at retailers. Second, I develop a structural model of forward-looking consumers that incorporates (i) new and used goods buying decisions, (ii) used goods selling decisions, (iii) consumer expectations about future prices of new and used goods as well as resale values of used goods, and (iv) the depreciation of both owners' and potential buyers' consumption values. Third, I develop a new Bayesian estimation method to estimate my model. In particular, my method can alleviate the computational burden of estimating non-stationary discrete choice dynamic programming models with continuous state variables that evolve stochastically over time. The estimation results suggest that consumers are forward-looking in the Japanese video game market and the substitutability between new and used video games is quite low. Using the estimates, I quantify the impact of eliminating the used video game market on new-game revenues. I find that the elimination of used video game market could reduce the revenue for a new game.

Battery energy management plays a crucial role in fuel economy improvement of charge-sustaining parallel hybrid electric vehicles. Currently available control strategies consider battery state of charge (SOC) and driver’s request through the pedal input in decision-making. This method does not achieve an optimal performance for saving fuel or maintaining appropriate SOC level, especially during the operation in extreme driving conditions or hilly terrain. The objective of this thesis is to develop a control algorithm using forthcoming traffic condition and road elevation, which could be fed from navigation systems. This would enable the controller to predict potential of regenerative charging to capture cost-free energy and intentionally depleting battery energy to assist an engine at high power demand. The starting point for this research is the modelling of a small sport-utility vehicle by the analysis of the vehicles currently available in the market. The result of the analysis is used in order to establish a generic mild hybrid powertrain model, which is subsequently examined to compare the performance of controllers. A baseline is established with a conventional powertrain equipped with a spark ignition direct injection engine and a continuously variable transmission. Hybridisation of this vehicle with an integrated starter alternator and a traditional rule-based control strategy is presented. Parameter optimisation in four standard driving cycles is explained, followed by a detailed energy flow analysis. An additional potential improvement is presented by dynamic programming (DP), which shows a benefit of a predictive control. Based on these results, a predictive control algorithm using fuzzy logic is introduced. The main tools of the controller design are the DP, adaptive-network-based fuzzy inference system with subtractive clustering and design of experiment. Using a quasi-static backward simulation model, the performance of the controller is compared with the result from the instantaneous control and the DP. The focus is fuel saving and SOC control at the end of journeys, especially in aggressive driving conditions and a hilly road. The controller shows a good potential to improve fuel economy and tight SOC control in long journey and hilly terrain. Fuel economy improvement and SOC correction are close to the optimal solution by the DP, especially in long trips on steep road where there is a large gap between the baseline controller and the DP. However, there is little benefit in short trips and flat road. It is caused by the low improvement margin of the mild hybrid powertrain and the limited future journey information. To provide a further step to implementation, a software-in-the-loop simulation model is developed. A fully dynamic model of the powertrain and the control algorithm are implemented in AMESim-Simulink co-simulation environment. This shows small deterioration of the control performance by driver’s pedal action, powertrain dynamics and limited computational precision on the controller performance.

This thesis studies the interaction between new and used durable goods without physical depreciation. In product categories such as CDs/DVDs and video games, the competition from used goods markets has been viewed as a serious problem by producers. These products physically depreciate negligibly, but owners' consumption values could depreciate quickly due to satiation. Consequently, used goods that are almost identical to new goods may become available immediately after a new product release. However, the existence of used goods markets also provides consumers with a selling opportunity. If consumers are forward-looking and account for the future resale value of a product in their buying decision, used goods markets could increase the sales of new goods. Thus, whether used good markets are harmful or beneficial to new-good producers is an empirical question. To tackle this question, I extend the previous literature in three ways. First, I assemble a new data set from the Japanese video game market. This unique data set includes not only the sales and prices of new and used goods, but also the resale value of used copies, the quantity of used copies retailers purchased from consumers, and the inventory level of used copies at retailers. Second, I develop a structural model of forward-looking consumers that incorporates (i) new and used goods buying decisions, (ii) used goods selling decisions, (iii) consumer expectations about future prices of new and used goods as well as resale values of used goods, and (iv) the depreciation of both owners' and potential buyers' consumption values. Third, I develop a new Bayesian estimation method to estimate my model. In particular, my method can alleviate the computational burden of estimating non-stationary discrete choice dynamic programming models with continuous state variables that evolve stochastically over time. The estimation results suggest that consumers are forward-looking in the Japanese video game market and the substitutability between new and used video games is quite low. Using the estimates, I quantify the impact of eliminating the used video game market on new-game revenues. I find that the elimination of used video game market could reduce the revenue for a new game.

The concept of dynamic programming was originally used in late 1949, mostly during the 1950s, by Richard Bellman to describe decision making problems. By 1952, he refined this to the modern meaning, referring specifically to nesting smaller decision problems inside larger decisions. Also, the Bellman equation, one of the basic concepts in dynamic programming, is named after him. Dynamic programming has become an important argument which was used in various fields; such as, economics, finance, bioinformatics, aerospace, information theory, etc. Since Richard Bellman's invention of dynamic programming, economists and mathematicians have formulated and solved a huge variety of sequential decision making problems both in deterministic and stochastic cases; either finite or infinite time horizon. This thesis is comprised of five chapters where the major objective is to study both deterministic and stochastic dynamic programming models in finance. In the first chapter, we give a brief history of dynamic programming and we introduce the essentials of theory. Unlike economists, who have analyzed the dynamic programming on discrete, that is, periodic and continuous time domains, we claim that trading is not a reasonably periodic or continuous act. Therefore, it is more accurate to demonstrate the dynamic programming on non-periodic time domains. In the second chapter we introduce time scales calculus. Moreover, since it is more realistic to analyze a decision maker’s behavior without risk aversion, we give basics of Stochastic Calculus in this chapter. After we introduce the necessary background, in the third chapter we construct the deterministic dynamic sequence problem on isolated time scales. Then we derive the corresponding Bellman equation for the sequence problem. We analyze the relation between solutions of the sequence problem and the Bellman equation through the principle of optimality. We give an example of the deterministic model in finance with all details of calculations by using guessing method, and we prove uniqueness and existence of the solution by using the Contraction Mapping Theorem. In the fourth chapter, we define the stochastic dynamic sequence problem on isolated time scales. Then we derive the corresponding stochastic Bellman equation. As in the deterministic case, we give an example in finance with the distributions of solutions.

The minimum set cover problem is, without question, among the most ubiquitous and well-studied problems in computer science. Its theoretical hardness has been fully characterized--logarithmic approximability has been established, and no sublogarithmic approximation exists unless P=NP. However, the gap between real-world instances and the theoretical worst case is often immense--many covering problems of practical relevance admit much better approximations, or even solvability in polynomial time. Simple combinatorial or geometric structure can often be exploited to obtain improved algorithms on a problem-by-problem basis, but there is no general method of determining the extent to which this is possible. In this thesis, we aim to shed light on the relationship between the structure and the hardness of covering problems. We discuss several measures of structural complexity of set cover instances and prove new algorithmic and hardness results linking the approximability of a set cover problem to its underlying structure. In particular, we provide: - An APX-hardness proof for a wide family of problems that encode a simple covering problem known as Special-3SC. - A class of polynomial dynamic programming algorithms for a group of weighted geometric set cover problems having simple structure. - A simplified quasi-uniform sampling algorithm that yields improved approximations for weighted covering problems having low cell complexity or geometric union complexity. - Applications of the above to various capacitated covering problems via linear programming strengthening and rounding. In total, we obtain new results for dozens of covering problems exhibiting geometric or combinatorial structure. We tabulate these problems and classify them according to their approximability.

This thesis considers the problem of performance modeling, analysis and control of capacitated re-entrant lines. Specifically, the first part of the thesis develops an analytical framework for the modeling, analysis and control of capacitated re-entrant lines, which is based on Generalized Stochastic Petri nets (GSPN) framework. The corresponding scheduling problem is systematically formulated, and the structure of the optimal policy is characterized and compared to that identified for "traditional" re-entrant lines. The second part of thesis addresses the problem of developing a systematic and computationally effective method for computing the optimal scheduling policy for any given configuration of capacitated re-entrant line. Specifically, the underlying scheduling problem is transformed to a Markov Decision Process (MDP) problem and an algorithm that systematically generates the MDP formulation for any given fab configuration is developed. The third part of thesis develops an effective approximating scheme based on the Neuro-Dynamic Programming (NDP) theory. In its general definition, the NDP method seeks the approximation of the optimal relative value function of the underlying MDP formulation by a parameterized function. Hence, an approximating structure for the considered problem is proposed and the quality of the generated approximations is systematically assessed. More specifically, this part of the thesis develops a set of "feature" functions and the mathematical apparatus necessary to evaluate the considered approximating scheme through a numerical experiment. The obtained results indicate that good quality approximations can be achieved by considering a set of features that characterize the distribution of the running process instances to the various processing stages and their lower order interactions. The last part of the thesis exploits the performance models developed in its earlier parts in order to provide an analytical characterization of the optimality of various deadlock resolution strategies for Markovian resource allocation systems under the objective of maximizing throughput.

A Web-server farm is a specialized facility designed specifically for housing Web servers catering to one or more Internet facing Web sites. In this dissertation, stochastic dynamic programming technique is used to obtain the optimal admission control policy with different classes of customers, and stochastic uid- ow models are used to compute the performance measures in the network. The two types of network traffic considered in this research are streaming (guaranteed bandwidth per connection) and elastic (shares available bandwidth equally among connections). We first obtain the optimal admission control policy using stochastic dynamic programming, in which, based on the number of requests of each type being served, a decision is made whether to allow or deny service to an incoming request. In this subproblem, we consider a xed bandwidth capacity server, which allocates the requested bandwidth to the streaming requests and divides all of the remaining bandwidth equally among all of the elastic requests. The performance metric of interest in this case will be the blocking probability of streaming traffic, which will be computed in order to be able to provide Quality of Service (QoS) guarantees. Next, we obtain bounds on the expected waiting time in the system for elastic requests that enter the system. This will be done at the server level in such a way that the total available bandwidth for the requests is constant. Trace data will be converted to an ON-OFF source and fluid- flow models will be used for this analysis. The results are compared with both the mean waiting time obtained by simulating real data, and the expected waiting time obtained using traditional queueing models. Finally, we consider the network of servers and routers within the Web farm where data from servers flows and merges before getting transmitted to the requesting users via the Internet. We compute the waiting time of the elastic requests at intermediate and edge nodes by obtaining the distribution of the out ow of the upstream node. This out ow distribution is obtained by using a methodology based on minimizing the deviations from the constituent in flows. This analysis also helps us to compute waiting times at different bandwidth capacities, and hence obtain a suitable bandwidth to promise or satisfy the QoS guarantees. This research helps in obtaining performance measures for different traffic classes at a Web-server farm so as to be able to promise or provide QoS guarantees; while at the same time helping in utilizing the resources of the server farms efficiently, thereby reducing the operational costs and increasing energy savings.