Inferring biochemical routes from biochemical networks

Metabolism is a defining feature of life, and its study is important to understand how a cell works, alterations that lead to disease and for applications in drug discovery. From a systems perspective, metabolism can be represented as a network that captures all the metabolites as nodes and the inter-conversions among pairs of them as edges. Such an abstraction enables the networks to be studied by applying graph theory, particularly, to infer the flow of chemical information in the networks by identifying relevant metabolic pathways. In this study, different weighting schemes are used to illustrate that appropriately weighted networks can capture the quantitative cellular dynamics quite accurately. Thus, the networks now combine the elegance and simplicity of representation of the system and ease of analysing metabolic graphs. Metabolic routes or paths determined by this therefore are likely to be more biologically meaningful. The usefulness of the approach is demonstrated with two examples, first for understanding bacterial stress response and second for studying metabolic alterations that occurs in cancer cells.

Precoding-Based Network Alignment Using Transform Approach for Acyclic Networks With Delay

The algebraic formulation for linear network coding in acyclic networks with the links having integer delay is well known. Based on this formulation, for a given set of connections over an arbitrary acyclic network with integer delay assumed for the links, the output symbols at the sink nodes, at any given time instant, is a F(p)m-linear combination of the input symbols across different generations, where F(p)m denotes the field over which the network operates (p is prime and m is a positive integer). We use finite-field discrete Fourier transform to convert the output symbols at the sink nodes, at any given time instant, into a F(p)m-linear combination of the input symbols generated during the same generation without making use of memory at the intermediate nodes. We call this as transforming the acyclic network with delay into n-instantaneous networks (n is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (nontransform) approach if and only if there exists a network code satisfying sink demands in the transform approach. When the zero-interference conditions are not satisfied, we propose three precoding-based network alignment (PBNA) schemes for three-source three-destination multiple unicast network with delays (3-S 3-D MUN-D) termed as PBNA using transform approach and time-invariant local encoding coefficients (LECs), PBNA using time-varying LECs, and PBNA using transform approach and block time-varying LECs. We derive sets of necessary and sufficient conditions under which throughputs close to n' + 1/2n' + 1, n'/2n' + 1, and n'/2n' + 1 are achieved for the three source-destination pairs in a 3-S 3-D MUN-D employing PBNA using transform approach and time-invariant LECs, and PBNA using transform approach and block time-varying LECs, where n' is a positive integer. For PBNA using time-varying LECs, we obtain a sufficient condition under which a throughput demand of n(1)/n, n(2)/n, and n(3)/n can be met for the three source-destination pairs in a 3-S 3-D MUN-D, where n(1), n(2), and n(3) are positive integers less than or equal to the positive integer n. This condition is also necessary when n(1) + n(3) = n(1) + n(2) = n where n(1) >= n(2) >= n(3).

Co-Evolution of Content Spread and Popularity in Mobile Opportunistic Networks

We consider a setting in which a single item of content is disseminated in a population of mobile nodes by opportunistic copying when pairs of nodes come in radio contact. The nodes in the population may either be interested in receiving the content (referred to as destinations) or not yet interested in receiving the content (referred to as relays). We consider a model for the evolution of popularity, the process by which relays get converted into destinations. A key contribution of our work is to model and study the joint evolution of content popularity and its spread in the population. Copying the content to relay nodes is beneficial since they can help spread the content to destinations, and could themselves be converted into destinations. We derive a fluid limit for the joint evolution model and obtain optimal policies for copying to relay nodes in order to deliver content to a desired fraction of destinations, while limiting the fraction of relay nodes that get the content but never turn into destinations. We prove that a time-threshold policy is optimal for controlling the copying to relays, i.e., there is an optimal time-threshold up to which all opportunities for copying to relays are exploited, and after which relays are not copied to. We then utilize simulations and numerical evaluations to provide insights into the effects of various system parameters on the optimally controlled co-evolution model.

BELIEF PROPAGATION FOR OPTIMAL EDGE COVER IN THE RANDOM COMPLETE GRAPH

We apply the objective method of Aldous to the problem of finding the minimum-cost edge cover of the complete graph with random independent and identically distributed edge costs. The limit, as the number of vertices goes to infinity, of the expected minimum cost for this problem is known via a combinatorial approach of Hessler and Wastlund. We provide a proof of this result using the machinery of the objective method and local weak convergence, which was used to prove the (2) limit of the random assignment problem. A proof via the objective method is useful because it provides us with more information on the nature of the edge's incident on a typical root in the minimum-cost edge cover. We further show that a belief propagation algorithm converges asymptotically to the optimal solution. This can be applied in a computational linguistics problem of semantic projection. The belief propagation algorithm yields a near optimal solution with lesser complexity than the known best algorithms designed for optimality in worst-case settings.

Social insect colony as a biological regulatory system: modelling information flow in dominance networks

Social insects provide an excellent platform to investigate flow of information in regulatory systems since their successful social organization is essentially achieved by effective information transfer through complex connectivity patterns among the colony members. Network representation of such behavioural interactions offers a powerful tool for structural as well as dynamical analysis of the underlying regulatory systems. In this paper, we focus on the dominance interaction networks in the tropical social wasp Ropalidia marginata-a species where behavioural observations indicate that such interactions are principally responsible for the transfer of information between individuals about their colony needs, resulting in a regulation of their own activities. Our research reveals that the dominance networks of R. marginata are structurally similar to a class of naturally evolved information processing networks, a fact confirmed also by the predominance of a specific substructure-the `feed-forward loop'-a key functional component in many other information transfer networks. The dynamical analysis through Boolean modelling confirms that the networks are sufficiently stable under small fluctuations and yet capable of more efficient information transfer compared to their randomized counterparts. Our results suggest the involvement of a common structural design principle in different biological regulatory systems and a possible similarity with respect to the effect of selection on the organization levels of such systems. The findings are also consistent with the hypothesis that dominance behaviour has been shaped by natural selection to co-opt the information transfer process in such social insect species, in addition to its primal function of mediation of reproductive competition in the colony.

Two timescale convergent Q-learning for sleep-scheduling in wireless sensor networks

In this paper, we consider an intrusion detection application for Wireless Sensor Networks. We study the problem of scheduling the sleep times of the individual sensors, where the objective is to maximize the network lifetime while keeping the tracking error to a minimum. We formulate this problem as a partially-observable Markov decision process (POMDP) with continuous stateaction spaces, in a manner similar to Fuemmeler and Veeravalli (IEEE Trans Signal Process 56(5), 2091-2101, 2008). However, unlike their formulation, we consider infinite horizon discounted and average cost objectives as performance criteria. For each criterion, we propose a convergent on-policy Q-learning algorithm that operates on two timescales, while employing function approximation. Feature-based representations and function approximation is necessary to handle the curse of dimensionality associated with the underlying POMDP. Our proposed algorithm incorporates a policy gradient update using a one-simulation simultaneous perturbation stochastic approximation estimate on the faster timescale, while the Q-value parameter (arising from a linear function approximation architecture for the Q-values) is updated in an on-policy temporal difference algorithm-like fashion on the slower timescale. The feature selection scheme employed in each of our algorithms manages the energy and tracking components in a manner that assists the search for the optimal sleep-scheduling policy. For the sake of comparison, in both discounted and average settings, we also develop a function approximation analogue of the Q-learning algorithm. This algorithm, unlike the two-timescale variant, does not possess theoretical convergence guarantees. Finally, we also adapt our algorithms to include a stochastic iterative estimation scheme for the intruder's mobility model and this is useful in settings where the latter is not known. Our simulation results on a synthetic 2-dimensional network setting suggest that our algorithms result in better tracking accuracy at the cost of only a few additional sensors, in comparison to a recent prior work.

An Eigen Approach to Transmit Beamforming in Wireless Networks With Single Antenna Receivers

In this paper, we propose an eigen framework for transmit beamforming for single-hop and dual-hop network models with single antenna receivers. In cases where number of receivers is not more than three, the proposed Eigen approach is vastly superior in terms of ease of implementation and computational complexity compared with the existing convex-relaxation-based approaches. The essential premise is that the precoding problems can be posed as equivalent optimization problems of searching for an optimal vector in the joint numerical range of Hermitian matrices. We show that the latter problem has two convex approximations: the first one is a semi-definite program that yields a lower bound on the solution, and the second one is a linear matrix inequality that yields an upper bound on the solution. We study the performance of the proposed and existing techniques using numerical simulations.

Energy-efficient, delay-constrained, QoS-aware broadcast for cooperative wireless sensor networks

The problem of delay-constrained, energy-efficient broadcast in cooperative wireless networks is NP-complete. While centralised setting allows some heuristic solutions, designing heuristics in distributed implementation poses significant challenges. This is more so in wireless sensor networks (WSNs) where nodes are deployed randomly and topology changes dynamically due to node failure/join and environment conditions. This paper demonstrates that careful design of network infrastructure can achieve guaranteed delay bounds and energy-efficiency, and even meet quality of service requirements during broadcast. The paper makes three prime contributions. First, we present an optimal lower bound on energy consumption for broadcast that is tighter than what has been previously proposed. Next, iSteiner, a lightweight, distributed and deterministic algorithm for creation of network infrastructure is discussed. iPercolate is the algorithm that exploits this structure to cooperatively broadcast information with guaranteed delivery and delay bounds, while allowing real-time traffic to pass undisturbed.

Performance Analysis of Space-Shift Keying in Decode-and-Forward Multihop MIMO Networks

In this paper, space-shift keying (SSK) is considered for multihop multiple-input-multiple-output (MIMO) networks. In SSK, only one among n(s) = 2(m) available transmit antennas, chosen on the basis of m information bits, is activated during transmission. We consider two different systems of multihop co-operation, where each node has multiple antennas and employs SSK. In system I, a multihop diversity relaying scheme is considered. In system II, a multihop multibranch relaying scheme is considered. In both systems, we adopt decode-and-forward (DF) relaying, where each relay forwards the signal only when it correctly decodes. We analyze the end-to-end bit error rate (BER) and diversity order of both the systems with SSK. For binary SSK (n(s) = 2), our analytical BER expression is exact, and our numerical results show that the BERs evaluated through the analytical expression overlap with those obtained through Monte Carlo simulations. For nonbinary SSK (n(s) > 2), we derive an approximate BER expression, where the analytically evaluated BER results closely follow the simulated BER results. We show the comparison of the BERs of SSK and conventional phase-shift keying (PSK) and also show the instances where SSK outperforms PSK. We also present the diversity analyses for SSK in systems I and II, which predict the achievable diversity orders as a function of system parameters.

Belief propagation for minimum weight many-to-one matchings in the random complete graph

In a complete bipartite graph with vertex sets of cardinalities n and n', assign random weights from exponential distribution with mean 1, independently to each edge. We show that, as n -> infinity, with n' = n/alpha] for any fixed alpha > 1, the minimum weight of many-to-one matchings converges to a constant (depending on alpha). Many-to-one matching arises as an optimization step in an algorithm for genome sequencing and as a measure of distance between finite sets. We prove that a belief propagation (BP) algorithm converges asymptotically to the optimal solution. We use the objective method of Aldous to prove our results. We build on previous works on minimum weight matching and minimum weight edge cover problems to extend the objective method and to further the applicability of belief propagation to random combinatorial optimization problems.

Percolation on networks with antagonistic and dependent interactions

Drawing inspiration from real world interacting systems, we study a system consisting of two networks that exhibit antagonistic and dependent interactions. By antagonistic and dependent interactions we mean that a proportion of functional nodes in a network cause failure of nodes in the other, while failure of nodes in the other results in failure of links in the first. In contrast to interdependent networks, which can exhibit first-order phase transitions, we find that the phase transitions in such networks are continuous. Our analysis shows that, compared to an isolated network, the system is more robust against random attacks. Surprisingly, we observe a region in the parameter space where the giant connected components of both networks start oscillating. Furthermore, we find that for Erdos-Renyi and scale-free networks the system oscillates only when the dependence and antagonism between the two networks are very high. We believe that this study can further our understanding of real world interacting systems.

Adaptive Sleep-Wake Control using Reinforcement Learning in Sensor Networks

The aim in this paper is to allocate the `sleep time' of the individual sensors in an intrusion detection application so that the energy consumption from the sensors is reduced, while keeping the tracking error to a minimum. We propose two novel reinforcement learning (RL) based algorithms that attempt to minimize a certain long-run average cost objective. Both our algorithms incorporate feature-based representations to handle the curse of dimensionality associated with the underlying partially-observable Markov decision process (POMDP). Further, the feature selection scheme used in our algorithms intelligently manages the energy cost and tracking cost factors, which in turn assists the search for the optimal sleeping policy. We also extend these algorithms to a setting where the intruder's mobility model is not known by incorporating a stochastic iterative scheme for estimating the mobility model. The simulation results on a synthetic 2-d network setting are encouraging.

Low Complexity Power and Scheduling Policies for Wireless Networks to Provide Quality of Service

We consider optimal power allocation policies for a single server, multiuser system. The power is consumed in transmission of data only. The transmission channel may experience multipath fading. We obtain very efficient, low computational complexity algorithms which minimize power and ensure stability of the data queues. We also obtain policies when the users may have mean delay constraints. If the power required is a linear function of rate then we exploit linearity and obtain linear programs with low complexity.

Secure Transmission in Cooperative Networks with Weak Eavesdroppers

In this letter, we propose a scheme to improve the secrecy rate of cooperative networks using Analog Network Coding (ANC). ANC mixes the signals in the air; the desired signal is then separated out, from the mixed signals, at the legitimate receiver using techniques like self interference subtraction and signal nulling, thereby achieving better secrecy rates. Assuming global channel state information, memoryless adversaries and the decode-and-forward strategy, we seek to maximize the average secrecy rate between the source and the destination, subject to an overall power budget. Then, exploiting the structure of the optimization problem, we compute its optimal solution. Finally, we use numerical evaluations to compare our scheme with the conventional approaches.

Optimal power allocation for protective jamming in wireless networks: A flow based model

We address the problem of passive eavesdroppers in multi-hop wireless networks using the technique of friendly jamming. The network is assumed to employ Decode and Forward (DF) relaying. Assuming the availability of perfect channel state information (CSI) of legitimate nodes and eavesdroppers, we consider a scheduling and power allocation (PA) problem for a multiple-source multiple-sink scenario so that eavesdroppers are jammed, and source-destination throughput targets are met while minimizing the overall transmitted power. We propose activation sets (AS-es) for scheduling, and formulate an optimization problem for PA. Several methods for finding AS-es are discussed and compared. We present an approximate linear program for the original nonlinear, non-convex PA optimization problem, and argue that under certain conditions, both the formulations produce identical results. In the absence of eavesdroppers' CSI, we utilize the notion of Vulnerability Region (VR), and formulate an optimization problem with the objective of minimizing the VR. Our results show that the proposed solution can achieve power-efficient operation while defeating eavesdroppers and achieving desired source-destination throughputs simultaneously. (C) 2015 Elsevier B.V. All rights reserved.