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.

Effects of stochastic coding on olfactory discrimination in flies and mice.

Sparse coding can improve discrimination of sensory stimuli by reducing overlap between their representations. Two factors, however, can offset sparse coding's benefits: similar sensory stimuli have significant overlap and responses vary across trials. To elucidate the effects of these 2 factors, we analyzed odor responses in the fly and mouse olfactory regions implicated in learning and discrimination-the mushroom body (MB) and the piriform cortex (PCx). We found that neuronal responses fall along a continuum from extremely reliable across trials to extremely variable or stochastic. Computationally, we show that the observed variability arises from noise within central circuits rather than sensory noise. We propose this coding scheme to be advantageous for coarse- and fine-odor discrimination. More reliable cells enable quick discrimination between dissimilar odors. For similar odors, however, these cells overlap and do not provide distinguishing information. By contrast, more unreliable cells are decorrelated for similar odors, providing distinguishing information, though these benefits only accrue with extended training with more trials. Overall, we have uncovered a conserved, stochastic coding scheme in vertebrates and invertebrates, and we identify a candidate mechanism, based on variability in a winner-take-all (WTA) inhibitory circuit, that improves discrimination with training.

Dense and persistent odor representations in the olfactory bulb of awake mice.

Recording and analysis of neural activity is often biased toward detecting sparse subsets of highly active neurons, masking important signals carried in low magnitude and variable responses. To investigate the contribution of seemingly noisy activity to odor encoding, we used mesoscale calcium imaging from mice of both sexes to record odor responses from the dorsal surface of bilateral olfactory bulbs (OBs). The outer layer of the mouse OB is comprised of dendrites organized into discrete "glomeruli", which are defined by odor receptor-specific sensory neuron input. We extracted activity from a large population of glomeruli and used logistic regression to classify odors from individual trials with high accuracy. We then used add-in and drop-out analyses to determine subsets of glomeruli necessary and sufficient for odor classification. Classifiers successfully predicted odor identity even after excluding sparse, highly active glomeruli, indicating that odor information is redundantly represented across a large population of glomeruli. Additionally, we found that Random Forest feature selection informed by Gini Inequality (RFGI) reliably ranked glomeruli by their contribution to overall odor classification. RFGI provided a measure of "feature importance" for each glomerulus that correlated with intuitive features like response magnitude. Finally, in agreement with previous work, we found that odor information persists in glomerular activity after odor offset. Together, our findings support a model of olfactory bulb odor coding where sparse activity is sufficient for odor identification, but information is widely, redundantly available across a large population of glomeruli, with each glomerulus representing information about more than one odor.Significance statement This study leverages meso-scale imaging and machine learning to investigate how odor information is first represented in the brain. Typically, recordings of neuronal activity focus on active individual cells, potentially overlooking broader variations in neuronal responses across populations. Our results demonstrate that a considerable amount of olfactory information is redundantly distributed across a large proportion of olfactory bulb glomeruli. Even after excluding a majority of glomeruli, odor identification remained possible. These findings indicate that, although a few glomeruli are sufficient for odor recognition, an abundance of additional information is represented across a broad population. Understanding how the brain manages redundant olfactory information will shed light on its adaptive mechanisms for navigating diverse real-world circumstances and responding to fluctuating internal states.

Reducing Catastrophic Forgetting With Associative Learning: A Lesson From Fruit Flies.

Catastrophic forgetting remains an outstanding challenge in continual learning. Recently, methods inspired by the brain, such as continual representation learning and memory replay, have been used to combat catastrophic forgetting. Associative learning (retaining associations between inputs and outputs, even after good representations are learned) plays an important function in the brain; however, its role in continual learning has not been carefully studied. Here, we identified a two-layer neural circuit in the fruit fly olfactory system that performs continual associative learning between odors and their associated valences. In the first layer, inputs (odors) are encoded using sparse, high-dimensional representations, which reduces memory interference by activating nonoverlapping populations of neurons for different odors. In the second layer, only the synapses between odor-activated neurons and the odor's associated output neuron are modified during learning; the rest of the weights are frozen to prevent unrelated memories from being overwritten. We prove theoretically that these two perceptron-like layers help reduce catastrophic forgetting compared to the original perceptron algorithm, under continual learning. We then show empirically on benchmark data sets that this simple and lightweight architecture outperforms other popular neural-inspired algorithms when also using a two-layer feedforward architecture. Overall, fruit flies evolved an efficient continual associative learning algorithm, and circuit mechanisms from neuroscience can be translated to improve machine computation.

