Research interests

• We work at the interface of theoretical computer science, machine learning, and systems biology.
• We primarily study "algorithms in nature", i.e., how collections of molecules, cells, and organisms process information and solve interesting computational problems critical for survival.

Publications

 +2024

• S. Dasgupta, Y. Meirovitch, X. Zheng, I. Bush, J. W. Lichtman, and S. Navlakha (2024). A neural algorithm for computing bipartite matchings. Proc. Natl. Acad. Sci. USA, 121(37):e2321032121.
  [abstract]
  Abstract: 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 discovered 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.
  [pdf] [press release] [code]

 +2023

• S. Srinivasan, S. Daste, M. Modi, G. Turner, A. Fleischmann, and S. Navlakha (2023). Effects of stochastic coding on olfactory discrimination in flies and mice. PLoS Biol., 21, 10:e3002206.
  [abstract]
  Abstract: 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 two 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 inhibitory circuit, that improves discrimination with training.
  [pdf] [press release]


• Y. Shen, S. Dasgupta, and S. Navlakha (2023). Reducing catastrophic forgetting with associative learning --- a lesson from fruit flies. Neural Comp., 35, 11:1797-1819.
  [abstract]
  Abstract: 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 (i.e., 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 non-overlapping 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 datasets that this simple and lightweight architecture outperforms other popular neurally-inspired algorithms when also using a three-layer feed-forward architecture. Overall, fruit flies evolved an efficient continual associative learning algorithm, and circuit mechanisms from neuroscience can be translated to improve machine computation.
  [pdf] [code]

 +2022

• S. Dasgupta, D. Hattori, and S. Navlakha (2022). A neural theory for counting memories. Nature Commun., 13, 5961.
  [abstract]
  Abstract: Keeping track of the number of times different stimuli have been experienced is a critical computation for behavior. Here, we propose a theoretical two-layer neural circuit that stores counts of stimulus occurrence frequencies. This circuit implements a data structure, called a count sketch, that is commonly used in computer science to maintain item frequencies in streaming data. Our first model implements a count sketch using Hebbian synapses and outputs stimulus-specific frequencies. Our second model uses anti-Hebbian plasticity and only tracks frequencies within four count categories ("1-2-3-many"), which trades-off the number of categories that need to be distinguished with the potential ethological value of those categories. We show how both models can robustly track stimulus occurrence frequencies, thus expanding the traditional novelty-familiarity memory axis from binary to discrete with more than two possible values. Finally, we show that an implementation of the "1-2-3-many" count sketch exists in the insect mushroom body.
  [pdf] [press release] [code]


• J. Y. Suen and S. Navlakha (2022). A feedback control principle common to several biological and engineered systems. J. R. Soc. Interface,19, 188:20210711.
  [abstract]
  Abstract: Feedback control is used by many distributed systems to optimize behavior. Traditional feedback control algorithms spend significant resources to constantly sense and stabilize a continuous control variable of interest, such as vehicle speed for implementing cruise control, or body temperature for maintaining homeostasis. In contrast, discrete-event feedback (e.g., a server acknowledging when data is successfully transmitted, or a brief antennal interaction when an ant returns to the nest after successful foraging) can reduce costs associated with monitoring a continuous variable; however, optimizing behavior in this setting requires alternative strategies. Here, we studied parallels between discrete-event feedback control strategies in biological and engineered systems. We found that two common engineering rules --- additive-increase, upon positive feedback, and multiplicative-decrease, upon negative feedback (called AIMD), and multiplicative-increase multiplicative-decrease (MIMD) --- are used by diverse biological systems, including for regulating foraging by harvester ant colonies, for maintaining cell-size homeostasis, and for synaptic learning and adaptation in neural circuits. These rules support several goals of these systems, including optimizing efficiency (i.e., utilizing all available resources); splitting resources fairly among cooperating agents, or conversely, acquiring resources quickly among competing agents; and minimizing the latency of responses, especially when conditions change. We hypothesize that theoretical frameworks from distributed computing may offer new ways to analyze adaptation behavior of biology systems, and in return, biological strategies may inspire new algorithms for discrete-event feedback control in engineering.
  [pdf] [press release]

 +2021

• J. J. How, S. Navlakha, and S. H. Chalasani (2021). Neural network features distinguish chemosensory stimuli in Caenorhabditis elegans. PLoS Comput. Biol., 17, 11:e1009591.
  [abstract]
  Abstract: 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.
  [pdf] [press release]


• A. Chandrasekhar, J. A. R. Marshall, C. Austin, S. Navlakha, and D. M. Gordon (2021). Better tired than lost: turtle ant trail networks favor coherence over short edges. PLoS Comput. Biol., 17, 10:e1009523.
  [abstract]
  Abstract: 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.
  [pdf]


• I. Ziamtsov, K. Faizi, and S. Navlakha (2021). Branch-Pipe: Improving graph skeletonization around branch points in 3D point clouds. Remote Sens., 13(19), 3802.
  [abstract]
  Abstract: Modern plant phenotyping requires tools that are robust to noise and missing data, while being able to efficiently process large numbers of plants. Here, we studied skeletonization of plant architectures from 3D point clouds, which is critical for many downstream tasks, including analyses of plant shape, morphology, and branching angles. We developed an algorithm to improve skeletonization at branch points (forks) by leveraging geometric properties of cylinders around branch points. We tested this algorithm on a diverse set of high-resolution 3D point clouds of tomato and tobacco plants, grown in five environments and across multiple developmental timepoints. Compared to existing methods for 3D skeletonization, our method efficiently and more accurately estimated branching angles, even in areas with noisy, missing, or non-uniformly sampled data. Our method is also applicable to inorganic datasets, such as scans of industrial pipes or urban scenes containing networks of complex cylindrical shapes.
  [pdf]


• Y. Shen, J. Wang, and S. Navlakha (2021). A correspondence between normalization strategies in artificial and biological neural networks. Neural Comput., 33(12): 3179-3203.
  [abstract]
  Abstract: 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 review, 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 --- i.e., they both push activation patterns of hidden units towards 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 datasets. Overall, we hope this bi-directional 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.
  [pdf]


• S. Navlakha, S. Morjaria, R. Perez-Johnston, A. Zhang, and Y. Taur (2021). Projecting COVID-19 disease severity in cancer patients using purposefully-designed machine learning. BMC Infect. Dis. 21, 1:391.
  [abstract]
  Abstract: 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. 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). Our algorithm classified patients into these classes with an area under the receiver operating characteristic curve (AUROC) ranging from 70-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. 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.
  [pdf] [press release] [yahoo] [medical research]


