Narrow Results

We introduce a recovery algorithm for low-density parity-check codes that provides substantial coding gain over the conventional method. Concisely, it consists of an inference procedure based on successive decoding rounds using different subsets of bit nodes from the bipartite graph representing the code. The technique also sheds light on certain characteristics of the sum–product algorithm and effectively copes with the problems of trapping sets, cycles, and other anomalies that adversely affect the performance LDPC codes.

The following sections are included:

• Introduction

• Experimental Results

• Analysis of the Sum-Product Algorithm
  • Bipartite Graphs
  • The Sum-Product Algorithm
  • Reduction of the SPA to a local sum algorithm when check nodes have degree 2

• Examples
  • A cycle of length 2m
  • 2 bits n checks
  • 4-Choose-2
  • 3-to-1 covers of the complete 2-bits-3-checks graph
  • Degradation of performance with the coarse termination criterion

• Concluding Remarks

• References

The gram-negative myxobacterium Myxococcus xanthus is equipped with an interesting motility system that allows it to reverse direction on average every 8 minutes by switching the construction of two motility engines at the ends of this rod-shaped bacterium. While the mechanisms responsible for timing and engine construction/deconstruction are relatively well understood, there are several competing hypotheses as to how they are coupled together. In this paper we examine the evidence for protein interactions underlying these possible couplings using a novel framework consisting of a probabilistic model describing protein and domain interactions and a belief propagation inference algorithm. When provided with large amount of indirect pieces of information, such as high-throughput experiment results, and protein structures, we can reliably determine the relative likelihoods of these hypotheses, even though each individual piece of evidence by itself has very limited reliability. The same framework can be used to map large protein and domain interaction networks in myxobacteria and other organisms.