Habituation as a neural algorithm for online odor discrimination.

Habituation is a form of simple memory that suppresses neural activity in response to repeated, neutral stimuli. This process is critical in helping organisms guide attention toward the most salient and novel features in the environment. Here, we follow known circuit mechanisms in the fruit fly olfactory system to derive a simple algorithm for habituation. We show, both empirically and analytically, that this algorithm is able to filter out redundant information, enhance discrimination between odors that share a similar background, and improve detection of novel components in odor mixtures. Overall, we propose an algorithmic perspective on the biological mechanism of habituation and use this perspective to understand how sensory physiology can affect odor perception. Our framework may also help toward understanding the effects of habituation in other more sophisticated neural systems.

Neural network features distinguish chemosensory stimuli in Caenorhabditis elegans.

Nervous systems extract and process information from the environment to alter animal behavior and physiology. Despite progress in understanding how different stimuli are represented by changes in neuronal activity, less is known about how they affect broader neural network properties. We developed a framework for using graph-theoretic features of neural network activity to predict ecologically relevant stimulus properties, in particular stimulus identity. We used the transparent nematode, Caenorhabditis elegans, with its small nervous system to define neural network features associated with various chemosensory stimuli. We first immobilized animals using a microfluidic device and exposed their noses to chemical stimuli while monitoring changes in neural activity of more than 50 neurons in the head region. We found that graph-theoretic features, which capture patterns of interactions between neurons, are modulated by stimulus identity. Further, we show that a simple machine learning classifier trained using graph-theoretic features alone, or in combination with neural activity features, can accurately predict salt stimulus. Moreover, by focusing on putative causal interactions between neurons, the graph-theoretic features were almost twice as predictive as the neural activity features. These results reveal that stimulus identity modulates the broad, network-level organization of the nervous system, and that graph theory can be used to characterize these changes.

Better tired than lost: Turtle ant trail networks favor coherence over short edges.

Creating a routing backbone is a fundamental problem in both biology and engineering. The routing backbone of the trail networks of arboreal turtle ants (Cephalotes goniodontus) connects many nests and food sources using trail pheromone deposited by ants as they walk. Unlike species that forage on the ground, the trail networks of arboreal ants are constrained by the vegetation. We examined what objectives the trail networks meet by comparing the observed ant trail networks with networks of random, hypothetical trail networks in the same surrounding vegetation and with trails optimized for four objectives: minimizing path length, minimizing average edge length, minimizing number of nodes, and minimizing opportunities to get lost. The ants' trails minimized path length by minimizing the number of nodes traversed rather than choosing short edges. In addition, the ants' trails reduced the opportunity for ants to get lost at each node, favoring nodes with 3D configurations most likely to be reinforced by pheromone. Thus, rather than finding the shortest edges, turtle ant trail networks take advantage of natural variation in the environment to favor coherence, keeping the ants together on the trails.

Adjustment in tumbling rates improves bacterial chemotaxis on obstacle-laden terrains.

The mechanisms of bacterial chemotaxis have been extensively studied for several decades, but how the physical environment influences the collective migration of bacterial cells remains less understood. Previous models of bacterial chemotaxis have suggested that the movement of migrating bacteria across obstacle-laden terrains may be slower compared with terrains without them. Here, we show experimentally that the size or density of evenly spaced obstacles do not alter the average exit rate of Escherichia coli cells from microchambers in response to external attractants, a function that is dependent on intact cell-cell communication. We also show, both by analyzing a revised theoretical model and by experimentally following single cells, that the reduced exit time in the presence of obstacles is a consequence of reduced tumbling frequency that is adjusted by the E. coli cells in response to the topology of their environment. These findings imply operational short-term memory of bacteria while moving through complex environments in response to chemotactic stimuli and motivate improved algorithms for self-autonomous robotic swarms.

Plant 3D (P3D): a plant phenotyping toolkit for 3D point clouds.

