Heads (rolling?) on Mars....

This is being re-posted from my microblog Tumbld Thoughts.

I think I know the location of Phillip K. Dick's (PKD) head. HINT: you must get your ass there ASAP. My awareness of the lost cybernetic PKD head courtesy of the book "How to Build an Android". Quote courtesy of Hauser from "Total Recall: 1990". Telling Quaid (alter ego) to go to Mars.

As for the recent movie (Total Recall: 2012), see my critique ("For whom would you rather buy a new memory?", originally posted at Tumbld Thoughts on August 3) below:

Aha! I just knew the remake of "Total Recall" [2] was going to be a shitty fraud! My main problem going in was that the new movie, unlike the original movie and short story, does not take place on Mars. Instead, it takes place on earth in a dystopian future. No Mars, no sale. Colin Farrell in the role of Quaid [3] also does not help. 

As a matter of principle, I like the premise. The mix of cognitive engineering and "out there" sci-fi sensibility is something I can get on board with. But the new movie offers little inspiration from either [4]. In short, it's not getting my ass to Mars.....oh wait, it can't!

NOTES:

[1] for more information, please also see this article from BoingBoing.


[2] so far so bad, according to Wired.

[3] I have no doubt he would be able to say "get your ass to Mars". The problem is that he doesn't have the opportunity to.

[4] although I understand that people travel seamlessly through the earth's core in a post-apocalyptic future. That alone ruins it for me. Good night.

Cascades in Common: biological network function in evolution

What is a network cascade? And what is their relevance to biological evolution? The answer, while not definitive in this post, is that they contribute to both adaptive variation and variation between species. Cascades have been defined in a range of complex networks, from economic systems and social hierarchies to cellular processes and the internet. In [1], cascades are defined as the downstream effects of some disruption or change in the network (termed higher-order interrelationships). Of particular interest are small, localized disruptions that result in widespread state changes (such as innovations, death, and revolutions) [2]. While these type of responses are not typical network behavior (as we will see), cascade dynamics can be altered by changing the connectivity of a network [3]. In [4], nodes and edges were added to maximize the spread of cascade activity in a set of network topologies. Thus, cascades can also result from the "bursty" nature of information and activity flows in a network, as the activity of network components is often stochastic and rarely coordinated.

Figure 1. A: Example of a link (edge) in a genetic regulatory network (arrow c is linked to gene g via activation of binding site n). B: a kinetic model that describes the relationship between the occupancy of n and the input c given four possible outcomes. C: effect of gene network on a phenotype (A-P axis of Drosophila during development). COURTESY: Figures 1, 2, and 10 in [5].

The complex and subtle effects and dynamics of cascades cannot be understood outside the context of biological networks. In this case, we will focus on networks representing gene regulation and more general physiological mechanisms. To better understand the outcomes of gene expression in organisms, researchers have used an approach called genetic regulatory networks (GRNs). GRNs are hierarchical, directed networks that are modular [6], exhibit differential effects [6], and feature a number of important topological motifs [7]. Hierarchical gene regulatory networks are rooted (top level) by master regulatory genes, which code for transcription factors [8] that regulate many downstream targets. The effects of connectivity can range from immediate (first-order) connections to more diffuse (second- and third-order) connections [9]. An example focusing on second-order connectivity can be seen in Figure 2. While the connectivity between nodes is an important determiner of function, the flows between nodes (or edges) are also an important feature of gene regulatory networks. Flows (or slow cascades) are perhaps a better indicator of functional potential, as different parts of the network can be activated or inactivated in different contexts. These flows contribute to activation of the network from top to bottom, which can be characterized as a cascade [9]. 

Figure 2. Two examples of second-order interconnectivity in a hierarchical, directed graph. COURTESY: Figure 3 in [1].