• Y. Liang et al. (2021). Can a fruit fly learn word embeddings? To appear in the Intl. Conf. on Learning Representations (ICLR), 2021.
  [abstract]
  Abstract: The mushroom body of the fruit fly brain is one of the best studied systems in neuroscience. At its core it consists of a population of Kenyon cells, which receive inputs from multiple sensory modalities. These cells are inhibited by the anterior paired lateral neuron, thus creating a sparse high dimensional representation of the inputs. In this work we study a mathematical formalization of this network motif and apply it to learning the correlational structure between words and their context in a corpus of unstructured text, a common natural language processing (NLP) task. We show that this network can learn semantic representations of words and can generate both static and context-dependent word embeddings. Unlike conventional methods (e.g., BERT, GloVe) that use dense representations for word embedding, our algorithm encodes semantic meaning of words and their context in the form of sparse binary hash codes. The quality of the learned representations is evaluated on word similarity analysis, word-sense disambiguation, and document classification. It is shown that not only can the fruit fly network motif achieve performance comparable to existing methods in NLP, but, additionally, it uses only a fraction of the computational resources (shorter training time and smaller memory footprint).
  [pdf] [demo] [discover magazine]

 +2020

• S. Sultan, J. Snider, A. Conn, M. Li, C. N. Topp, and S. Navlakha (2020). A statistical growth property of plant root architectures. Plant Phenomics, 2020, 1-11.
  [abstract]
  Abstract: Numerous types of biological branching networks, with varying shapes and sizes, are used to acquire and distribute resources. Here, we show that plant root and shoot architectures share a fundamental design property. We studied the spatial density function of plant architectures, which specifies the probability of finding a branch at each location in the 3-dimensional volume occupied by the plant. We analyzed 1645 root architectures from four species and discovered that the spatial density functions of all architectures are population-similar. This means that despite their apparent visual diversity, all of the roots studied share the same basic shape, aside from stretching and compression along orthogonal directions. Moreover, the spatial density of all architectures can be described as variations on a single underlying function: a Gaussian density truncated at a boundary of roughly three standard deviations. Thus, the root density of any architecture requires only four parameters to specify: the total mass of the architecture and the standard deviations of the Gaussian in the three (x,y,z) growth directions. Plant shoot architectures also follow this design form, suggesting that two basic plant transport systems may use similar growth strategies.
  [pdf]



• Y. Shen, S. Dasgupta, and S. Navlakha (2020). Habituation as a neural algorithm for online odor discrimination. Proc. Natl. Acad. Sci. USA, 117, 22:12402-12410.
  [abstract]
  Abstract: Habituation is a form of simple memory that suppresses neural activity to repeated, neutral stimuli. This process is critical in helping organisms guide attention towards 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 understand the effects of habituation in other more sophisticated neural systems.
  [pdf] [code] [press release] [inverse] [tbr news media]



• I. Ziamtsov and S. Navlakha (2020). Plant 3D (P3D): A plant phenotyping toolkit for 3D point clouds. Bioinformatics, 36(12): 3949-3950.
  [abstract]
  Abstract: Developing methods to efficiently analyze 3D point cloud data of plant architectures remains 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 P3D 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.
  [pdf] [code]



• M. J. Wilkinson et al. (2020). Ten-hour time-restricted eating reduces weight, blood pressure, and atherogenic lipids in patients with metabolic syndrome. Cell Metab., 31, 1:92-104.e5.
  [abstract]
  Abstract: In animal models, time-restricted feeding (TRF) can prevent and reverse aspects of metabolic diseases. Time-restricted eating (TRE) in human pilot studies reduces the risks of metabolic diseases in otherwise healthy individuals. However, patients with diagnosed metabolic syndrome often undergo pharmacotherapy, and it has never been tested whether TRE can act synergistically with pharmacotherapy in animal models or humans. In a single-arm, paired-sample trial, 19 participants with metabolic syndrome and a baseline mean daily eating window of ≥14 h, the majority of whom were on a statin and/or antihypertensive therapy, underwent 10 h of TRE (all dietary intake within a consistent self-selected 10 h window) for 12 weeks. We found this TRE intervention improves cardiometabolic health for patients with metabolic syndrome receiving standard medical care including high rates of statin and anti-hypertensive use. TRE is a potentially powerful lifestyle intervention that can be added to standard medical practice to treat metabolic syndrome.
  [pdf] [press release]

 +2019

• I. Ziamtsov and S. Navlakha (2019). Machine learning approaches to improve three basic plant phenotyping tasks using 3D point clouds. Plant Physiol., 181, 4:1425-1440.
  [abstract]
  Abstract: Developing automated methods to efficiently process large volumes of point cloud data remains a grand challenge for 3D plant phenotyping applications. Here, we develop a collection of machine learning methods to tackle three primary challenges in plant phenotyping: lamina/stem classification, lamina counting, and stem skeletonization. For classification, we assess and validate 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. Using deep learning, we achieved 97.8% accuracy on classifying lamina versus stems; critically, we also demonstrate 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 over-segmentation; this method achieved 86.6% accuracy, outperforming prior methods developed for this problem. Finally, for stem skeletonization, we developed an enhanced tip detection technique that ran an order of magnitude faster and that generated more precise skeleton architectures compared to prior methods. Overall, our improvements enables higher throughput and accurate extraction of phenotypic properties from 3D point cloud data.
  [pdf] [press release]