MOTIVATION: Developing methods to efficiently analyze 3D point cloud data of plant architectures remain challenging for many phenotyping applications. Here, we describe a tool that tackles four core phenotyping tasks: classification of cloud points into stem and lamina points, graph skeletonization of the stem points, segmentation of individual lamina and whole leaf labeling. These four tasks are critical for numerous downstream phenotyping goals, such as quantifying plant biomass, performing morphological analyses of plant shapes and uncovering genotype to phenotype relationships. The Plant 3D tool provides an intuitive graphical user interface, a fast 3D rendering engine for visualizing plants with millions of cloud points, and several graph-theoretic and machine-learning algorithms for 3D architecture analyses. AVAILABILITY AND IMPLEMENTATION: P3D is open-source and implemented in C++. Source code and Windows installer are freely available at https://github.com/iziamtso/P3D/. CONTACT: iziamtso@ucsd.edu or navlakha@cshl.edu. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

A Correspondence Between Normalization Strategies in Artificial and Biological Neural Networks.

A fundamental challenge at the interface of machine learning and neuroscience is to uncover computational principles that are shared between artificial and biological neural networks. In deep learning, normalization methods such as batch normalization, weight normalization, and their many variants help to stabilize hidden unit activity and accelerate network training, and these methods have been called one of the most important recent innovations for optimizing deep networks. In the brain, homeostatic plasticity represents a set of mechanisms that also stabilize and normalize network activity to lie within certain ranges, and these mechanisms are critical for maintaining normal brain function. In this article, we discuss parallels between artificial and biological normalization methods at four spatial scales: normalization of a single neuron's activity, normalization of synaptic weights of a neuron, normalization of a layer of neurons, and normalization of a network of neurons. We argue that both types of methods are functionally equivalent-that is, both push activation patterns of hidden units toward a homeostatic state, where all neurons are equally used-and we argue that such representations can improve coding capacity, discrimination, and regularization. As a proof of concept, we develop an algorithm, inspired by a neural normalization technique called synaptic scaling, and show that this algorithm performs competitively against existing normalization methods on several data sets. Overall, we hope this bidirectional connection will inspire neuroscientists and machine learners in three ways: to uncover new normalization algorithms based on established neurobiological principles; to help quantify the trade-offs of different homeostatic plasticity mechanisms used in the brain; and to offer insights about how stability may not hinder, but may actually promote, plasticity.

Projecting COVID-19 disease severity in cancer patients using purposefully-designed machine learning.

BACKGROUND: Accurately predicting outcomes for cancer patients with COVID-19 has been clinically challenging. Numerous clinical variables have been retrospectively associated with disease severity, but the predictive value of these variables, and how multiple variables interact to increase risk, remains unclear. METHODS: We used machine learning algorithms to predict COVID-19 severity in 348 cancer patients at Memorial Sloan Kettering Cancer Center in New York City. Using only clinical variables collected on or before a patient's COVID-19 positive date (time zero), we sought to classify patients into one of three possible future outcomes: Severe-early (the patient required high levels of oxygen support within 3 days of being tested positive for COVID-19), Severe-late (the patient required high levels of oxygen after 3 days), and Non-severe (the patient never required oxygen support). RESULTS: Our algorithm classified patients into these classes with an area under the receiver operating characteristic curve (AUROC) ranging from 70 to 85%, significantly outperforming prior methods and univariate analyses. Critically, classification accuracy is highest when using a potpourri of clinical variables - including basic patient information, pre-existing diagnoses, laboratory and radiological work, and underlying cancer type - suggesting that COVID-19 in cancer patients comes with numerous, combinatorial risk factors. CONCLUSIONS: Overall, we provide a computational tool that can identify high-risk patients early in their disease progression, which could aid in clinical decision-making and selecting treatment options.

A neural data structure for novelty detection.

Novelty detection is a fundamental biological problem that organisms must solve to determine whether a given stimulus departs from those previously experienced. In computer science, this problem is solved efficiently using a data structure called a Bloom filter. We found that the fruit fly olfactory circuit evolved a variant of a Bloom filter to assess the novelty of odors. Compared with a traditional Bloom filter, the fly adjusts novelty responses based on two additional features: the similarity of an odor to previously experienced odors and the time elapsed since the odor was last experienced. We elaborate and validate a framework to predict novelty responses of fruit flies to given pairs of odors. We also translate insights from the fly circuit to develop a class of distance- and time-sensitive Bloom filters that outperform prior filters when evaluated on several biological and computational datasets. Overall, our work illuminates the algorithmic basis of an important neurobiological problem and offers strategies for novelty detection in computational systems.