How can we understand the role of cascades in evolution, and how are they affected by evolution? In Erwin and Davidson [6], the effects of changes in a given GRN architecture depend on where in the network these changes occur. In a recent review by Cohen et.al [10], the concept of physiological regulatory networks (PRNs) is introduced. In PRNs (see Figure 3), nodes can represent a wide range of physiological phenomena (e.g. immune molecules, metabolites), each class of which constitutes a subnetwork. Notably, homeostasis [11] governs the state of edges between these nodes in a way that regulates the global network state. There is an interesting interaction between homeostasis and the propagation of cascades, especially as it relates to contributions of heterogeneous subnetworks towards the global physiological state. Using this formulation of a network, alternative physiological structures may form, which are different network topologies that have equivocal functional outcomes and the same overall fitness [10]. This provides a degree of robustness that protects the organisms from potentially disastrous changes to the network structure. This is also true for many developmental processes, as networks are conserved across phylogeny [8]. However, changes to developmental networks may also enable evolutionary changes. In the case of one such process (the oocyte-to-embryo transition), certain genes can lose or gain function which can in turn enable reproductive isolation [11]. Thus, the network properties that enable cascades to occur could also enable evolutionary change.

Figure 3. An example of a PRN topology and its outputs. COURTESY: Figure 1 in [10].

Using a strictly hierarchical gene regulatory network, I would like to conduct a thought experiment to illustrate the changes required and observed across phylogeny, where we begin with a densely connected graph and then delete connections one by one in the fashion of a sensitivity analysis. The deletions could represent mutational perturbations or some other unspecified disruption. In this example, suppose that we have a fully-connected random topology with activation spreading from the top nodes to the bottom (see Figure 4, right). Because it is fully connected, this topology exhibits maximal robustness, and as such cannot be highly disrupted unless many edges are removed. Now let us consider a network topology that is sparsely connected at the top with activation spreading in the same manner as before (Figure 4, left). In this case, large parts of the network can be inactivated with the removal of many fewer connections. Because it has fewer redundant connections, there are fewer opportunities to re-route the influence from higher levels.

Figure 4. Three-level strictly hierarchical gene regulatory network from thought experiment.

It is of note that in both cases, nodes are treated as static entities. Interestingly, a study by LeClerc [13] suggests that in evolutionary simulations, sparser network topologies tend to evolve from an initial condition of dense connectivity. This is because the resulting sparse topologies retain the dynamic robustness of the original topology, a result also observed in a wide range of species (e.g. yeast, Arabidopsis, and Drosophila among others). In terms of cascades, Duncan Watts suggests that in general, the propensity for large-scale cascades to be triggered by perturbations of varying magnitude is a nonlinear response [14]. Large-scale cascades, or avalanche-like displacements, occur rather infrequently and define major functional events or changes in the biological system [15]. Furthermore, cascades can either be progressive (propagate at a regular rate) or non-progressive (propagate irregularly by chance) [3], which can either provide opportunities for an adaptive response, or act as a set of constraints on network topology evolution. As in the case of LeClerc's evolutionary simulations, the propensity of cascades in a network also occurs with regard to connectivity. In sparsely connected networks, the perturbation of highly-connected nodes is most likely to trigger cascades. In densely- connected and heterogeneous networks, the propagation of cascades are limited to the local stability of nodes. Cascades triggered in this manner are very unstable and harder to predict, and point to potential roles for transcriptional stability and noise in cascade dynamics.

What does this tell us about evolutionary systems? Is this a secondary reason why developmental networks tend to be conserved (the first being to "lock-in" essential function)? And what happens when a large-scale cascade occurs in a gene regulatory or physiological network? To get at these questions, we must understand what kinds of changes are enabled when key features of a network are changed. In Bhardwaj, Yan, and Gerstein [16], the hierarchical layout of a GRN is compared to social hierarchies. In particular, GRNs can be either autocratic (generally sparsely connected from top to bottom) or democratic (more densely connected and less dependent on higher levels). Examples of this range from the expansion of existing hierarchical layers of regulation in E.coli genomes (e.g. democratic) to differences between top-level and mid-level transcription factors in yeast genomes (e.g. more autocratic) [17]. The hubs and other structural features of regulatory hierarchies also provide an opportunity for coordinating global changes in gene expression based on relatively few mutational changes and enhancing the effects of beneficial mutations [17]. 

