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.

Electron transfer amongst flavo- and hemo-proteins: diffusible species effect the relay processes, not protein-protein binding

Hitherto, electron transfer (ET) between redox proteins has been deemed to occur via donor-acceptor binding, and diffusible reactive species are considered as deleterious side-products in such systems. Herein, ET from cytochrome P450 reductase (CPR, an animal membrane flavoprotein) and horseradish peroxidase (HRP, a plant hemoprotein) to cytochrome c (Cyt c, a soluble animal hemoprotein) was probed under diverse conditions, using standard assays. ET in the CPR-Cyt c system was critically inhibited by cyanide and sub-equivalent levels of polar one-electron cyclers like copper ions, vitamin C/Trolox and superoxide dismutase. In the presence of lipids, inhibition was also afforded by amphipathic molecules vitamin E, palmitoyl-vitamin C and the membrane hemoprotein, cytochrome b(5). Such nonspecific inhibition (by diverse agents in both aqueous and lipid phases) indicated that electron transfer/relay was effected by small diffusible agents, whose lifetimes are shortened by the diverse radical scavengers. When CPR was retained in a dialysis membrane and Cyt c presented outside in free solution, ET was still observed. Further, HRP (taken at nM levels) catalyzed oxidation of a phenolic substrate was significantly inhibited upon the incorporation of sub-nM levels of Cyt c. The findings imply that CPR-Cyt c or HRP-Cyt c binding is not crucial for ET. Further, fundamental quantitative arguments (based on diffusion/collision) challenge the erstwhile protein-protein binding-assisted ET hypothesis. It is proven beyond reasonable doubt that mobile and diffusible electron carriers (ions and radicals) serve as ``redox-relay agents'' in the biological ET models/setup studied.