In this paper, a novel framework is presented to estimate protein-protein interactions (PPIs) and domain-domain interactions (DDIs) based on a belief propagation estimation method that efficiently computes interaction probabilities. Experimental interactions, domain architecture, and gene ontology (GO) annotations are used to create a factor graph representation of the joint probability distribution of pairwise protein and domain interactions. Bound structures are used asa priorievidence of domain interactions. These structures come from experiments documented in iPfam. The probability distribution contained in the factor graph is then efficiently marginalized with a message passing algorithm called the sum-product algorithm (SPA). This method is compared against two other approaches: maximum-likelihood estimation (MLE) and maximum specificity set cover (MSSC). SPA performs better for simulated scenarios and for inferring high-quality PPI data ofSaccharomyces cerevisiae. This framework can be used to predict potential protein and domain interactions at a genome wide scale and for any organism with identified protein-domain architectures.

The invention of turbo coding demonstrated that interleaved concatenation of weak codes can achieve excellent performance in the waterfall region of the bit error rate curve when decoded iteratively. The performance curve of turbo codes, however, typically exhibits an error floor due to poor minimum distance. The minimum distance can be increased by introducing a stronger component code into the concatenation, but this can lead to unacceptably large decoding effort if full BCJR decoding is used. In this paper we consider reduced complexity soft input soft output decoding of convolutional codes with long constraint lengths. In particular, we consider the M*-BCJR algorithm, which uses the M-algorithm principle to preserve only the M most promising trellis states at each step of the forward recursion. We demonstrate that the forward state metrics, typically used in M-type algorithms, are insufficient to reliably identify the best M states. In contrast, very small M suffices to achieve very good decoding performance if the state selection is based on both the forward metric and an estimate of the backward metric. We present how a heuristic based on a supercode, a higher rate code containing all the codewords of the original code but having a simpler trellis representation, can serve as an efficient estimate for the backward state metrics, enabling practical decoding of turbo codes with a strong component code.

Viterbi decoding and sequential decoding are the standard approaches to decoding convolutional codes (and linear codes with trellis representations in general). However, when reliable communication at low signal-to-noise ratios (SNR) is desired, both techniques are impractical: the Viterbi algorithm requires large amounts of memory and numbers of computations to decode powerful codes, while sequential decoding at low SNR requires exploring large portions of the code tree. In this paper we present a novel two-pass decoder which incorporates features of both these techniques but can achieve decoding complexities lower than either of them. The decoder initially performs a backward pass that resembles the add-compare-select stage of the Viterbi decoder or the backward stage of the BCJR decoder. However, it is performed not on the trellis representing the actual code used for transmission, but on a higher rate supercode (a linear code containing all codewords of the original code) with a simpler trellis representation. The supercode state metrics obtained in the backward pass are preserved and subsequently used in the forward pass. The forward pass involves the actual tree search for the most likely transmitted codeword (of the original code), and the supercode state metrics serve as heuristics, speeding up the search process. We demonstrate that such a decoder, with a proper choice of parameters, can be made equivalent to a sequential decoder with the Fano metric, a sequential decoder with an ML metric, or a Viterbi decoder (run backwards). However, the decoder operates most effectively in between these modes, when the computational load is distributed evenly between the backward and forward stages.

UNLABELLED: Cytoprophet is a software tool that allows prediction and visualization of protein and domain interaction networks. It is implemented as a plug-in of Cytoscape, an open source software framework for analysis and visualization of molecular networks. Cytoprophet implements three algorithms that predict new potential physical interactions using the domain composition of proteins and experimental assays. The algorithms for protein and domain interaction inference include maximum likelihood estimation (MLE) using expectation maximization (EM); the set cover approach maximum specificity set cover (MSSC) and the sum-product algorithm (SPA). After accepting an input set of proteins with Uniprot ID/Accession numbers and a selected prediction algorithm, Cytoprophet draws a network of potential interactions with probability scores and GO distances as edge attributes. A network of domain interactions between the domains of the initial protein list can also be generated. Cytoprophet was designed to take advantage of the visual capabilities of Cytoscape and be simple to use. An example of inference in a signaling network of myxobacterium Myxococcus xanthus is presented and available at Cytoprophet's website. AVAILABILITY: http://cytoprophet.cse.nd.edu.

Abstract An additional reference is needed in the article Cytoprophet: a Cytoscape plug-in for protein and domain interaction networks inference. We include this reference as a matter of addendum. Contact: [email protected]

Convolutional codes are an efficient means of achieving reliable communication with low latency and complexity constraints. Since optimal Viterbi decoding of long (say, above 8) constraint length codes can be prohibitively complex, sequential decoders, such as the Zigangirov-Jelinek (ZJ) stack algorithm or the Fano algorithm can be applied. However, the performance of sequential algorithms is limited by a steep increase in the average number of steps per information bit that takes place close to the cutoff rate, more than by the error correcting capabilities of the code itself. In this paper we examine the problem of improving the performance of sequential decoders by designing more sophisticated path metrics. In particular, we propose a look-ahead (LA) path metric, which equals the Fano metric of the best path stemming from the current path for a fixed number of time steps. We demonstrate that in the limit of a large number of look-ahead time steps, sequential decoding becomes equivalent to the backtracking step of the Viterbi algorithm. Direct computation of the LA metric requires searching an exponential number of partial paths at each state and is infeasible, since the extra cost of computing the metric outweighs the savings in the number of time steps. However, in some scenarios of interest, the LA metric can be computed by other means. In the particular case of a covolutional code transmitted over a binary symmetric channel (BSC), this metric can be obtained from a modified syndrome decoder that stores for each partial syndrome the weight of the minimum weight error event. We demonstrate through simulations that this structure leads to an efficient and computationally inexpensive sequential decoding algorithm.