Using models of this type, the potential for cascades (as opposed to normal GRN function) can be modeled using computational simulations of sea urchin embryonic development [18]. This exercise demonstrates that transitions between regulatory "states" can occur sharply, which is contingent upon connectivity (e.g. more likely in autocratic networks). Secondly, the model of Boulouri and Davidson [18] shows that each hierarchical level is activated in succession, with a lag of a few hours for each level activated. Perturbations of and significant delays in this lag time (through a variety of mechanisms) could lead to large-scale evolutionary changes via developmental timing and coherence.

Perhaps cascades and changes in network connectivity due to perturbation (environmental or mutational) indeed play a role in setting up evolutionary changes. At the very least, the interaction between standing variation, adaptive changes, and genetic/physiological regulation can be better understood by considering the role of cascade dynamics. This is a largely unexplored area, but future work in the areas of dynamical evolutionary simulations, network representations, and multilevel/multiscalar models may provide us with some useful advances.

REFERENCES:

[1] Acemoglu, D., Asuman Ozdaglar, A., and Tahbaz–Salehi, A.   Cascades in Networks and Aggregate Volatility. NBER Working Paper 16516 (2010).

[2] Culotta, A.   Maximizing Cascades in Social Networks: an overview. Technical Report, Computer Science Department, University of Massachusetts, Amherst (2003).

[3] Sheldon, D., Dilkina, B., Elmachtoub, A., Finseth, R., Sabharwal, A., Conrad, J., Gomes, C., Shmoys, D., Allen, W., Amundsen, O., and Vaughan, B.   Maximizing the Spread of Cascades Using Network Design. arXiv, 1203.3514 (2012).

[4] Feldmann,  A., Gilbert, A.C. and  Willingert, W.   Data networks as cascades: investigating the multifractal nature of Internet WAN traffic. Proceedings of SIGCOMM (1998).

For information on potential natural defense mechanisms against large-scale cascades that can severely disrupt a network's function, please see: Motter, A.E.   Cascade control and defense in complex networks. Physical Review Letters, 93, 098701 (2004).

[5] Tkacik, G. and Walczak, A.M.   Information transmission in genetic regulatory networks: a review. Journal of Physics: Condensed Matter, 23, 153102 (2011).

[6]  Erwin, D.H. and Davidson, E.H.   The evolution of hierarchical gene regulatory networks. Nature Reviews Genetics, 10, 141-148 (2009).

[7] Ingram, P.J., Stumpf, M.P.H., and Stark, J.   Network motifs: structure does not determine function. BMC Genomics, 7, 108 (2006). 

This paper demonstrates that the bi-fan motif (a type of one-to-many hierarchical relationship) has a broad range of potential functional responses.

[8] Gehring, W.J.   Master Control Genes in Development and Evolution: the Homeobox story. Yale University Press, New Haven (1998). 

For a basic definition, please see: Myers, P.Z.   Master Control Genes and Pax-6. Pharyngula, http://scienceblogs.com/pharyngula/2007/09/23/basics-master-control-genes-an/ (2007)

Examples of master regulatory genes include Oct4 (pluripotency), Pax6 (eye development), and p53 (cancer).

[9] Watts, D.J.   A simple model of global cascades on random networks. PNAS, 99(9), 5766 –5771 (2002).

[10] Cohen, A.A., Martin, L.B., Wingfield, J.C., McWilliams, S.R., and Dunne, J.A.   Physiological regulatory networks: ecological roles and evolutionary constraints. Trends in Ecology and Evolution, 27(8), 428-435 (2012).

[11] Cannon, W.   Wisdom of the Body. W.W. Norton, New York (1930). 