• A. Conn, A. Chandrasekhar, M. van Rongen, O. Leyser, J. Chory, and S. Navlakha (2019). Network trade-offs and homeostasis in Arabidopsis shoot architectures. PLoS Comput. Biol., 15, 9:e1007325.
  [abstract]
  Abstract: Understanding the optimization principles 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 significantly 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.
  [pdf] [code and data]



• J. Y. Suen and S. Navlakha (2019). Travel in city road networks follows similar trade-off transport principles as neural and plant arbors. J. R. Soc. Interface, 16, 154:20190041.
  [abstract]
  Abstract: Both engineered and biological transportation networks face trade-offs in their design. Network users desire to quickly get from one location in the network to another, whereas network planners need to minimize costs in building infrastructure. Here, we use the theory of Pareto optimality to study this design trade-off in road networks of 101 cities, with wide-ranging population sizes, land areas, and geographies. Using a simple one parameter trade-off function, we find that most cities lie near the Pareto front and significantly closer to the front than expected by alternate design structures. To account for other optimization dimensions or constraints that may be important (e.g., traffic congestion, geography), we performed a higher-order Pareto optimality analysis and found that most cities analyzed lie within a region of design space bounded by only 4 archetypal cities. The trade-offs studied here are also faced and well-optimized by two biological transport networks --- neural arbors in the brain and branching architectures of plant shoots --- suggesting similar design principles across some biological and engineered transport systems.
  [pdf] [code]



• A. Chandrasekhar and S. Navlakha (2019). Neural arbors are Pareto optimal. Proc. R. Soc. B., 286(1902):20182727.
  [abstract]
  Abstract: 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. Analyzing 14145 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.
  [pdf]



• S. Rashid et al. (2019). Adjustment in tumbling rates improves bacterial chemotaxis on obstacle-laden terrains. Proc. Natl. Acad. Sci. USA, 116, 24:11770-11775.
  [abstract]
  Abstract: 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..
  [pdf] [press release] [naked scientists] [nature reviews microbiology]



• S. Rashid, S. Singh, S. Navlakha, and Z. Bar-Joseph (2019). A bacterial based distributed gradient descent model for mass scale evacuations. Swarm Evol. Comput., 46, 97-103.
  [abstract]
  Abstract: Most current methods for distributed agent coordination rely on large messages, complex computations and unique identifiability of communicating agents. To allow for efficient coordination in constrained environments with limited communication and computational resources, we derived a distributed gradient descent (DGD) algorithm based on how bacteria cells interact when searching for food. The method combines the (static) map of each agent with messages received from other agents. Both messages and computations are restricted to a simple vocabulary and are aggregated so no knowledge of the sender is required. In contrast to most prior DGD methods, where the interaction graph is assumed to be static, we allow for dynamic changes in the neighborhood graph for each agent. We prove that the method still correctly converges to a local optimum in such dynamic settings. We tested the usefulness of the method in simulations of mass-scale emergency evacuations in which obstacles are dynamically added to a given environment. We show that our bacterial based model can drastically reduce evacuation times in complex and realistic environments, when compared to prior models.
  [pdf]

 +2018

• S. Dasgupta, T. C. Sheehan, C. F. Stevens, and S. Navlakha (2018). A neural data structure for novelty detection. Proc. Natl. Acad. Sci. USA, 115, 51:13093-13098.
  [abstract]
  Abstract: Novelty detection is a fundamental biological problem that organisms must solve to determine if 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 noticed that the fruit fly olfactory circuit evolved a variant of a Bloom filter to assess the novelty of odors. Compared to 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 new 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 new strategies for novelty detection in computational systems.
  [pdf] [press release] [video] [nautilus]



• J. G. Fleischer, R. Schulte, H. H. Tsai, S. Tiyagi, A. Ibarra, M. N. Shokhirev, L. Huang, M. W. Hetzer, and S. Navlakha (2018). Predicting age from the transcriptome of human dermal fibroblasts. Genome Biol., 19, 1:221.
  [abstract]
  Abstract: Biomarkers of aging can be used to assess the health of individuals and to study aging and age- related diseases. We generate a large dataset of genome-wide RNA-seq profiles of human dermal fibroblasts from 133 people aged 1 to 94 years old to test whether signatures of aging are encoded within the transcriptome. We develop an ensemble machine learning method that predicts age to a median error of 4 years, outperforming previous methods used to predict age. The ensemble was further validated by testing it on ten progeria patients, and our method is the only one that predicts accelerated aging in these patients.
  [pdf] [code] [press release] [san diego union tribune] [tech times] [pew trusts]



• S. Navlakha, Z. Bar-Joseph, and A. L. Barth (2018). Network design and the brain. Trends Cogn. Sci., 22, 1:64-78.
  [abstract]
  Abstract: Neural circuits have evolved to accommodate similar information processing challenges as those faced by engineered systems. Here, we compare neural versus engineering strategies for constructing networks. During circuit development, synapses are massively over-produced and then pruned back over time, whereas in engineered networks, connections are initially sparse and are then added over time. We provide a computational perspective on these two different approaches, including discussion of how and why they are used, insights that one can provide the other, and areas for future joint investigation. By thinking algorithmically about the goals, constraints, and optimization principles employed by neural circuits, we can develop brain-derived strategies for enhancing network design, while also stimulating experimental hypotheses about circuit development and function.
  [pdf]