When designing communication systems based on serially concatenated codes and iterative decoding, it is common practice to use recursive convolutional codes as inner codes. In this paper we show that very good performance can also be obtained by using simple block codes as inner codes. In particular, we propose a simple extension of a single parity check encoder that produces large Hamming weight output sequences for weight one input sequences. We also present a soft decoding algorithm and use a uniform interleaver analysis and EXIT charts to design efficient schemes that perform well in both the waterfall and error floor regions of the bit error rate curve

The goal of this paper is to establish which practical routing schemes for wireless networks are most suitable for power-limited and bandwidth-limited communication regimes. We regard channel state information (CSI) at the receiver and point-to-point capacity-achieving codes for the additive white Gaussian noise (AWGN) channel as practical features, interference cancellation (IC) as possible, but less practical, and synchronous cooperation (CSI at the transmitters) as impractical. We consider a communication network with a single source node, a single destination node, and N-1 intermediate nodes placed equidistantly on a line between them. We analyze the minimum total transmit power needed to achieve a desired end-to-end rate for several schemes and demonstrate that multihop communication with spatial reuse performs very well in the power-limited regime, even without IC. However, within a class of schemes not performing IC, single-hop transmission (directly from source to destination) is more suitable for the bandwidth-limited regime, especially when higher spectral efficiencies are required. At such higher spectral efficiencies, the gap between single-hop and multihop can be closed by employing IC, and we present a scheme based upon backward decoding that can remove all interference from the multihop system with an arbitrarily small rate loss. This new scheme is also used to demonstrate that rates of O(logN) are achievable over linear wireless networks even without synchronous cooperation.

In this paper we propose a new soft-input soft-output equalization algorithm, offering very good performance/complexity tradeoffs. It follows the structure of the BCJR algorithm, but dynamically constructs a simplified trellis during the forward recursion. In each trellis section, only the M states with the strongest forward metric are preserved, similar to the M-BCJR algorithm. Unlike the M-BCJR, however, the remaining states are not deleted, but rather merged into the surviving states. The new algorithm compares favorably with the reduced-state BCJR algorithm, offering better performance and more flexibility, particularly for systems with higher order modulations

We consider a wireless communication system with a single source node, a single destination node, and multiple relay nodes placed equidistantly between them. We limit our analysis to the case of coded TDMA multihop transmission, i.e., the nodes do not cooperate and do not try to access the channel simultaneously. Given a global constraint on bandwidth, we determine the number of hops that achieves a desired end-to-end rate with the least total transmission power. Furthermore, we examine how the optimum number of hops changes when an end-to-end delay constraint is introduced using the sphere-packing bound and computer simulations. The analysis demonstrates that the optimum number of hops depends on the end-to-end rate and the path-loss exponent. Specifically, we show the existence of an asymptotic per-link spectral efficiency, which is the preferred spectral efficiency in TDMA multihop transmission.

Closed loop transmit diversity (CLTD) for FDD WCDMA relies on low-rate feedback to achieve both beamforming and diversity gain. Since the feedback channel is not immune to errors, occasionally base station (BS) uses different antenna weight vector from the one requested by mobile station (MS). Surprisingly, most of the resulting performance degradation is caused not by reduced power of the Rx signal, but by erroneous dedicated channel estimation at the MS relying on knowledge of used weight vector. In this paper we introduce a general trellis-based antenna weight verification algorithm, which attempts to detect feedback errors and determine the most likely weight vector. By exploiting the structure of CLTD schemes proposed for WCDMA with 2 and 4 BS-antennas we show methods to reduce the complexity of our algorithm. Our comparative simulations show that antenna weight verification reduces the performance degradation due to feedback errors less than 0.5 dB at 1% frame error rate for considered 4 antenna schemes.

The joint operation of high speed downlink packet access (HSDPA) and adaptive antennas in a WCDMA cellular network is considered. The total throughput per cell of HSDPA depends heavily on the strategy employed by the scheduler. It is argued that the maximum SIR scheduler, which maximizes throughput in the single antenna system by serving only the user with the best momentary channel quality, will not substantially benefit from adaptive antennas due to excess self interference at the receiver. As an alternative a set of scheduling strategies is proposed, which rely on serving simultaneously multiple spatially separated users. System level simulations show that with the spatial division multiple access scheduler it is possible to achieve almost twofold throughput improvement over maximum SIR when using four antennas per sector.

Adaptive antennas at the base stations have a big potential to increase downlink capacity and coverage in WCDMA systems. One of the most promising techniques of adaptive antenna control is closed-loop transmit diversity. This method achieves beamforming gain as well as diversity gain by feedback of downlink fast fading characteristics from mobile station to base station. Due to the limited feedback rate, typically the best antenna weight vector chosen from a restricted set is reported. If this feedback is subject to transmission errors, two performance degrading effects occur: a suboptimal weight vector is used and channel estimation errors take place at the mobile station. The latter effect arises because the mobile station derives the channel estimate for the dedicated channel from the reported weight vector and the channel estimate per antenna based on the common pilot channel. In effect, feedback errors severely distort this estimate and lead to an error floor effect. However, channel estimation can also be based on the pilot symbols in the dedicated channel itself. This estimate has high variance, but is not distorted by feedback errors. If both estimates are combined in a process called antenna weight verification, performance can be dramatically increased. Within this paper an antenna weight verification scheme for eigenbeamformer is presented, which maximizes the estimation accuracy and eliminates the error floor. This is demonstrated by theoretical analysis and link-level simulations. It is shown that this antenna weight verification reduces the performance degradation to 0.2 dB at 1% frame error rate.