skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: A neural algorithm for computing bipartite matchings
Finding optimal bipartite matchings—e.g., matching medical students to hospitals for residency, items to buyers in an auction, or papers to reviewers for peer review—is a fundamental combinatorial optimization problem. We found a distributed algorithm for computing matchings by studying the development of the neuromuscular circuit. The neuromuscular circuit can be viewed as a bipartite graph formed between motor neurons and muscle fibers. In newborn animals, neurons and fibers are densely connected, but after development, each fiber is typically matched (i.e., connected) to exactly one neuron. We cast this synaptic pruning process as a distributed matching (or assignment) algorithm, where motor neurons “compete” with each other to “win” muscle fibers. We show that this algorithm is simple to implement, theoretically sound, and effective in practice when evaluated on real-world bipartite matching problems. Thus, insights from the development of neural circuits can inform the design of algorithms for fundamental computational problems.  more » « less
Award ID(s):
2211386 1950621
PAR ID:
10540677
Author(s) / Creator(s):
; ; ; ; ;
Publisher / Repository:
National Academy of Sciences
Date Published:
Journal Name:
Proceedings of the National Academy of Sciences
Volume:
121
Issue:
37
ISSN:
0027-8424
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. NA (Ed.)
    Stable matching of neurotransmitters with their receptors is fundamental to synapse function and reliable communication in neural circuits. Presynaptic neurotransmitters regulate the stabilization of postsynaptic transmitter receptors. Whether postsynaptic receptors regulate stabilization of presynaptic transmitters has received less attention. Here, we show that blockade of endogenous postsynaptic acetylcholine receptors (AChR) at the neuromuscular junction destabilizes the cholinergic phenotype in motor neurons and stabilizes an earlier, developmentally transient glutamatergic phenotype. Further, expression of exogenous postsynaptic gamma-aminobutyric acid type A receptors (GABAAreceptors) in muscle cells stabilizes an earlier, developmentally transient GABAergic motor neuron phenotype. Both AChR and GABAAreceptors are linked to presynaptic neurons through transsynaptic bridges. Knockdown of specific components of these transsynaptic bridges prevents stabilization of the cholinergic or GABAergic phenotypes. Bidirectional communication can enforce a match between transmitter and receptor and ensure the fidelity of synaptic transmission. Our findings suggest a potential role of dysfunctional transmitter receptors in neurological disorders that involve the loss of the presynaptic transmitter. 
    more » « less
  2. The integration of muscle cells with soft robotics in recent years has led to the development of biohybrid machines capable of untethered locomotion. A major frontier that currently remains unexplored is neuronal actuation and control of such muscle-powered biohybrid machines. As a step toward this goal, we present here a biohybrid swimmer driven by on-board neuromuscular units. The body of the swimmer consists of a free-standing soft scaffold, skeletal muscle tissue, and optogenetic stem cell-derived neural cluster containing motor neurons. Myoblasts embedded in extracellular matrix self-organize into a muscle tissue guided by the geometry of the scaffold, and the resulting muscle tissue is cocultured in situ with a neural cluster. Motor neurons then extend neurites selectively toward the muscle and innervate it, developing functional neuromuscular units. Based on this initial construct, we computationally designed, optimized, and implemented light-sensitive flagellar swimmers actuated by these neuromuscular units. Cyclic muscle contractions, induced by neural stimulation, drive time-irreversible flagellar dynamics, thereby providing thrust for untethered forward locomotion of the swimmer. Overall, this work demonstrates an example of a biohybrid robot implementing neuromuscular actuation and illustrates a path toward the forward design and control of neuron-enabled biohybrid machines. 
    more » « less
  3. Many important structured prediction problems, including learning to rank items, correspondence-based natural language processing, and multi-object tracking, can be formulated as weighted bipartite matching optimizations. Existing structured prediction approaches have significant drawbacks when applied under the constraints of perfect bipartite matchings. Exponential family probabilistic models, such as the conditional random field (CRF), provide statistical consistency guarantees, but suffer computationally from the need to compute the normalization term of its distribution over matchings, which is a #P-hard matrix permanent computation. In contrast, the structured support vector machine (SSVM) provides computational efficiency, but lacks Fisher consistency, meaning that there are distributions of data for which it cannot learn the optimal matching even under ideal learning conditions (i.e., given the true distribution and selecting from all measurable potential functions). We propose adversarial bipartite matching to avoid both of these limitations. We develop this approach algorithmically, establish its computational efficiency and Fisher consistency properties, and apply it to matching problems that demonstrate its empirical benefits 
    more » « less
  4. Three-dimensional (3D) biomimetic systems hold great promise for the study of biological systems in vitro as well as for the development and testing of pharmaceuticals. Here, we test the hypothesis that an intact segment of lumbar rat spinal cord will form functional neuromuscular junctions (NMJs) with engineered, 3D muscle tissue, mimicking the partial development of the peripheral nervous system (PNS). Muscle tissues are grown on a 3D-printed polyethylene glycol (PEG) skeleton where deflection of the backbone due to muscle contraction causes the displacement of the pillar-like “feet.” We show that spinal cord explants extend a robust and complex arbor of motor neurons and glia in vitro. We then engineered a “spinobot” by innervating the muscle tissue with an intact segment of lumbar spinal cord that houses the hindlimb locomotor central pattern generator (CPG). Within 7 days of the spinal cord being introduced to the muscle tissue, functional neuromuscular junctions (NMJs) are formed, resulting in the development of an early PNS in vitro. The newly innervated muscles exhibit spontaneous contractions as measured by the displacement of pillars on the PEG skeleton. Upon chemical excitation, the spinal cord-muscle system initiated muscular twitches with a consistent frequency pattern. These sequences of contraction/relaxation suggest the action of a spinal CPG. Chemical inhibition with a blocker of neuronal glutamate receptors effectively blocked contractions. Overall, these data demonstrate that a rat spinal cord is capable of forming functional neuromuscular junctions ex vivo with an engineered muscle tissue at an ontogenetically similar timescale. 
    more » « less
  5. Appropriate generalization of learned responses to new situations is vital for adaptive behavior. We provide a circuit-level account of generalization in the electrosensory lobe (ELL) of weakly electric mormyrid fish. Much is already known in this system about a form of learning in which motor corollary discharge signals cancel responses to the uninformative input evoked by the fish’s own electric pulses. However, for this cancellation to be useful under natural circumstances, it must generalize accurately across behavioral regimes, specifically different electric pulse rates. We show that such generalization indeed occurs in ELL neurons, and develop a circuit-level model explaining how this may be achieved. The mechanism involves regularized synaptic plasticity and an approximate matching of the temporal dynamics of motor corollary discharge and electrosensory inputs. Recordings of motor corollary discharge signals in mossy fibers and granule cells provide direct evidence for such matching. 
    more » « less