• A. Chandrasekhar, D. M. Gordon, and S. Navlakha (2018). A distributed algorithm to maintain and repair the trail networks of arboreal ants. Nature Sci. Rep., 8, 1:9297.
  [abstract]
  Abstract: We study how the arboreal turtle ant (Cephalotes goniodontus) solves a fundamental computing problem: maintaining a trail network and finding alternative paths to route around broken links in the network. Turtle ants form a routing backbone of foraging trails linking several nests and temporary food sources. This species travels only in the trees, so their foraging trails are constrained to lie on a natural graph formed by overlapping branches and vines in the tangled canopy. Links between branches, however, can be ephemeral, easily destroyed by wind, rain, or animal movements. Here we report a biologically feasible distributed algorithm, parameterized using field data, that can plausibly describe how turtle ants maintain the routing backbone and find alternative paths to circumvent broken links in the backbone. We validate the ability of this probabilistic algorithm to circumvent simulated breaks in synthetic and real-world networks, and we derive an analytic explanation for why certain features are crucial to improve the algorithm’s success. Our proposed algorithm uses fewer computational resources than common distributed graph search algorithms, and thus may be useful in other domains, such as for swarm computing or for coordinating molecular robots.
  [pdf] [bbc podcast] [wired]



• J. How and S. Navlakha (2018). Evidence for Rentian scaling of functional modules in diverse biological networks. Neural Comput., 30, 8:2210-2244.
  [abstract]
  Abstract: 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 inter-module 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 6 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 C. 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.
  [pdf]



• P. Beukema et al. (2018). TrpM8-mediated somatosensation in mouse neocortex. J. Comp. Neurol., 526(9):144-1456.
  [abstract]
  Abstract: Somatosensation is a complex sense mediated by more than a dozen distinct neural subtypes in the periphery. Although pressure and touch sensation have been mapped to primary somatosensory cortex in rodents, it has been controversial whether pain and temperature inputs are also directed to this area. Here we use a well-defined somatosensory modality, cool sensation mediated by peripheral TrpM8-receptors, to investigate the neural substrate for cool perception in the mouse neocortex. Using activation of cutaneous TrpM8 receptor-expressing neurons, we identify candidate neocortical areas responsive for cool sensation. Initially, we optimized TrpM8 stimulation and determined that menthol, a selective TrpM8 agonist, was more effective than cool stimulation at inducing expression of the immediate-early gene c-fos in the spinal cord. We developed a broad-scale brain survey method for identification of activated brain areas, using automated methods to quantify c-fos immunoreactivity (fos-IR) across animals. Brain areas corresponding to the posterior insular cortex and secondary somatosensory (S2) show elevated fos-IR after menthol stimulation, in contrast to weaker activation in primary somatosensory cortex (S1). In addition, menthol exposure triggered fos-IR in piriform cortex, the amygdala, and the hypothalamus. Menthol-mediated activation was absent in TrpM8-knock-out animals. Our results indicate that cool somatosensory input broadly drives neural activity across the mouse brain, with neocortical signal most elevated in the posterior insula, as well as S2 and S1. These findings are consistent with data from humans indicating that the posterior insula is specialized for somatosensory information encoding temperature, pain, and gentle touch.
  [pdf] [press release]

 +2017

• S. Dasgupta, C. F. Stevens, and S. Navlakha (2017). A neural algorithm for a fundamental computing problem. Science, 358, 6364:793-796.
  [abstract]
  Abstract: Similarity search — for example, identifying similar images in a database or similar documents on the web — is a fundamental computing problem faced by large-scale information retrieval systems. We discovered that the fruit fly olfactory circuit solves this problem with a variant of a computer science algorithm (called locality-sensitive hashing). The fly circuit assigns similar neural activity patterns to similar odors, so that behaviors learned from one odor can be applied when a similar odor is experienced. The fly algorithm, however, uses three computational strategies that depart from traditional approaches. These strategies can be translated to improve the performance of computational similarity searches. This perspective helps illuminate the logic supporting an important sensory function and provides a conceptually new algorithm for solving a fundamental computational problem.
  [pdf] [biorxiv] [press art] [press release] [forbes] [scientific american] [the verge] [sd union tribune] [nautilus] [smithsonian] [seeker] [cbc news] [medium w/ code] [quanta magazine] [science in the classroom] [video]



• A. Conn, U. Pedmale, J. Chory, and S. Navlakha (2017). High-resolution laser scanning reveals plant architectures that reflect universal network design principles. Cell Syst., 5, 1:53-62.e3.
  [abstract]
  Abstract: Transport networks serve critical functions in biological and engineered systems, and yet their design requires trade-offs between competing objectives. Due to their sessile lifestyle, plants need to optimize their architecture to efficiently acquire and distribute resources, while also minimizing costs in building infrastructure. To understand how plants resolve this design tradeoff, we used high-precision three-dimensional laser scanning to map the architectures of tomato, tobacco, or sorghum plants grown in several environmental conditions and through multiple developmental time-points, scanning in total 505 architectures from 37 plants. Using a graph-theoretic algorithm we developed to evaluate design strategies, we find that plant architectures lie along the Pareto front between two simple length-based objectives -- minimizing total branch length and minimizing nutrient transport distance -- thereby conferring a selective fitness advantage for plant transport processes. The location along the Pareto front can distinguish amongst species and conditions, suggesting that during evolution, natural selection may employ common network design principles despite different optimization trade-offs.
  [pdf] [code and data] [journal cover] [press art] [press release] [popular science] [sd union tribune] [video]



• A. Conn, U. Pedmale, J. Chory, C. F. Stevens, and S. Navlakha (2017). A statistical description of plant shoot architecture. Curr. Biol., 27, 14:2078-2088.e3.
  [abstract]
  Abstract: Plant architectures can be characterized statistically by their spatial density function, which specifies the probability of finding a branch at each location in the territory occupied by a plant. Using high-precision 3D scanning, we analyzed 557 plant shoot architectures, representing 3 species, grown across 3-5 environmental conditions, and through 20-30 developmental time-points. We found two elegant properties in the spatial density functions of these architectures: all functions could be nearly modified in one direction without affecting the density in orthogonal directions (called separability), and all functions shared the same underlying shape, aside from stretching and compression (called self-similarity). Surprisingly, despite their striking visual diversity, we discovered that all architectures could be described as variations on a single underlying function: a Gaussian density function truncated at roughly two standard deviations. We also observed systematic variation in the spatial density functions across species, growth conditions, and time, which suggests functional specialization despite following the same general design form.
  [pdf] [code and data] [press art] [press release] [video]