Machine Learning Approaches to Improve Three Basic Plant Phenotyping Tasks Using Three-Dimensional Point Clouds.

Developing automated methods to efficiently process large volumes of point cloud data remains a challenge for three-dimensional (3D) plant phenotyping applications. Here, we describe the development of machine learning methods to tackle three primary challenges in plant phenotyping: lamina/stem classification, lamina counting, and stem skeletonization. For classification, we assessed and validated the accuracy of our methods on a dataset of 54 3D shoot architectures, representing multiple growth conditions and developmental time points for two Solanaceous species, tomato (Solanum lycopersicum cv 75 m82D) and Nicotiana benthamiana Using deep learning, we classified lamina versus stems with 97.8% accuracy. Critically, we also demonstrated the robustness of our method to growth conditions and species that have not been trained on, which is important in practical applications but is often untested. For lamina counting, we developed an enhanced region-growing algorithm to reduce oversegmentation; this method achieved 86.6% accuracy, outperforming prior methods developed for this problem. Finally, for stem skeletonization, we developed an enhanced tip detection technique, which ran an order of magnitude faster and generated more precise skeleton architectures than prior methods. Overall, our improvements enable higher throughput and accurate extraction of phenotypic properties from 3D point cloud data.

Network trade-offs and homeostasis in Arabidopsis shoot architectures.

Understanding the optimization objectives that shape shoot architectures remains a critical problem in plant biology. Here, we performed 3D scanning of 152 Arabidopsis shoot architectures, including wildtype and 10 mutant strains, and we uncovered a design principle that describes how architectures make trade-offs between competing objectives. First, we used graph-theoretic analysis to show that Arabidopsis shoot architectures strike a Pareto optimal that can be captured as maximizing performance in transporting nutrients and minimizing costs in building the architecture. Second, we identify small sets of genes that can be mutated to shift the weight prioritizing one objective over the other. Third, we show that this prioritization weight feature is significantly less variable across replicates of the same genotype compared to other common plant traits (e.g., number of rosette leaves, total volume occupied). This suggests that this feature is a robust descriptor of a genotype, and that local variability in structure may be compensated for globally in a homeostatic manner. Overall, our work provides a framework to understand optimization trade-offs made by shoot architectures and provides evidence that these trade-offs can be modified genetically, which may aid plant breeding and selection efforts.

Neural arbors are Pareto optimal.

Neural arbors (dendrites and axons) can be viewed as graphs connecting the cell body of a neuron to various pre- and post-synaptic partners. Several constraints have been proposed on the topology of these graphs, such as minimizing the amount of wire needed to construct the arbor (wiring cost), and minimizing the graph distances between the cell body and synaptic partners (conduction delay). These two objectives compete with each other-optimizing one results in poorer performance on the other. Here, we describe how well neural arbors resolve this network design trade-off using the theory of Pareto optimality. We develop an algorithm to generate arbors that near-optimally balance between these two objectives, and demonstrate that this algorithm improves over previous algorithms. We then use this algorithm to study how close neural arbors are to being Pareto optimal. Analysing 14 145 arbors across numerous brain regions, species and cell types, we find that neural arbors are much closer to being Pareto optimal than would be expected by chance and other reasonable baselines. We also investigate how the location of the arbor on the Pareto front, and the distance from the arbor to the Pareto front, can be used to classify between some arbor types (e.g. axons versus dendrites, or different cell types), highlighting a new potential connection between arbor structure and function. Finally, using this framework, we find that another biological branching structure-plant shoot architectures used to collect and distribute nutrients-are also Pareto optimal, suggesting shared principles of network design between two systems separated by millions of years of evolution.

Evidence of Rentian Scaling of Functional Modules in Diverse Biological Networks.