For a basic definition, please see this Scientific American article (http://www.scientificamerican.com/article.cfm?id=what-is-homeostasis).

[12] Evsikov, A.V., Graber, J.H., Brockman, J.M., Hampl, A., Holbrook, A.E., Singh, P., Eppig, J.J., Solter, D., and Knowles, B.B.   Cracking the egg: molecular dynamics and evolutionary aspects of the transition from the fully grown oocyte to embryo. Genes and Development, 20, 2713–2727 (2006).

[13] LeClerc, R.D.   Survival of the sparsest: robust gene networks are parsimonious. Molecular Systems Biology, 4, 213 (2008).

[14] Watts, D.J.   A simple model of global cascades on random networks. PNAS, 99(9), 5766 –5771 (2002).

Large-scale cascades (e.g. avalanches) can be caused by relatively small perturbations. In technical terms, the size distribution of cascades relative to the degree of perturbation is variable according to a power law. Also see related concept of scale-free networks.

[15] Pajevic, S. and Plenz, D.   Efficient Network Reconstruction from Dynamical Cascades Identifies Small-World Topology of Neuronal Avalanches. PLoS Computational Biology, 5(1), e1000271 (2009).

[16] Bhardwaj, N., Yan, K-K., and Gerstein, M.B.   Analysis of diverse regulatory networks in a hierarchical  context shows consistent tendencies for collaboration in the middle levels. PNAS, 107(15), 6841–6846 (2010).

[17] Crombach, A. and Hogeweg, P.   Evolution of Evolvability in Gene Regulatory Networks. PLoS Computational Biology, 4(7), e1000112 (2008).

[18] Bolouri, H. and Davidson, E.H.   Transcriptional regulatory cascades in development: initial rates, not steady state, determine network kinetics. PNAS, 100(16), 9371–9376 (2003).

Claude Shannon's Mechanical Zoo

Portrait of Claude Elwood Shannon, courtesy of Fan Chung Graham.

It's time for some fun courtesy of Claude Shannon, the legend of Bell Labs. The father of information theory was also an inventor of great renown. These inventions did not lead to useful, everyday products, but did involve some incredible engineering. I ran across some classic footage on YouTube for two of these which is always fun to watch.

Above is a picture of his Juggling Diorama, a mechanical automaton built for the simulation of juggling [1]. It is a classic simulation in the sense that a reduced physical model of the process can help clarify the algorithmic and mathematical structure of juggling as a mental and physical process. To this end, Shannon also worked out a Juggling Theorem (an application of combinatorics), which is apparently reducible to a T-shirt slogan.

Shannon also designed small autonomous mechatronic rodents, pioneering the design of such devices years before similar research- and consumer-oriented application came to fruition. It is also a very early attempt at machine learning, based on cybernetic principles in fashion at the time.

The picture above is an example of a mechanical rodent he designed being put into a maze (a contraption called "Thesus"), some 40 years before the Khepera robot came on the scene [2]. For a comprehensive tour of past and present robots, mechatronic devices, and mechanical automata, visit cyberneticzoo.com [3].

NOTES:
[1] more on the science of juggling can be found here and here. And an overview on a German museum exhibit a few years back called Codes and Clowns.

[2] there are more stories about Shannon's mechanical rats roaming the halls of Bell Labs in the recently published book "The Idea Factory".

[3] quite an impressive overview of some really obscure technology. My favorite is the mechanical animal compendium.

"Space" as a BIG mental space

This is for everyone who looked at all of the media hype surrounding SpaceX's launch of their Falcon series rocket [1] and thought "This is it"? I mean, it's nice that we are moving towards more accessible space travel. And there is a lot of room for practical innovation in terms of space travel. However, I felt like we are revisiting what was done in the 1950s and 1960s -- only with private initiative. Without much critical assessment to be found, the SpaceX media hype definately has the feel of neo-conservative propaganda [2]. As it stands, large parts of the Space Coast now resemble a ghost town, and the US still does not have a reliable way to get into space.

This is why it is refreshing to see a concerted effort to think BIG (sans media largesse). I remember reading the visionary science magazine OMNI in the early 1990s, and was fascinated by their obsession with the terraforming of Mars. Although it was a totally obscure and mostly implausible idea, that didn't stop them from occupying that mental space. We need the same kind of visionary audacity to achieve the next step in spaceflight. The 100 Year StarShip (100yss) initiative is an effort to focus the mind on building a ship that would take a crew to another solar system in 100 years. Certainly sounds BIG enough. They just has a symposium in Houston which featured speakers from the Star Trek franchise plus various academics, technologists, and entrepreneurs. We'll see what emerges. A similar initiative called "Build the Enterprise" is a call to arms for thinking BIG when it comes to space travel and exploration.

Does this sound absurd? An initiative to send a Captain Picard action figure to space (via high-altitude balloon) is already fully funded [3].....

In 1994, a paper was published by Miguel Alcubierre [4] on the feasibility of a warp drive similar to the one used in Star Trek [5]. This spawned a cottage industry of people investigating this particular mechanism for interstellar travel (all operating from a BIG premise). The basic idea is to exploit general relativity (e.g. the structure of spacetime) by traveling within a bubble embedded on the surface of spacetime. Theoretically, this would serve as a workaround to the universal speed limit (e.g. light). Practically speaking, a team of scientists estimated that it would take nearly all of the energy in the known universe (now that's big) to create and keep the bubble stable for an extended period of time [6]. Nevertheless, I think ideas like this will lead us to some major, fundamental discoveries regarding interstellar travel, even if Alcubierre's warp drive design is implausible.

A spacetime "bubble": is this the key to warp drive? COURTESY: Wolfram Mathematica simulation.

So what is my solution? And why do I keep writing "big" as BIG? Answer: think BIG (brash, ingenious, and grand) and you shall be rewarded. Occupy the "out there" ideas, instead of always taking incremental steps or becoming bogged down in the culture wars. Own these audacious ideas, and even though the larger goal (terraforming Mars, traveling to another galaxy) might not come to fruition, many other, more incremental things will result. This is what originally happened with the space program. Even if we hadn't succeeded at the Moonshot (which we did anyways), we still were able to obtain many derivative products from this endeavor [7]. 

NOTES:
[1] the SpaceX craft (left) reminds me of the Phoenix (Zephram Cochrane's ship - right) featured in Star Trek: First Contact. Not sure if that's a backhanded compliment or not. Or if the SpaceX design was intentional.

[2] meaning something like: "look what we can do without the government largess of NASA!" Which is totally false by the way. Also, why are all of our prevailing ideologies "neo" this or that? Is it the "old wine in new bottles" problem, or is it like "post"-modernism?

[3] Once again, thank you, Kickstarter. Your featured projects are not entirely frivolous.

[4] Alcubierre, M.   The warp drive: hyper-fast travel within general relativity. Classical and Quantum Gravity, 11(5), L73–L77 (1994). Here is a nice blog post on "time control technologies", of which the Alcubierre drive is an instance.

For more visionary examples, please see: Wagner, R. and Cook, H.   Designs on Space: blueprints for 21rst space exploration. Simon and Schuster, New York (2001).

[5] I have found that "Star Wars" provides far less inspiration for technological innovation.

[6] Pfenning, M.J. and Ford, L. H.   The unphysical nature of 'Warp Drive'". Classical and Quantum Gravity, 14(7), 1743–1751 (1997).

[7] in an attempt to be concrete about this claim, here is a list of 27 products that have resulted from NASA's endeavors. Just a first-pass approximation, by the way.

A brief mention of "wicked" problems....

What is the computational structure of social change? Or social persistence, for that matter? These might seem like strange questions, mainly because they are not asked too often. True, people have tried to understand the phenomenon of social dynamics using a variety of techniques spanning from agent-based models to economic models and even discourse analysis. However, these approaches have not provided a predictive framework suitable for the onset and management of large-scale events that define social changes. These include disruptions and upheavels such as stock market crashes, ethnic conflicts, and disease outbreaks. Because their computational representations feature complexity beyond NP (non-polynomial) [1], they are called "wicked" problems [2].

Figure 1. Nested set of solution spaces for different degrees of problem hardness.

As a formal concept, wicked problems were first identified in late 1960s and early 1970s [3]. Wicked problems are highly complex and nonlinear, with dynamic, spatial, and parallel process components. Some components of these problems many not be predictable [4]. In fact, this may not be true of any single component. In the literature [5], there are four features that distinguish "wicked problems" from relatively easier ones (such as chess, network reconstruction, or pattern recognition):

Figure 2. Is this a wicked problem? Is this how it should be set up?

1) ill-defined problem space: In a recent workshop (HTDE 2012), I discussed the attributes of "hard-to-define" problems. While not all hard-to-define problems are wicked, wicked problems do not feature a closed or even finite set of possible solutions. Whether they can truly be treated using an algorithmic framework is not clear.

2) all solutions are heuristic: due to the limitations of the first feature, any given wicked problem has no exact solution. The problem space will be characterized by many different solutions, likely context-dependent (the word "contingent" [6] can also be used).

3) there is no "stopping rule" for wicked problems. In conventional computing, the is an end point to a simulation of program that can be defined either deterministically (program-dependent) or stochastically (a Turing machine). With wicked problems, there is no natural stopping point, as the problem has no natural end-point [7].