• J. Y. Suen and S. Navlakha (2017). Using inspiration from synaptic plasticity rules to optimize traffic flow in distributed engineered networks. Neural Comput., 29, 5:1204-1228.
  [abstract]
  Abstract: 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 only depends 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 via 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.
  [pdf] [press release] [press art] [science daily] [daily mail]



• S. Navlakha (2017). Learning the structural vocabulary of a network. Neural Comput., 29, 2:287-312.
  [abstract]
  Abstract: 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.
  [pdf] [journal cover]

 +2016

• S. Singh, S. Rashid, S. Navlakha, and Z. Bar-Joseph (2016). Distributed gradient descent in bacterial food search. Proc. 20th Intl. Conf. on Research in Computational Molecular Biology (RECOMB).
  [abstract]
  Abstract: Communication and coordination play a major role in the ability of bacterial cells to adapt to ever changing environments and conditions. Recent work has shown that such coordination underlies several aspects of bacterial responses including their ability to develop antibiotic resistance. Here we develop a new distributed gradient descent method that helps explain how bacterial cells collectively search for food in harsh environments using extremely limited communication and computational complexity. This method can also be used for computational tasks when agents are facing similarly restricted conditions. We formalize the communication and computation assumptions required for successful coordination and prove that the method we propose leads to convergence even when using a dynamically changing interaction network. The proposed method improves upon prior models suggested for bacterial foraging despite making fewer assumptions. Simulation studies and analysis of experimental data illustrate the ability of the method to explain and further predict several aspects of bacterial swarm food search.
  [pdf]

 +2015