Biological networks have long been known to be modular, containing sets of nodes that are highly connected internally. Less emphasis, however, has been placed on understanding how intermodule connections are distributed within a network. Here, we borrow ideas from engineered circuit design and study Rentian scaling, which states that the number of external connections between nodes in different modules is related to the number of nodes inside the modules by a power-law relationship. We tested this property in a broad class of molecular networks, including protein interaction networks for six species and gene regulatory networks for 41 human and 25 mouse cell types. Using evolutionarily defined modules corresponding to known biological processes in the cell, we found that all networks displayed Rentian scaling with a broad range of exponents. We also found evidence for Rentian scaling in functional modules in the Caenorhabditis elegans neural network, but, interestingly, not in three different social networks, suggesting that this property does not inevitably emerge. To understand how such scaling may have arisen evolutionarily, we derived a new graph model that can generate Rentian networks given a target Rent exponent and a module decomposition as inputs. Overall, our work uncovers a new principle shared by engineered circuits and biological networks.

Learning the Structural Vocabulary of a Network.

Networks have become instrumental in deciphering how information is processed and transferred within systems in almost every scientific field today. Nearly all network analyses, however, have relied on humans to devise structural features of networks believed to be most discriminative for an application. We present a framework for comparing and classifying networks without human-crafted features using deep learning. After training, autoencoders contain hidden units that encode a robust structural vocabulary for succinctly describing graphs. We use this feature vocabulary to tackle several network mining problems and find improved predictive performance versus many popular features used today. These problems include uncovering growth mechanisms driving the evolution of networks, predicting protein network fragility, and identifying environmental niches for metabolic networks. Deep learning offers a principled approach for mining complex networks and tackling graph-theoretic problems.

Using Inspiration from Synaptic Plasticity Rules to Optimize Traffic Flow in Distributed Engineered Networks.

Controlling the flow and routing of data is a fundamental problem in many distributed networks, including transportation systems, integrated circuits, and the Internet. In the brain, synaptic plasticity rules have been discovered that regulate network activity in response to environmental inputs, which enable circuits to be stable yet flexible. Here, we develop a new neuro-inspired model for network flow control that depends only on modifying edge weights in an activity-dependent manner. We show how two fundamental plasticity rules, long-term potentiation and long-term depression, can be cast as a distributed gradient descent algorithm for regulating traffic flow in engineered networks. We then characterize, both by simulation and analytically, how different forms of edge-weight-update rules affect network routing efficiency and robustness. We find a close correspondence between certain classes of synaptic weight update rules derived experimentally in the brain and rules commonly used in engineering, suggesting common principles to both.

Unbiased, High-Throughput Electron Microscopy Analysis of Experience-Dependent Synaptic Changes in the Neocortex.

Neocortical circuits can be altered by sensory and motor experience, with experimental evidence supporting both anatomical and electrophysiological changes in synaptic properties. Previous studies have focused on changes in specific neurons or pathways-for example, the thalamocortical circuitry, layer 4-3 (L4-L3) synapses, or in the apical dendrites of L5 neurons- but a broad-scale analysis of experience-induced changes across the cortical column has been lacking. Without this comprehensive approach, a full understanding of how cortical circuits adapt during learning or altered sensory input will be impossible. Here we adapt an electron microscopy technique that selectively labels synapses, in combination with a machine-learning algorithm for semiautomated synapse detection, to perform an unbiased analysis of developmental and experience-dependent changes in synaptic properties across an entire cortical column in mice. Synapse density and length were compared across development and during whisker-evoked plasticity. Between postnatal days 14 and 18, synapse density significantly increases most in superficial layers, and synapse length increases in L3 and L5B. Removal of all but a single whisker row for 24 h led to an apparent increase in synapse density in L2 and a decrease in L6, and a significant increase in length in L3. Targeted electrophysiological analysis of changes in miniature EPSC and IPSC properties in L2 pyramidal neurons showed that mEPSC frequency nearly doubled in the whisker-spared column, a difference that was highly significant. Together, this analysis shows that data-intensive analysis of column-wide changes in synapse properties can generate specific and testable hypotheses about experience-dependent changes in cortical organization. SIGNIFICANCE STATEMENT: Development and sensory experience can change synapse properties in the neocortex. Here we use a semiautomated analysis of electron microscopy images for an unbiased, column-wide analysis of synapse changes. This analysis reveals new loci for synaptic change that can be verified by targeted electrophysiological investigation. This method can be used as a platform for generating new hypotheses about synaptic changes across different brain areas and experimental conditions.