Global optimization of cerebral cortex layout
See allHide authors and affiliations

Communicated by A. Noam Chomsky, Massachusetts Institute of Technology, Cambridge, MA, September 8, 2003 (received for review December 21, 2002)
Abstract
Functional areas of mammalian cerebral cortex seem positioned to minimize costs of their interconnections, down to a bestinabillion optimality level. The optimization problem here, originating in microcircuit design, is: Given connections among components, what is the physical placement of the components on a surface that minimizes total length of connections? Because of unfeasibility of measuring longrange “wire length” in the cortex, a simpler adjacency cost was validated. To deal with incomplete information on brain networks, a size law was developed that predicts optimization patterns in subnetworks. Macaque and cat cortex rank better in this connection optimization than the wiring of comparably structured computer chips, but somewhat worse than the macroeconomic commodityflow network among U.S. states. However, cortex wiring conforms to the size law better than the macroeconomic patterns, which may indicate cortex optimizing mechanisms involve more global processes.
Simple “save wire” generative principles from combinatorial network optimization theory predict layout of sensory areas of macaque and cat cerebral cortex. The areas appear to be positioned on the cortex to minimize interconnecting wiring, in some cases to current limits of detectability. This picture of largescale component placement optimization in the cortex resembles earlier findings for ganglion layout in the nervous system of Caenorhabditis elegans (1, 2) and for optimization of neuron arbors (3, 4), but to orders of magnitude finer optimality (5, 6). Computer searches of all of the tens of millions of alternative possible roundworm ganglion placements indicated that the actual layout of the nematode requires the least total wire length for the nervous system's 1,000 connections. On the model of these worm ganglion searches, we have worked out methods for optimality searches of layouts of cerebral cortex areas. To avoid difficulties of wire length measurement, a more manageable adjacency cost was calibrated as a surrogate. To detect optimization of subnetworks when the complete network is inaccessible and to distinguish local from largerscale optimization mechanisms, a size law was articulated (ref. 7 and www.cs.umd.edu/Library/TRs).
We present evidence that the cortex areas appear optimally placed, down to the limits of present computing resources. If these types of results are confirmed, they constitute a predictive success story of recent quantitative neuroanatomy. This is a much finer degree of neurooptimality than previously reported (e.g., refs. 3, 5, and 6). We have also analyzed nonneural networks (a benchmark computer microchip and macroeconomic patterns among U.S. states) as a calibration of these methods. Some chip layouts minimize connection costs better than chance, but worse than the cortex layouts. The economic network performs even better than the cortex, but apparently only via simple local processes.
Component placement optimization (also characterized as a quadratic assignment problem) has been a research focus in computer science for design of largescale integrated circuits (8, 9). Briefly defined, the problem is: Given connections among a set of components, find the spatial layout of the components that minimizes total connection costs. This task, like many other network optimization problems (e.g., traveling salesman), is nondeterministic polynomial (NP)time hard. The formal concept of NPhardness, and the related concept of NPcompleteness, need not be defined here (10–12); they have long been conjectured to be linked with a problem being intrinsically computationally intractable, i.e., not generally solvable without exhaustive search of all possible solutioncandidates.
Of course, a cerebral cortex is vastly more complex than the 300neuron C. elegans nervous system; it is also molded by experience much more extensively. And, even when connections are reported between two cortex areas, connection lengths and densities are usually not available. In addition, the 2D cortical sheet is intricately folded, so that measuring distance between two areas becomes a 3D problem. Observing the actual course of an axon bundle in the white matter is yet another layer of difficulty. Finally, widespread axonal bifurcation of corticocortical connections in cat and monkey visual systems has been reported, with estimates of branching ranging >30% for some populations of projecting neurons (13). Such a bifurcation can save ≈10% of the corresponding length of two separate connections (4, 14). However, cerebral connection compendia only describe links between pairs of areas (15, 16); they therefore cannot systematically represent these branchings, and so remain inaccurate as a basis for computing wire costs. Is optimization still discernable through so many barriers?
Adjacency Rule Costing
The adjacency rule is: If two components a and b are connected, then a and b are adjacent. Two components are adjacent if immediately contiguous topologically (as are, e.g., the United States and Canada). The rule is a candidate for a network wireminimizing heuristic (17); in fact, it is also extensively confirmed for macaque and cat visual cortex areas, rat olfactory areas, and C. elegans ganglia (1, 2, 18, 19). Conformance of a cortex layout to such a “myopic” adjacency rule is much more feasible to compute than its total wire length cost: Just compare interconnections and contiguities of the layout's areas and score how many ruleviolations occur. [For example, in Table 1, the seventh row VOT is {0, 2, 0, 2, 0, 1 , 0}; it adds 2 to the total cost of the actual layout, because two areas are connected (i.e., value >0) but not adjacent (i.e., not bold).]
How useful would such adjacency costing be? The basic point remains, that component placement optimization is a computationally intractable, NPhard problem; hence, a quick and dirty heuristic like the adjacency rule cannot provide a general solution to such a problem. [In fact, as noted elsewhere (18, 20), most of the worm's interganglionic connections are not to adjacent ganglia, but rather to more remote loci. Similarly for the majority of connections in macaque and in cat cortex. See Table 2, which is published as supporting information on the PNAS web site.]
So a first question would be, how closely correlated here in fact are layout wire costs and adjacency performance? As explained, we cannot expect to have accurate wire length data for cerebral cortex. However, another strategy is to use our earlier C. elegans databases as a test bed for such queries; a positive picture for the worm would motivate exploring a similar working hypothesis for the cortex. In fact, the nematode layouts that perform best for the above simple adjacency rule also perform very well in terms of wire cost. This type of comparison can be generalized: Fig. 1 is a dispersion diagram for 100,000 randomly sampled worm ganglion layouts (see Fig. 7, which is published as supporting information on the PNAS web site). The amorphous cloud of points indicates that, generally, adjacency rule conformance is not an efficient means to good wire cost. However, the narrow trail of points at the far lower left of Fig. 1 suggests a special case: extremely good, nearoptimal adjacency rule performance does correlate well with very good wire cost (see also Fig. 6).
It should be noted that Fig. 1 shows that merely connecting components to their neighbors will not optimize wire cost; only a layout that is optimized in turn for adjacency rule conformance will do that. Hence, a regress: optimal wire cost can be approximated via optimal adjacency rule conformance, but now the wire cost minimization problem has been replaced by another combinatorial optimization problem of the same NP level of computational complexity (21). [The 2D adjacencyrule placement problem is NPcomplete. It can be efficiently reduced to Hamiltonian Path (see ref. 10, problem GT39) (T. Schaefer, personal communication).] [In turn, adjacency optimization itself can be achieved via an evolutionary process such as a genetic algorithm, e.g., we have so implemented our GenAlg (22).] That the worm's connection matrix should be just such that the best adjacency rule layouts match the very cheapest wire cost ones, although the set of all others does not, may be an instance of the type of connection matrix finetuning we reported (22) for a forcedirected placement algorithm, i.e., that the worm's set of connections appears to be just such that it has relatively few local minima traps.
Size Law
So, the first provisional conclusion is that very good adjacency performance is indeed worth examining as a feasible, surrogate index of connectionoptimization for layout of cortical areas. Another difficulty is that cortical connection and adjacency information is not complete: For macaque (15) and cat (16), the anatomy is satisfactory for the visual areas, usable also for auditory and somatosensory areas, but only partial for frontallimbic areas. Therefore, any nearterm optimization analysis of the cortex will not include the entire system, but only large subsets. On the working hypothesis that the total system was perfectly optimized, what level of optimization would be expected for such a subset? To begin with, the following size law can be conjectured:
If a set of connected components is optimally placed, then, the smaller a subset of the total layout, the less optimal it will tend to be.
The idea of a proof begins with the familiar observation, that global optimality need not yield local subsystem optimality; local meansends sacrifices are often required for the best overall solution. Furthermore, as an isolated subset of the total optimized system gets smaller, its own constraints (e.g., localglobal tradeoffs) will be likely to depart more and more from those of the total layout, and so the subset by itself is less likely to be as well optimized. However, not all types of optimized networks obey such a size law: For instance, a uniform fabric mesh with just a regular, repeating pattern of connections between adjacent nodes, such as among wire intersections in chainlink fencing, will show perfect adjacencyrule optimization for all sizes of subsets (see Fig. 2).
Typical connection costs to be minimized are total wire length, or violations of an adjacency rule. For an ncomponent layout, there are n! possible layouts. Optimality of a given layout can be expressed in terms of the percentile rank of its cost relative to all other alternative layouts, i.e., the proportion of all layouts that have a lower cost.
How do neural systems behave? The size law can first be evaluated for the 11component worm ganglion system, with total layout wire length as the cost measure. A nested chain of ganglion subsets was generated, each composed of contiguous elements, proceeding from head to tail, from 4 to the full 11 components. The cost of each subset of the actual layout was compared with all possible alternative layouts of that subset of components. (Components external, but immediately contiguous, to a subset are included in the analysis as fixed “edge” constraints.) For the smallest set, 8.33% of all layouts are better than the actual layout; this performance monotonically improves, up to the full 11component set, for which (as reported in refs. 2 and 23) no layout is better than the actual one. In addition, when optimality (proportion of layouts better than actual) is plotted logarithmically against subset size, the descending curve closely approximates a straight line (r ^{2} > 0.99, P < 0.001), suggesting the growth function is in fact a simple exponential one.
Mammalian cortex optimization is of at least as much interest as worm ganglion optimization. Yet, as explained, connection length data are not in general available, and even in the best cases (macaque and cat), adequate information on connections and adjacencies exists mainly for sensory areas. In addition, there is the doublebind that, according to the size law, component sets that are large enough to be well optimized will tend to be too large for feasible search of all layouts. We first evaluated the size law for 17 contiguous core visual areas of macaque cortex (see Fig. 3), with conformance to the adjacency rule as optimality measure. For the macaque visual cortex areas, we constructed a matrix of ipsilateral intracortical connections and a topological database of adjacencies among the areas (15, 25). Areas outside of the core set, but along the immediate periphery of the group, were treated again as fixed edge components (see Table 1). A nested series of compact subsets was generated, each composed of contiguous elements. Although actual cortical areas form a jigsaw puzzle of widely differing sizes and shapes, they are approximated here as uniformly interchangeable: For example, when V1 and V2 are swapped, V1 adjacencies are assigned to V2, and vice versa, whereas V1 and V2 each retain their original connections. (Thus, as also to a lesser extent for the worm ganglion problem, actual cortical layouts are in fact even being tested against some topologically impossible alternative layouts.)
Fig. 4A shows that the size law seems to apply well to the actual cortex layout and does not hold for a corresponding scrambled calibration set. The logarithmic scale of the y axis should be noted: the size law curve fits a straight line well (r ^{2} > 0.91, P < 0.001), suggesting, as for the much more complete worm ganglia subset series, a simple exponential growth function. It should be emphasized that the “total set” here consists of only 17 components of the entire ≈73 area macaque cortical system and does not include extracortical efferent and afferent connections. The size law provides an account of how such an incomplete system would attain only an optimality ranking in the top 10^{–7} of all possible layouts, even if the complete system were in fact perfectly optimal.
We similarly analyzed placement optimization for all 15 contiguous visual areas of cat cortex (along with a fixed edge zone of immediately surrounding areas) (Fig. 9, which is published as supporting information on the PNAS web site). From published anatomy (ref. 16, Fig. 1 with corrections, and ref. 27), we constructed a matrix of cat ipsilateral intracortical connections and a topological database of adjacencies among the Brodmann areas. (Area SVA is included in 17, ALG in 19; DP in EPp and AI, V in VP and AII, SSF in EPp; some boundary indeterminacies remain unresolved; see Table 3, which is published as supporting information on the PNAS web site.) The results (Figs. 4B and 10) confirm the picture for macaque visual cortex: again, there is a significant size law effect, with smaller subsets of the actual layout ranking only in the midrange among all possible layouts, but larger subsets performing progressively better in their relative ranking for adjacency rule optimality. Optimality improves exponentially with subset size.
Naturally, these two visual cortex series raise the question of how much finer optimality even larger subsets of the actual layout attain, for instance, as observed via simple random samples of the extremely large total sets of all alternative possible layouts (28, 29). For cat sensory cortex (visual, auditory, and somatosensory), anatomical data for 39 contiguous Brodmann areas was adequate for such an analysis. When the subset was extended from the above 15 visual areas to 20 areas, a sample of a billion of all possible 10^{18} layouts showed a rise of actual layout rank from 10^{–5} into the top 10^{–8} of all layouts. (That is, only three layouts of a billion sampled were better than the actual layout.) For a 25area subset, a billionlayout random sample yielded no placements cheaper than the actual one, suggesting the actual layout's ranking may be too high to be detectable at this sample size. Similarly no layouts cheaper than the actual one were found for 30 areas, and also up to 39. Although this is, of course, the most striking finding reported here, it should be interpreted with some care; to begin with, larger sample sizes are warranted. For the 39area cat cortex layout, we performed three separate random samplings, each of 100 billion layouts from the 10^{46} alternative possible layouts: we found no layouts with better adjacencyrule optimization than the actual one. However, with only 39 of the total 57 areas included in this analysis, the size law would suggest the 39 areas need not be perfectly optimally laid out, even if the total 57component system was. (In addition, of course, the neuroanatomical database inevitably still includes errors.) We therefore constructed a simple genetic algorithm, along the lines of one we had developed for the worm ganglion placement problem (22); it quickly finds layouts of the 39 areas cheaper than the actual one.
Metamodule Grouping
Of course, exhaustive search of all 57! alternative layouts of the 57 Brodmann areas of cat cortex (= 4 × 10^{76} layouts) would be cosmically unfeasible (2, 23). Another sampling strategy is instead to unite and conquer: Cluster the Brodmann areas of the actual layout into groups of topologically contiguous components, then search the smaller set of alternative placements of these lockeddown “metamodules” (see Table 4, which is published as supporting information on the PNAS web site). This strategy is based on a metamodule conjecture:
If a set of connected components is optimally placed, then a set of metamodules, each consisting of a subset of those components in the same positions, is also optimally placed.
Figs. 4C and 11 show size law optimization performance of a series of nested layouts of 14 metamodules composed of 40 cat cortical areas. Each metamodule was grouped from adjacent Brodmann areas, all of the same modality (visual, auditory, then somatosensory); metamodules were assembled to have approximately equal numbers of areas, to be of approximately equal area, and to be as compact as possible. The main observation is that the full 14metamodule layout now approaches the top tenmillionth level of optimization, comparable to that found for the worm ganglion system. The size law curve again fits a straight line well (r ^{2} > 0.97, P < 0.001). The consistency of the entire size law trend here constitutes further convergent support for the basic cortical optimality conclusion.
Nonneural Networks
As a further calibration of the methods here, we analyzed connection optimization of two types of nonneural systems: a computer microchip and macroeconomic commodityflow networks. The chip was AMI49, the largest of the set of MCNC microcircuit benchmarks,§ which contains 49 blocks or modules, comparable to the number of functional areas in one cortex hemisphere. We studied three AMI49 layouts of fully automatic design, with costs to be minimized: (i) a function of layout area and maximum path delay (30); (ii) a “blended” function of area and total wire length (31); and (iii) total wire length¶ (see Fig. 5 and Fig. 12, which is published as supporting information on the PNAS web site). In each case, the central 15 blocks of the chip, along with the surrounding edgezone of immediately contiguous blocks, was analyzed (see Table 5, which is published as supporting information on the PNAS web site). Again, placement of the interconnected areas was evaluated for how well total interconnection costs (adjacency rule violations) are minimized, with the actual layout compared with alternative possible layouts. The size law curve for the minimum wire length layout (iii) showed the same pattern as for the cortex networks, although somewhat weaker; the full 15component subset attains an optimality rank of 10^{–3} (see Fig. 6 and Fig. 13, which is published as supporting information on the PNAS web site). Neither of the other AMI49 layouts showed a size law pattern, nor did either attain significant optimality. (In comparisons with the cortex, it should be recalled that, unlike for chips, information on cortex wiring is still not complete.) So, for these calibration networks, adjacency rule conformance seems capable of distinguishing a target of wire length minimization from some other related cost measures. And again, as for the scrambled layouts earlier, adjacency costing does not seem to inflate optimality rankings (see also Figs. 1 and 2).
The macroeconomic system studied was U.S. states (see Fig. 14, which is published as supporting information on the PNAS web site). The “connection” cost to be minimized was combined “export + import” commodity flow (in American dollars) between nonadjacent units. (Because nearly all cells in the matrices have non0 values, economic transactions above a threshold were analyzed, with cutoff set here to yield approximately the same connectivity density as for macaque and cat cortex above; see Table 2.) Optimality measure was conformance of the system to the simple “all or nothing” adjacency rule, with each layout scored in terms of its number of violations of the rule. For U.S. interstate commodity flow, a core of 15 central contiguous states, along with a surrounding edgezone of immediately contiguous states, was analyzed (32) (see Table 6, which is published as supporting information on the PNAS web site). We similarly analyzed as pilot data European international commodity flow among eight countries (33). The total U.S. system attains perfect connectionoptimization. The smaller European nation set shows a similar pattern. (See Fig. 15, which is published as supporting information on the PNAS web site.) As calibration, a scrambled layout of the U.S. system shows no optimization. This powerful performance of the optimization model (rather than a mere satisficing model) may appear to vindicate the wisdom of the hive, the “invisible hand” of laissezfaire economics. Indeed, very fine component placement optimization may thereby seem a rather pervasive phenomenon. However, each macroeconomic series completely departs from the size law pattern; in particular, smaller subsets already attain perfect optimality, with no alternative layouts better than the actual one. So, optimality does not necessarily entail conformance to the size law. This breakdown suggests the macroeconomic networks are optimized only via local processes, unlike the cortex (and some chip) networks. In contrast, conformance of the cortex systems to the size law suggests they are instead “hightradeoff” networks requiring longrange micro/macro exchanges of local optimality for global optimality.
Conclusion
For each cortical network above, the population distribution of costs of alternative possible layouts conforms well to a normal distribution. For each neural system, when connections to/from surrounding edges are excluded from the analysis, optimality of the actual layout decreases. Conversely, when weighting information on connection strength is included in the adjacencyrule costing, actual layout optimality improves over simple allornothing costing. Similarly for r ^{2} fit to the size law. On an assumption that the more realistic the modeling, the more optimal a network should appear, these trends further confirm the optimality assessment.
The convergent set of “best of all possible brains” results reported here (see Table 7, which is published as supporting information on the PNAS web site) raises the issue: are complete mammal cortex layouts in fact optimal, as the total C. elegans ganglion layout appears to be? As for minimumvolume neuron arbors (4), optimal cortex may be just an initial plan that can be modified and elaborated. Natural next questions arise about optimization mechanisms, for instance, direction of causation–from connections to positioning, or vice versa, or both. Although the point should be interpreted with some care, each of the cortex systems analyzed here shows better goodness of fit to an “if connected, then adjacent” hypothesis than to the converse hypothesis. [The test consists of comparing, for each actual layout (see Table 2), its number of counterexamples to “if connected, then adjacent” with the number of counterexamples to the converse hypothesis; the comparison includes a correction for unequal populations of connections and adjacencies. The scrambled calibration layouts show no bias in either direction.] It is also worth noting that, for the C. elegans optimization problem, we have demonstrated simple mechanisms that proceed solely from connections to adjacencies, namely, a genetic algorithm, and also a forcedirected placement algorithm (22). A similar genetic algorithm was described above for cat sensory cortex.
This discussion has focused on neuroanatomy, upon minimization of biological connectionstructures. However, the above macroeconomic analyses really concerned abstract, functional “connections,” i.e., commercial transactions. We thereby proceed from anatomy to physiology broadly conceived. The adjacency rule then generalizes, If components are connected in the wider sense of causal interrelation, then they are topologically adjacent. (No action at a distance.) For instance, the largescale optimization landscapes of cortex and genome may be worth comparing: the structure of the genome would be analyzed similarly as above. Two genes might count as connected if they are coactivated, (approximately) contemporaneously expressed. Contiguity would be interpreted as proximity of position in the 3D genome structure. In fact, a first step toward such an approach may be a recent study of clustering of highly expressed genes in chromosomal domains (34).
Acknowledgments
We thank Richard Kissh for parallel supercomputer software engineering and Eric Celarier, Jarrett Rosenberg, Thomas Schaefer, and Corey Washington for assistance. This work was supported by National Institute of Mental Health Grant MH49867. The National Cancer Institute generously made available supercomputers at its Advanced Biomedical Computing Center.
Footnotes

↵ † To whom correspondence should be addressed. Email: cherniak{at}umd.edu.

Abbreviation: NP, nondeterministic polynomial.

↵ § International Workshop on Layout Synthesis, May, 1992, Research Triangle Park, NC.

↵ ¶ Lin, J.M. & Chang, Y.W., Proceedings of the ACM/IEEE Design Automation Conference, June 18–22, 2001, Las Vegas, NV.
 Copyright © 2004, The National Academy of Sciences
References

↵
Cherniak, C. (1991) University of Maryland Institute for Advanced Computer Studies Technical Report CSTR2711 (Univ. of Maryland, College Park).
 ↵
 ↵
 ↵

↵
Ramon y Cajal, S. (1995) Histology of the Nervous System of Man and Vertebrates, trans. Azoulay, L., Swanson, N. & Swanson, L. (Oxford, New York), Vol. 1, p. 116.

↵
Weibel, E., Taylor, C. & Bolis, L., eds. (1998) Principles of Animal Design (Cambridge, New York).

↵
Cherniak, C. (2000) University of Maryland Institute for Advanced Computer Studies Technical Report CSTR4525 (Univ. of Maryland, College Park).
 ↵

↵
Sherwani, N. (1999) Algorithms for VLSI Physical Design Automation (Kluwer, Boston), 3rd Ed.

↵
Garey, M. & Johnson, D. (1979) Intractability: A Guide to the Theory of NPCompleteness (Freeman, San Francisco).

Lewis, H. & Papadimitriou, C. (1978) Sci. Am. 238 , 96–109.

↵
Stockmeyer, L. & Chandra, A. (1979) Sci. Am. 240 , 140–159.
 ↵

↵
Hwang, F., Richards, D. & Winter, P. (1992) The Steiner Tree Problem (North–Holland, Amsterdam), pp. 37–49.
 ↵
 ↵

↵
Soukup, J. (1981) Proc. IEEE 69 , 1281–1304.
 ↵
 ↵

↵
Cherniak, C. (1996) Trends Neurosci. 19 , 414–415.

↵
Seppanen, J. & Moore, J. (1975) Int. J. Production Res. 13 , 239–254.

↵
Cherniak, C., Mokhtarzada, Z. & Nodelman, U. (2002) in Computational Neuroanatomy: Principles and Methods, ed. Ascoli, G. (Humana, Totowa, NJ), pp. 71–82.

↵
Cherniak, C. (1994) Philos. Studies 73 , 89–107.

↵
Van Essen, D., Felleman, D., DeYoe, E., Olavarria, J. & Knierim, J. (1990) Cold Spring Harbor Symp. Quant. Biol. LV , 679–696.
 ↵
 ↵
 ↵

↵
Golden, B. & Stewart, W. (1985) in The Traveling Salesman Problem, eds. Lawler, E., Lenstra, J., Rinnoy Kan, A. & Shmoys, D. (Wiley, New York), pp. 207–249.

↵
Bentley, J. (1990) in Proceedings of the ACMSIAM Symposium on Discrete Algorithms, ed. Johnson, D. (Society for Industrial and Applied Mathematics, San Francisco), pp. 91–99.

↵
Esbensen, H. & Kuh, E. (1997) ACM Trans. Design Automat. Electron. Systems 2 , 62–80.

↵
Hong, X., Huang, G., Cai, Y., Dong, S., Cheng, C. & Gu, J. (2000) in International Conference on ComputerAided Design, (IEEE, San Jose, CA), pp. 8–12.

↵
Bureau of Transportation Statistics (1997) StatetoState Commodity Flows: Commodity Flow Survey (U.S. Department of Transportation, Washington, DC).

↵
Organization for Economic Cooperation and Development (1999) International Trade by Commodity Statistics (Organization for Economic Cooperation and Development, Boulogne, France).

↵
Caron, H., van Schaik, B., van der Mee, M., Baas, F., Riggins, G., van Sluis, P., Hermus, M., van Asperen, R., Boon, K., Voute, P., et al. (2001) Science 291 , 1289–1292. pmid:11181992