4) so-called "messes" [8] define interactions between subdomains of the problem. In this case, a problem's subdomains form a dense, fully-connected network which cannot be decomposed to reveal clear causal or associative relationships. Instead of being merely massively parallel, such problems are at least massively interactive and are often exhibit parallelism as well. Furthermore, such messes often transcend formal system-level boundaries, and from a phenomenological standpoint implicate several loosely-related systems.

Figure 3. Two first-pass approximations at wicked problems? LEFT: M.C. Escher's Mobius Strip, RIGHT: SimCity.

How is this perspective useful for computing and solving complex scientific problems? Well, it is not so much useful as it is a challenge. There is much work to be done here. So what a challenge it is [9]!

NOTES:
[1] Papadimitriou, G.H.   Computational Complexity. Addison-Wesley, Boston (1994).

[2] Brown, V.A., Harris, J.A., and Russell, J.Y.   Tackling Wicked Problems: Through the Transdisciplinary Imagination. Earthscan, London (2010).

[3] According to Wikipedia, C. West Churchman introduced the term in 1967, which was expanded upon in the following paper:

Rittel, H.W.J. and Webber, M.M.   Dilemmas in a General Theory of Planning. Policy Sciences, 4, 155-169 (1973).

[4] Mandelbrot, B. and Hudson, R.L.   The (mis)Behavior of Markets: a fractal view of risk, ruin, and reward. Basic Books, New York (2004).

