Computer Science and Engineering Department, University of California San Diego, La Jolla, CA 92037.
Department of Molecular and Cell Biology and Center for Brain Science, Harvard University, Cambridge, MA 02138.
Proc Natl Acad Sci U S A. 2024 Sep 10;121(37):e2321032121. doi: 10.1073/pnas.2321032121. Epub 2024 Sep 3.
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.
寻找最优的二分匹配——例如，将医学生与医院进行住院医师匹配、将物品与拍卖中的买家匹配、或将论文与同行评审者进行匹配——是一个基本的组合优化问题。我们通过研究神经肌肉回路的发育找到了一种计算匹配的分布式算法。神经肌肉回路可以看作是由运动神经元和肌肉纤维形成的二分图。在新生动物中，神经元和纤维是密集连接的，但在发育后，每个纤维通常与（即连接）一个神经元匹配。我们将这个突触修剪过程建模为一个分布式匹配（或分配）算法，其中运动神经元相互竞争以“赢得”肌肉纤维。我们表明，当在实际的二分匹配问题上进行评估时，该算法易于实现、理论上合理且有效。因此，神经回路发育的见解可以为基本计算问题的算法设计提供信息。
