GoKawiilCould a computer scientist build a brain? Stan Kerstjens & Anthony M. Zador Cold Spring Harbor Laboratory Correspondence: [email protected]
How does a brain wire itself, starting from a single cell, using only the information encoded in a genome? We pose this as an engineering problem: Write a program that a single cell executes to build itself into a brain. The program must be small enough to fit in a genome, and fast enough to finish within developmental time. A computer scientist who knows little about biology quickly realizes why the obvious strategies, which developmental biology has rejected experimentally, fail at scale: The genome is too small to store per-synapse wiring, and axons searching blindly for targets would take too long. These same algorithmic constraints drive the design toward solutions that resemble the developmental strategies organisms actually use. That the same solution structure falls out of scaling limits as out of evolution suggests that features of neural development can be grounded in computational necessity rather than contingency alone. Where earlier thought experiments reached discouraging conclusions about the ability of a biologist to fix a radio1, or to understand a microprocessor2, the news here is better: The design of the brain may be recoverable, not from taking it apart, but from asking how a genome must specify it in the first place.
Suppose we hand a computer scientist the complete wiring diagram of a brain and ask: Write a program that a single cell executes to elaborate itself into this network. The program must fit in a genome-sized instruction set of about 1 gigabyte, and it must halt within a developmental time window of at most about a year. The challenge is that the algorithm must scale: It should work for the 302 neurons of C. elegans, the 10 5 10^{5} 105 neurons of a fly, the 10 8 10^{8} 108 neurons of a mouse3, and the 10 10 10^{10} 1010 neurons of a human brain4 (Fig. 1). How would someone with no knowledge of developmental biology approach this problem?
10² 10⁴ 10⁶ 10⁸ 10¹⁰ 10¹² 10 MB 100 MB 1 GB 10 GB genome size brain size (neurons) infeasible feasible C. elegans Drosophila Zebrafish Mouse Human Figure 1. The information gap. Brain size versus genome size for a range of organisms. Genome sizes vary only over about one order of magnitude, whereas brain sizes span eight. The dashed line shows where the simplest possible connectivity encoding—an adjacency matrix with one bit per pair of neurons, n 2 n^2 n 2 bits total—just fits within the genome . In the green region the genome is large enough to afford this encoding. In the red region, the brain is too large. Only C. elegans sits clearly in the feasible region, and may thus be encoded with an adjacency matrix. The brains of the other species must be encoded with a different strategy. The open question is what strategy could encode and construct these despite the computational constraints. Data sources: genome assembly lengths16–21 and neuron counts3,4,22–24. The computer scientist is, in effect, formalizing a task in the spirit of Turing5, von Neumann6, Waddington7, and Brenner8, who all saw the genome as a set of instructions for making an organism rather than a description of one. Formalizing the task helps to identify the algorithmic strategies that are both feasible and tractable. Working through the exercise, we find that strategies that work for a small nervous system hit hard walls as the network grows, and the constraints narrow the field to a small class of solutions. The convergence between theory and experiment informs both directions. For developmental neuroscientists, it formalizes familiar molecular mechanisms as solutions to a well-defined algorithmic problem and picks out which features of those mechanisms are computational necessities and which are free to vary. For theorists, it presents biological development as a system that solves an as-yet-unsolved computational task. Modern machine learning does not yet know how to generate large functional networks from compact descriptions, relying instead on either a large stored weight matrix copied from disk, or a training set that is orders of magnitude larger9. The initial zygote contains exactly such a description, and analyzing the developmental process may help inspire new algorithms for artificial systems. The problem and its constraints What does it mean to write a developmental program10–14? The computer scientist does not get to place neurons and wire them up from the outside, like an engineer soldering a circuit board. Instead, she must write a set of instructions that go into a single initial cell, and then she walks away. This initial cell divides, and each daughter inherits the same program and runs it independently. Each instance of the program can read only what it can sense locally: its own internal state along with molecular signals from its neighbor cells that are themselves running the same program. The cell performs actions that will build the brain: It divides, migrates, extends growth cones that navigate by reading molecular cues and form synapses upon arrival. The entire construction process is distributed and recursive, since every signal a cell reads was produced by another cell executing the same code. The programmer's sole lever is the instruction set she loads into the genome at the start, along with the cell's initial state. The program needs to yield the correct network while respecting practical constraints. We focus here on two aspects: It needs to be short enough to fit in the genome and finish in a reasonable amount of time. A human brain has n ≈ 10 10 n{\approx}10^{10} n≈1010 neurons, each of which forms connections with as many as m ≈ 10 4 m{\approx}10^{4} m≈104 targets15, for a total of as many as n × m ≈ 10 14 n \times m\approx10^{14} n×m≈1014 connections.
Big-O notation We use Big-O notation, O ( f ( n ) ) O\left(f(n)\right) O(f(n)), to describe how a cost scales with problem size n n n. The notation ignores constant factors and focuses on the growth rate: O ( n 2 ) O\left(n^2\right) O(n2) means the cost grows as the square of n n n; O ( log n ) O\left(\log n\right) O(logn) means it grows as the logarithm. A strategy is viable only if both its information requirement (space) and the total axon length it requires (time) fit within biological budgets as n n n grows from hundreds to billions. Linear or super-linear scaling (red) is usually bad: Costs explode and quickly exceed biological limits. Sub-linear scaling (green) tends to be good enough: Costs grow slowly with brain size. O(n²) O(n) O(n⅓) O(log n) biological limit (super-)linear sub-linear n time / space The program must satisfy two hard constraints. The information constraint. The instructions for building the brain must ultimately reside in the genome, which contains approximately 3 × 10 9 3 \times 10^{9} 3×109 base pairs21. Each base pair represents 2 bits, because there are four nucleotide bases. The total information content of the genome is therefore roughly 6 × 10 9 6 \times 10^{9} 6×109 bits, or about 10 10 10^{10} 1010 bits as a generous upper bound. This bound is generous as it assumes the genome has no redundancies, and that every nucleotide is devoted to brain wiring, leaving nothing for the rest of the organism. Any wiring strategy whose instructions exceed this budget cannot be the one biology uses. The budget does not vary much across species: C. elegans and a human differ by less than two orders of magnitude in genome size but by more than eight in neuron count (Fig. 1). Whatever algorithm wires a mammalian brain must scale sub-linearly with the number of neurons. The time constraint. The wiring process must complete within a developmental time window. With a bounded growth rate25–27, total axon length and developmental time are proportional: A strategy that requires growing too much axon, either transiently or permanently, also takes too long. Any viable strategy must keep both the total axon length and the total developmental time sub-linear in the number of neurons. Our computer scientist will consider three approaches over the next few sections, illustrated in Figs. 2–5. The computer scientist evaluates each approach against the problem constraints, until she finds a strategy that does not violate any. For now, she restricts herself to deterministic, activity-independent processes: Each cell executes its program without feedback from neural activity, and is not subject to noise. Plasticity, in particular, operates on connections that already exist; the problem of getting axons to the right populations in the first place is the first one she considers. Stochasticity and activity-dependent plasticity are discussed briefly in later sections.
Strategy 1: the identity approach Time O ( n ) O(n) O ( n )
Space O ( m n log n ) O(mn\log n) O ( mn lo g n ) Figure 2. The identity approach. Each neuron stores a list of target identities. Throughout Figures 2–5 a brain has n n n neurons, each connecting to m m m targets, built from a genome encoding up to 10 10 10^{10} 1 0 10 bits, and t t t is the number of cell types sharing a common wiring rule. “Time” means total axon length per target, the bottleneck being how fast a neuron can generate a length of axon. “Space” means bits of genomic instruction. In his 1974 Turing Award Lecture28, Donald Knuth stated that premature optimization is the root of all evil . Honoring his famous maxim, our computer scientist first pursues the most naive algorithm (Fig. 2): Assign every neuron a unique identity label, store in the genome a list of target labels for each neuron, and have each growth cone iterate through its list, navigating to each target and forming a synapse. But how does a growth cone find a cell with a given label? Without any map or spatial structure to exploit, the best a growth cone can do is search systematically, visiting cells until it finds a match. The problem is analogous to finding a book from an unsorted library. On average, a search turns up the right book after going through half the shelves; in the worst case, all of them. The search cost grows in proportion to the size of the collection. With n n n neurons and no navigable structure, a growth cone must extend past up to n n n cells to find one target. The total axon length per target is therefore O ( n ) O(n) O(n), growing linearly with brain size. For a human brain with n ≈ 10 10 n \approx 10^{10} n≈1010 neurons packed into a volume of about 1,300 cm 3 ^3 3, some 15 cm across4, the mean cell spacing is ∼ \sim ∼50 μ \mu μm, so an O ( n ) O(n) O(n) search extends roughly 500 km of axon per target, orders of magnitude beyond what a neuron can produce (and prune) in the weeks-to-months of development27,29. But axon length is not the only problem. The target list must come from the genome, which is the same in every cell. A neuron's genome must therefore contain not only its own targets, but a wiring list for each of the n n n neurons. Fig. 1 showed that an adjacency matrix encoding incurs an information cost on the order of O ( n 2 ) O(n^2) O(n2), or 10 20 10^{20} 1020 bits. However, this does not exploit the fact that the brain's wiring is very sparse: The vast majority of neuron pairs do not connect. Instead of listing all neuron pairs, it would be much more economical to encode, for each neuron, a list of labels for each adjacent neuron. How many bits does it take to label each neuron uniquely? With 1 bit you can distinguish 2 cells; with 2 bits, 4; with 3 bits, 8. Each additional bit doubles the number of distinct labels, so labeling n n n cells requires log 2 n \log_2 n log2n bits per label, about 33 bits for 10 10 10^{10} 1010 neurons. Each of the n n n neurons needs a list of m m m target labels, and each label is log 2 n \log_2 n log2n bits long. The total required storage is n × m × log n n \times m \times \log n n×m×logn, or O ( n m log n ) O(nm\log n) O(nmlogn) bits. For a human brain, that comes to roughly 3 × 10 15 3 \times 10^{15} 3×1015 bits, still orders of magnitude beyond the genome's 10 10 10^{10} 1010-bit capacity (the upper bound, assuming every bit in the genome was devoted to wiring up the brain, which of course it is not). Strategy 1 fails both constraints: The time required to generate the requisite axon length is too great and the list of instructions is too large. Developmental neuroscience arrived at the same conclusion. Sperry's chemoaffinity hypothesis proposed that each neuron carries a molecular identity and finds its target by label matching, the central idea of Strategy 130. Reasoning from regeneration experiments, in which severed axons re-found their original targets, Sperry suspected “literally millions, and possibly billions, of chemically differentiated neuron types, each distinguishable from all others”30. The hypothesis was generative and launched a productive search for identity molecules. That search turned up remarkable molecular diversity (Drosophila Dscam1 generates over 10,000 isoforms31, and vertebrate protocadherins create combinatorial identity codes32), but this diversity mediates local self-avoidance rather than global target selection33,34. The field has since moved from precise lock-and-key profiles toward logical recognition rules implemented in molecular machinery34–36, the same shift the scaling argument favors.
Strategy 2: the guidepost approach Time O ( n 3 ) O(\sqrt[3]{n}) O ( 3 n )
Space O ( k m n log n ) O(kmn\log n) O ( k mn lo g n ) Figure 3. The guidepost approach. Each neuron stores a sequence of waypoints to each target. Path length scales as n 1 / 3 n^{1/3} n 1/3 because n n n neurons fill a three-dimensional volume whose linear extent grows as the cube root. The search problem—finding the right partners efficiently—is the more obvious failure, so the computer scientist attacks it first (Fig. 3). Back in the unsorted library: Instead of wandering the shelves, someone provides a sequence of landmarks. To find Moby Dick, first go to the shelf with War and Peace; from there, look for Pride and Prejudice; from there, find Paradise Lost, which is near your target. Each landmark is a marker the growth cone can recognize when it arrives at that location; the growth cone reads them in sequence along its physical path. The growth cone never searches blindly; it always knows the next step. This solves the navigation problem. In Strategy 1, without directions, the growth cone had to search cell by cell, producing a path length proportional to the number of neurons n n n. Landmarks turn that exhaustive search into a direct walk: The growth cone proceeds straight toward its target, guided at each step. A directed walk through a three-dimensional volume is much shorter than an exhaustive search through it, because n n n neurons packed into three dimensions are only O ( n 3 ) O(\sqrt[3]{n}) O(3n ) cell-widths apart. The axon length per target drops from O ( n ) O(n) O(n) to O ( n 3 ) O(\sqrt[3]{n}) O(3n ). But the storage problem gets worse. The directions are specific to your starting point. Someone starting from a different shelf needs a completely different set of landmarks. Each neuron starts from a different location, so each needs its own set of directions for each target. If each path requires k k k waypoints, the genome must store n × m × k n \times m \times k n×m×k labels, each costing log n \log n logn bits as before; the space complexity is O ( n m k log n ) O(nmk \log n) O(nmklogn), exceeding Strategy 1 by a factor of k k k. The guidepost approach trades one problem for another: It shortens the path but inflates the instructions. The guidepost model of axon guidance34,37–39, in which long axonal trajectories are broken into short segments bounded by successive molecular choice points, documents the phenomenon Strategy 2 describes. The model has been enormously productive: It accounts for how axons navigate tissue boundaries, cross the midline, and enter target regions. But observing that an axon turns at a series of choice points does not account for how those points are specified. If each cue is independent, posted in the genome one waypoint at a time, the cost grows with every step, and the scaling argument rules this version out. The cheaper alternative is that the cues are not independent but readouts of an underlying order, the move Strategy 3 makes. Just as a reader who does not know the alphabet cannot tell whether a library is sorted or merely signposted shelf by shelf, the trajectory alone cannot tell the two strategies apart. The computer scientist is on the right track. Navigating by guideposts works; the problem is that the guideposts are arbitrary. Each one is an ad hoc molecular marker that the genome must specify and the growth cone must be taught to recognize. What the computer scientist needs is a systematic set of guideposts, one where every location has a predictable address.
Strategy 3: the coordinate approach not implementable Figure 4. The coordinate approach, on an external grid. Cells have addresses, and wiring rules are compact transformations on those addresses. This version uses an external Cartesian grid with displacement rules. It is not implementable, because it requires a global coordinate system that no cell can read from inside the tissue. Time O ( n 3 ) O(\sqrt[3]{n}) O ( 3 n )
... continue reading