[5] Wicked problems have been discussed extensively in the business and operations research literature as a mans to solve social policy problems. Please see the following example:

Lazarus, R.J.   Super Wicked Problems and Climate Change: Restraining the Present to Liberate the Future. Cornell Law Review, 94(5), Georgetown Public Law Research No. 1302623 (2009).

However, the things that define a wicked problem apply to a much larger class of problems. Formal methods are needed.

[6] Levin, K., Cashore, B., Bernstein, S., and Auld, G.   Playing it forward: Path dependency, progressive incrementalism, and the "Super Wicked" problem of global climate change. IOP Conference Series: Earth and Environmental Science, 50(6) (2009).

[7] an example might be cultural or biological evolution, which do not "end" until some major catastrophe wipes out the entire system. In these examples, it is interesting to note that you can observe an artificially-determined endpoint, but it does not always reveal a definitive solution (e.g. natural selection and the evolution of "maximally adaptive" traits).

[8] According to Wikipedia, this term was originally coined by Russell Ackoff. Please see the following reference:

Ackoff, R.   Systems, Messes, and Interactive Planning. In "Redesigning the Future". Wiley, New York (1974).

[9] I have no prize to offer for anyone who proposes reasonable-sounding solutions or formal methods. It's just a call-to-arms.

A new academic term meets liquid nitrogen....

Ah, Fall term is upon us. A tip for all the students out there: don't use your laptops excessively when class is in session...

Brought to you by Kieran Mullen, University of Oklahoma physics professor. Actually, this video was only a gratuitous demo (but an effective one at that) [1]. While we're on the subject, there are many things that can be destroyed after a bath in liquid nitrogen and an encounter with the floor: pumpkins, locks, and of course, giant koosh balls [2].

[1] the same principle goes for cell phones and full-course meals. You know who you are.

[2] COURTESY: Jefferson Lab, US Department of Energy.