• S. Navlakha, A. L. Barth, and Z. Bar-Joseph (2015). Decreasing-rate pruning optimizes the construction of efficient and robust networks. PLoS Comput. Biol., 11(7): e1004347.
  [abstract]
  Abstract: Robust, efficient, and low-cost networks are advantageous in both biological and engineered systems. During neural network development in the brain, synapses are massively over-produced and then pruned-back over time. This strategy is not commonly used when designing engineered networks, since adding connections that will soon be removed is considered wasteful. Here, we show that for large distributed routing networks, network function is markedly enhanced by hyper-connectivity followed by aggressive pruning and that the global rate of pruning, a developmental parameter not previously studied by experimentalists, plays a critical role in optimizing network structure. We first used high-throughput image analysis techniques to quantify the rate of pruning in the mammalian neocortex across a broad developmental time window and found that the rate is decreasing over time. Based on these results, we analyzed a model of computational routing networks and show using both theoretical analysis and simulations that decreasing rates lead to more robust and efficient networks compared to other rates. We also present an application of this strategy to improve the distributed design of airline networks. Thus, inspiration from neural network formation suggests effective ways to design distributed networks across several domains.
  [pdf] [press release] [fermat's library]



• S. Navlakha and Z. Bar-Joseph (2015). Distributed information processing in biological and computational systems. Commun. ACM, 58(1), 94–102.
  [abstract]
  Abstract: Two converging technologies have led to increased interest in the relationship between information processing in biological and distributed computational systems. On the one hand, we can now experimentally study biological networks at a much finer detail than ever before. On the other, mobile and sensor networks have become pervasive and require new algorithms to improve their robustness and handle their dynamic nature. In this review, we focus on the similarities and differences between information processing problems in both domains. We discuss the constraints that affect the communication models under which these systems operate, the trade-off between run-time and robustness, and the various algorithmic principles utilized by both domains. Our hope is that this review will allow researchers to identify the most promising biological and computational problems that can be studied concurrently to improve our understanding of both fields.
  [pdf] [video]



• S. Navlakha, C. Faloutsos, Z. Bar-Joseph (2015). MassExodus: Modeling evolving networks in harsh environments. Proc. of the European Conf. on Machine Learning and Principles and Practices of Knowledge Discovery and Databases (ECML/PKDD). Journal version in Data Mining and Knowledge Discovery (DAMI), 29(5), 1-22.
  [abstract]
  Abstract: Consider networks in harsh environments, where nodes may be lost due to failure, attack, or infection -- how is the topology affected by such events? Can we mimic and measure the effect? We propose a new generative model of network evolution in dynamic and harsh environments. Our model can reproduce the range of topologies observed across known robust and fragile biological networks, as well as several additional transport, communication, and social networks. We also develop a new optimization measure to evaluate robustness based on preserving high connectivity following random or adversarial bursty node loss. Using this measure, we evaluate the robustness of several real-world networks and propose a new distributed algorithm to construct secure networks operating within malicious environments.
  [pdf]



• S. Chandrasekaran, S. Navlakha, N. J. Audette, D. D. McCreary, J. Suhan, Z. Bar-Joseph, and A. L. Barth (2015). Unbiased, high-throughput electron microscopy analysis of experience-dependent synaptic changes in the neocortex. J. Neurosci., 35(50): 16450-16462.
  [abstract]
  Abstract: 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.
  [pdf] [press art] [journal cover] [science daily]

 +2014

• S. Navlakha, X. He, C. Faloutsos, Z. Bar-Joseph (2014). Topological properties of robust biological and computational networks. J. R. Soc. Interface, 11(96):20140283.
  [abstract]
  Abstract: Network robustness is an important principle in biology and engineering. Previous studies of global networks have identified both redundancy and sparseness as topological properties used by robust networks. By focusing on molecular subnetworks, or modules, we show that module topology is tightly linked to the level of environmental variability (noise) the module expects to encounter. Modules internal to the cell that are less exposed to environmental noise are more connected and less robust than external modules. A similar design principle is used by several other biological networks. We propose a simple change to the evolutionary gene duplication model which gives rise to the rich range of module topologies observed within real networks. We apply these observations to evaluate and design communication networks that are specifically optimized for noisy or malicious environments. Combined, joint analysis of biological and computational networks leads to novel algorithms and insights benefiting both fields.
  [pdf] [science daily] [motherboard vice]

 +2013

• S. Navlakha, P. Ahammad, E. W. Myers (2013). Unsupervised segmentation of noisy electron microscopy images using salient watersheds and region merging. BMC Bioinformatics, 14:294.
  [abstract]
  Abstract: Segmenting electron microscopy (EM) images of cellular and subcellular processes in the nervous system is a key step in many bioimaging pipelines involving classification and labeling of ultrastructures. However, fully automated techniques to segment images are often susceptible to noise and heterogeneity in EM images (e.g. different histological preparations, different organisms, different brain regions, etc.). Supervised techniques to address this problem are often helpful but require large sets of training data, which are often difficult to obtain in practice, especially across many conditions. We propose a new, principled unsupervised algorithm to segment EM images using a two-step approach: edge detection via salient watersheds following by robust region merging. We performed experiments to gather EM neuroimages of two organisms (mouse and fruit fly) using different histological preparations and generated manually curated ground-truth segmentations. We compared our algorithm against several state-of-the-art unsupervised segmentation algorithms and found superior performance using two standard measures of under-and over-segmentation error. Our algorithm is general and may be applicable to other large-scale segmentation problems for bioimages.
  [pdf] [code]



• S. Navlakha, J. Suhan, A. L. Barth, and Z. Bar-Joseph (2013). A high-throughput framework to detect synapses in electron microscopy images. Proc. 21st Intl. Conf. on Intelligent Systems for Molecular Biology/12th European Conference on Computational Biology (ISMB/ECCB), 2013. Journal version in Bioinformatics, 29(13):i9-17.
  [abstract]
  Abstract: Synaptic connections underlie learning and memory in the brain and are dynamically formed and eliminated during development and in response to stimuli. Quantifying changes in overall number and strength of synapses is an important pre-requisite for studying connectivity and plasticity in these cases or in diseased conditions. Unfortunately, most techniques to detect such changes are either low-throughput (e.g. electrophysiology), prone to error and difficult to automate (e.g. standard electron microscopy), or too coarse (e.g. MRI) to provide accurate and large-scale measurements. To facilitate high-throughput analyses, we used a 50-year-old experimental technique to selectively stain for synapses in electron microscopy (EM) images and developed a machine learning framework to automatically detect synapses in these images. To validate our method we experimentally imaged brain tissue of the somatosensory cortex in four mice. We detected thousands of synapses in these images and demonstrate the accuracy of our approach using cross-validation with manually labeled data and by comparing against existing algorithms and against tools that process standard EM images. We also used a semi-supervised algorithm that leverages unlabeled data to overcome sample heterogeneity and improve performance. Our algorithms are highly efficient and scalable and are freely available for others to use.
  [pdf] [code] [video of talk]

 +2012

• S. Navlakha, A. Gitter, and Z. Bar-Joseph (2012). A network-based approach for predicting missing pathway interactions. PLoS Comput. Biol., 8(8):e1002640.
  [abstract]
  Abstract: Embedded within large-scale protein interaction networks are signaling pathways that encode response cascades in the cell. Unfortunately, even for well-studied species like S. cerevisiae, only a fraction of all true protein interactions are known, which makes it difficult to reason about the exact flow of signals and the corresponding causal relations in the network. To help address this problem, we introduce a framework for predicting new interactions that aid connectivity between upstream proteins (sources) and downstream transcription factors (targets) of a particular pathway. Our algorithms attempt to globally minimize the distance between sources and targets by finding a small set of shortcut edges to add to the network. Unlike existing algorithms for predicting general protein interactions, by focusing on proteins involved in specific responses our approach homes-in on pathway-consistent interactions by reducing source-target distances. We applied our method to extend pathways in osmotic stress response in yeast and identified several missing interactions, some of which are supported by published reports. We also performed experiments that support a novel interaction not previously reported. Our framework is general and may be applicable to edge prediction problems in other domains.
  [pdf] [code]

 +2011

• S. Navlakha and Z. Bar-Joseph (2011). Algorithms in nature: the convergence of systems biology and computational thinking. Nature/EMBO Mol. Syst. Biol., 7:546.
  [abstract]
  Abstract: Computer science and biology have enjoyed a long and fruitful relationship for decades. Biologists rely on computational methods to analyze and integrate large data sets, while several computational methods were inspired by the high-level design principles of biological systems. Recently, these two directions have been converging. In this review, we argue that thinking computationally about biological processes may lead to more accurate models, which in turn can be used to improve the design of algorithms. We discuss the similar mechanisms and requirements shared by computational and biological processes and then present several recent studies that apply this joint analysis strategy to problems related to coordination, network analysis, and tracking and vision. We also discuss additional biological processes that can be studied in a similar manner and link them to potential computational problems. With the rapid accumulation of data detailing the inner workings of biological systems, we expect this direction of coupling biological and computational studies to greatly expand in the future.
  [pdf] [website]



• S. Navlakha and C. Kingsford (2011). Network archaeology: uncovering ancient networks from present-day interactions. PLoS Comput. Biol., 7(4):e1001119. Presented at the 6th RECOMB Systems Biology Satellite Conference, 2010.
  [abstract]
  Abstract: What proteins interacted in a long-extinct ancestor of yeast? How have different members of a protein complex assembled together over time? Our ability to answer such questions has been limited by the unavailability of ancestral protein-protein interaction (PPI) networks. To overcome this limitation, we propose several novel algorithms to reconstruct the growth history of a present-day network. Our likelihood-based method finds a probable previous state of the graph by applying an assumed growth model backwards in time. This approach retains node identities so that the history of individual nodes can be tracked. Using this methodology, we estimate protein ages in the yeast PPI network that are in good agreement with sequence-based estimates of age and with structural features of protein complexes. Further, by comparing the quality of the inferred histories for several different growth models (duplication-mutation with complementarity, forest fire, and preferential attachment), we provide additional evidence that a duplication-based model captures many features of PPI network growth better than models designed to mimic social network growth. From the reconstructed history, we model the arrival time of extant and ancestral interactions and predict that complexes have significantly re-wired over time and that new edges tend to form within existing complexes. We also hypothesize a distribution of per-protein duplication rates, track the change of the network's clustering coefficient, and predict paralogous relationships between extant proteins that are likely to be complementary to the relationships inferred using sequence alone. Finally, we infer plausible parameters for the model, thereby predicting the relative probability of various evolutionary events. The success of these algorithms indicates that parts of the history of the yeast PPI are encoded in its present-day form.
  [pdf] [press art] [website] [mit tech review] [engadget]



• R. Patro, E. Sefer, J. Malin, G. Marçais, S. Navlakha, and C. Kingsford (2011). Parsimonious reconstruction of network evolution. Workshop on Algorithms in Bioinformatics (WABI). Journal version in Algorithms Mol. Biol., 7(1):25, 2012.
  [abstract]
  Abstract: We consider the problem of reconstructing a maximally parsimonious history of network evolution under models that support gene duplication and loss and independent interaction gain and loss. We introduce a combinatorial framework for encoding network histories, and we give a fast procedure that, given a set of duplication histories, in practice finds network histories with close to the minimum number of interaction gain or loss events. In contrast to previous studies, our method does not require knowing the relative ordering of unrelated duplication events. Results on simulated histories suggest that common ancestral networks can be accurately reconstructed using this parsimony approach.
  [pdf]



• A. Thor et al. (2011). Link prediction for annotation graphs using graph summarization. Proc. 10th Intl. Semantic Web Conference (ISWC), 7031:714-729.
  [abstract]
  Abstract: Annotation graph datasets are a natural representation of scientific knowledge. They are common in the life sciences where genes or proteins are annotated with controlled vocabulary terms (CV terms) from ontologies. The W3C Linking Open Data (LOD) initiative and semantic Web technologies are playing a leading role in making such datasets widely available. Scientists can mine these datasets to discover patterns of annotation. While ontology alignment and integration across datasets has been explored in the context of the semantic Web, there is no current approach to mine such patterns in annotation graph datasets. In this paper, we propose a novel approach for link prediction; it is a preliminary task when discovering more complex patterns. Our prediction is based on a complementary methodology of graph summarization (GS) and dense subgraphs (DSG). GS can exploit and summarize knowledge captured within the ontologies and in the annotation patterns. DSG uses the ontology structure, in particular the distance between CV terms, to filter the graph, and to find promising subgraphs. We develop a scoring function based on multiple heuristics to rank the predictions. We perform an extensive evaluation on Arabidopsis thaliana genes.
  [pdf]

 +2010

• S. Navlakha and C. Kingsford (2010). The power of protein interaction networks for associating genes with diseases. Bioinformatics, 26(8):1057-63.
  [abstract]
  Abstract: Understanding the association between genetic diseases and their causal genes is an important problem concerning human health. With the recent influx of high-throughput data describing interactions between gene products, scientists have been provided a new avenue through which these associations can be inferred. Despite the recent interest in this problem, however, there is little understanding of the relative benefits and drawbacks underlying the proposed techniques. We assessed the utility of physical protein interactions for determining gene–disease associations by examining the performance of seven recently developed computational methods (plus several of their variants). We found that random-walk approaches individually outperform clustering and neighborhood approaches, although most methods make predictions not made by any other method. We show how combining these methods into a consensus method yields Pareto optimal performance. We also quantified how a diffuse topological distribution of disease-related proteins negatively affects prediction quality and are thus able to identify diseases especially amenable to network-based predictions and others for which additional information sources are absolutely required. The predictions made by each algorithm considered are available online.
  [pdf] [website] [faculty of 1000 review]



• S. Navlakha and C. Kingsford (2010). Exploring biological network dynamics with ensembles of graph partitions. Proc. 15th Intl. Pacific Symposium on Biocomputing (PSB), 166-177.
  [abstract]
  Abstract: Unveiling the modular structure of biological networks can reveal important organizational patterns in the cell. Many graph partitioning algorithms have been proposed towards this end. However, most approaches only consider a single, optimal decomposition of the network. In this work, we make use of the multitude of near-optimal clusterings in order to explore the dynamics of network clusterings and how those dynamics relate to the structure of the underlying network. We recast the modularity optimization problem as an integer linear program with diversity constraints. These constraints produce an ensemble of dissimilar but still highly modular clusterings. We apply our approach to four social and biological networks and show how optimal and near-optimal solutions can be used in conjunction to identify deeper community structure in the network, including inter-community dynamics, communities that are especially resilient to change, and core-and-peripheral community members.
  [pdf]



• G. Duggal, S. Navlakha, M. Girvan, and C. Kingsford (2010). Uncovering many views of biological networks using ensembles of graph partitions. Proc. 1st Intl. Workshop on Discovering, Summarizing, and Using Multiple Clusterings (KDD MultiClust), 2010:9.
  [abstract]
  Abstract: Densely interacting regions of biological networks often correspond to functional modules such as protein complexes. Most algorithms proposed to uncover modules, however, produce one clustering that only reveals a single view of how the cell is organized. We describe two new methods to find ensembles of provably near-optimal modularity partitions that lie within a heuristically constrained search space. We also show how to count the number of solutions in this space that exist within a bounded modularity range. We apply our algorithms to a protein interaction network for S. cerevisiae and show how fine-grained differences between near-optimal partitions can be used to define robust communities. We also propose a technique to find structurally diverse nearoptimal solutions and show that these different partitions are enriched for different biological functions. Our results indicate that near-optimal solutions can represent alternative and complementary views of the network's structure.
  [pdf] [website]



• J. R. White, S. Navlakha, N. Nagarajan, M. Ghodsi, C. Kingsford, and M. Pop (2010). Alignment and clustering of phylogenetic markers - implications for microbial diversity studies. BMC Bioinformatics, 11:152.
  [abstract]
  Abstract: Molecular studies of microbial diversity have provided many insights into the bacterial communities inhabiting the human body and the environment. A common first step in such studies is a survey of conserved marker genes (primarily 16S rRNA) to characterize the taxonomic composition and diversity of these communities. To date, however, there exists significant variability in analysis methods employed in these studies. Here we provide a critical assessment of current analysis methodologies that cluster sequences into operational taxonomic units (OTUs) and demonstrate that small changes in algorithm parameters can lead to significantly varying results. Our analysis provides strong evidence that the species-level diversity estimates produced using common OTU methodologies are inflated due to overly stringent parameter choices. We further describe an example of how semi-supervised clustering can produce OTUs that are more robust to changes in algorithm parameters. Our results highlight the need for systematic and open evaluation of data analysis methodologies, especially as targeted 16S rRNA diversity studies are increasingly relying on high-throughput sequencing technologies. All data and results from our study are available through the JGI FAMeS website.
  [pdf]

 +2009

• S. Navlakha, J. White, N. Nagarajan, M. Pop, and C. Kingsford (2009). Finding biologically accurate clusterings in hierarchical tree decompositions using the variation of information. Proc. 14th Intl. Conf. on Research in Computational Molecular Biology (RECOMB), 5541:400–417. Journal version in J. Comput. Biol., 17(3):503–516, 2010.
  [abstract]
  Abstract: Hierarchical clustering is a popular method for grouping to- gether similar elements based on a distance measure between them. In many cases, annotations for some elements are known beforehand, which can aid the clustering process. We present a novel approach for decom- posing a hierarchical clustering into the clusters that optimally match a set of known annotations, as measured by the variation of information metric. Our approach is general and does not require the user to enter the number of clusters desired. We apply it to two biological domains: finding protein complexes within protein interaction networks and identifying species within metagenomic DNA samples. For these two applications, we test the quality of our clusters by using them to predict complex and species membership, respectively. We find that our approach generally outperforms the commonly used heuristic methods.
  [pdf] [website]



• S. Navlakha, M.C. Schatz, and C. Kingsford (2009). Revealing biological modules via graph summarization. J. Comput. Biol., 16(2):253-64. Presented at the 5th RECOMB Systems Biology Satellite Conference, 2008.
  [abstract]
  Abstract: The division of a protein interaction network into biologically meaningful modules can aid with automated detection of protein complexes and prediction of biological processes and can uncover the global organization of the cell. We propose the use of a graph summarization (GS) technique, based on graph compression, to cluster protein interaction graphs into biologically relevant modules. The method is motivated by defining a biological module as a set of proteins that have similar sets of interaction partners. We show this definition, put into practice by a GS algorithm, reveals modules that are more biologically enriched than those found by other methods. We also apply GS to predict complex memberships, biological processes, and co-complexed pairs and show that in most settings GS is preferable over existing methods of protein interaction graph clustering.
  [pdf] [video of talk]

 +2008

• S. Navlakha, R. Rastogi, and N. Shrivastava (2008). Graph summarization with bounded error. Proc. 34th Intl. Conf. on Management of Data (SIGMOD), 419-432.
  [abstract]
  Abstract: We propose a highly compact two-part representation of a given graph G consisting of a graph summary and a set of corrections. The graph summary is an aggregate graph in which each node corresponds to a set of nodes in G, and each edge represents the edges between all pair of nodes in the two sets. On the other hand, the corrections portion specifies the list of edge-corrections that should be applied to the summary to recreate G. Our representations allow for both lossless and lossy graph compression with bounds on the introduced error. Further, in combination with the MDL principle, they yield highly intuitive coarse-level summaries of the input graph G. We develop algorithms to construct highly compressed graph representations with small sizes and guaranteed accuracy, and validate our approach through an extensive set of experiments with multiple real-life graph data sets. To the best of our knowledge, this is the first work to compute graph summaries using the MDL principle, and use the summaries (along with corrections) to compress graphs with bounded error.
  [pdf] [press art] [code]

 +2007

• H. Haidarian-Shahri, G. M. Namata, S. Navlakha, A. Deshpande, and N. Roussopoulos (2007). A graph-based approach to vehicle tracking in traffic camera video streams. Proc. 5th Intl. Workshop on Data Management for Sensor Networks (VLDB DMSN).
  [abstract]
  Abstract: Vehicle tracking has a wide variety of applications from law enforcement to traffic planning and public safety. However, the image resolution of the videos available from most traffic camera systems, make it difficult to track vehicles based on unique identifiers like license plates. In many cases, vehicles with similar attributes are indistinguishable from one another due to image quality issues. Often, network bandwidth and power constraints limit the frame rate, as well. In this paper, we discuss the challenges of performing vehicle tracking queries over video streams from ubiquitous traffic cameras. We identify the limitations of tracking vehicles individually in such conditions and provide a novel graph-based approach using the identity of neighboring vehicles to improve the performance. We evaluate our approach using streaming video feeds from live traffic cameras available on the Internet. The results show that vehicle tracking is feasible, even for low quality and low frame rate traffic cameras. Additionally, exploitation of the attributes of neighboring vehicles significantly improves the performance.
  [pdf]

Bio

Lab members

Funding & awards

Other writings

Other links