Inexact uniformization method for computing transient distributions of Markov chains

The uniformization method (also known as randomization) is a numerically stable algorithm for computing transient distributions of a continuous time Markov chain. When the solution is needed after a long run or when the convergence is slow, the uniformization method involves a large number of matrix-vector products. Despite this, the method remains very popular due to its ease of implementation and its reliability in many practical circumstances. Because calculating the matrix-vector product is the most time-consuming part of the method, overall efficiency in solving large-scale problems can be significantly enhanced if the matrix-vector product is made more economical. In this paper, we incorporate a new relaxation strategy into the uniformization method to compute the matrix-vector products only approximately. We analyze the error introduced by these inexact matrix-vector products and discuss strategies for refining the accuracy of the relaxation while reducing the execution cost. Numerical experiments drawn from computer systems and biological systems are given to show that significant computational savings are achieved in practical applications.

Identifying optimal lipid raft characteristics required to promote nanoscale protein-protein interactions on the plasma membrane

The dynamic lateral segregation of signaling proteins into microdomains is proposed to facilitate signal transduction, but the constraints on microdomain size, mobility, and diffusion that might realize this function are undefined. Here we interrogate a stochastic spatial model of the plasma membrane to determine how microdomains affect protein dynamics. Taking lipid rafts as representative microdomains, we show that reduced protein mobility in rafts segregates dynamically partitioning proteins, but the equilibrium concentration is largely independent of raft size and mobility. Rafts weakly impede small-scale protein diffusion but more strongly impede long-range protein mobility. The long-range mobility of raft-partitioning and raft-excluded proteins, however, is reduced to a similar extent. Dynamic partitioning into rafts increases specific interprotein collision rates, but to maximize this critical, biologically relevant function, rafts must be small (diameter, 6 to 14 nm) and mobile. Intermolecular collisions can also be favored by the selective capture and exclusion of proteins by rafts, although this mechanism is generally less efficient than simple dynamic partitioning. Generalizing these results, we conclude that microdomains can readily operate as protein concentrators or isolators but there appear to be significant constraints on size and mobility if microdomains are also required to function as reaction chambers that facilitate nanoscale protein-protein interactions. These results may have significant implications for the many signaling cascades that are scaffolded or assembled in plasma membrane microdomains.

Resource allocation and scheduling of multiple composite web services in cloud computing using cooperative coevolution genetic algorithm

In cloud computing, resource allocation and scheduling of multiple composite web services is an important and challenging problem. This is especially so in a hybrid cloud where there may be some low-cost resources available from private clouds and some high-cost resources from public clouds. Meeting this challenge involves two classical computational problems: one is assigning resources to each of the tasks in the composite web services; the other is scheduling the allocated resources when each resource may be used by multiple tasks at different points of time. In addition, Quality-of-Service (QoS) issues, such as execution time and running costs, must be considered in the resource allocation and scheduling problem. Here we present a Cooperative Coevolutionary Genetic Algorithm (CCGA) to solve the deadline-constrained resource allocation and scheduling problem for multiple composite web services. Experimental results show that our CCGA is both efficient and scalable.

Stochastic models and simulation of ion channel dynamics

The behaviour of ion channels within cardiac and neuronal cells is intrinsically stochastic in nature. When the number of channels is small this stochastic noise is large and can have an impact on the dynamics of the system which is potentially an issue when modelling small neurons and drug block in cardiac cells. While exact methods correctly capture the stochastic dynamics of a system they are computationally expensive, restricting their inclusion into tissue level models and so approximations to exact methods are often used instead. The other issue in modelling ion channel dynamics is that the transition rates are voltage dependent, adding a level of complexity as the channel dynamics are coupled to the membrane potential. By assuming that such transition rates are constant over each time step, it is possible to derive a stochastic differential equation (SDE), in the same manner as for biochemical reaction networks, that describes the stochastic dynamics of ion channels. While such a model is more computationally efficient than exact methods we show that there are analytical problems with the resulting SDE as well as issues in using current numerical schemes to solve such an equation. We therefore make two contributions: develop a different model to describe the stochastic ion channel dynamics that analytically behaves in the correct manner and also discuss numerical methods that preserve the analytical properties of the model.

Computing with motile bio-agents

We describe a model of computation of the parallel type, which we call 'computing with bio-agents', based on the concept that motions of biological objects such as bacteria or protein molecular motors in confined spaces can be regarded as computations. We begin with the observation that the geometric nature of the physical structures in which model biological objects move modulates the motions of the latter. Consequently, by changing the geometry, one can control the characteristic trajectories of the objects; on the basis of this, we argue that such systems are computing devices. We investigate the computing power of mobile bio-agent systems and show that they are computationally universal in the sense that they are capable of computing any Boolean function in parallel. We argue also that using appropriate conditions, bio-agent systems can solve NP-complete problems in probabilistic polynomial time.

Augmenting mobile computing with video game elements to support, motivate and engage young people in educational, real-world events

Video games have shown great potential as tools that both engage and motivate players to achieve tasks and build communities in fantasy worlds. We propose that the application of game elements to real world activities can aid in delivering contextual information in interesting ways and help young people to engage in everyday events. Our research will explore how we can unite utility and fun to enhance information delivery, encourage participation, build communities and engage users with utilitarian events situated in the real world. This research aims to identify key game elements that work effectively to engage young digital natives, and provide guidelines to influence the design of interactions and interfaces for event applications in the future. This research will primarily contribute to areas of user experience and pervasive gaming.

Bridging the representation and interaction challenges of mobile context-aware computing: designing agile ridesharing

The increasing capability of mobile devices and social networks to gather contextual and social data has led to increased interest in context-aware computing for mobile applications. This paper explores ways of reconciling two different viewpoints of context, representational and interactional, that have arisen respectively from technical and social science perspectives on context-aware computing. Through a case study in agile ridesharing, the importance of dynamic context control, historical context and broader context is discussed. We build upon earlier work that has sought to address the divide by further explicating the problem in the mobile context and expanding on the design approaches.