February 25, 2013

Innovation-palooza for February

Here are a couple more cross-posts (on Hard-to Define Events and Scientific Innovation, respectively) from my micro-blog, Tumbld Thoughts.






A. Take a look at the link [1] to a slideshow I am presenting in the near future as a follow-up to the Hard-to-define Events workshop I organized last summer. It is called "If your results are unpredictable, does it make them any less true?", and focuses on applying the hard-to-define events paradigm to biology and the development of scientific theory.


B. And here is an article from Joe Nocera of the NYT called "Innovation Nation at War" [2]. It is a critical assessment of the current patent system and how it is hurting the innovation economy. Specifically, he discusses patents in terms of their economic utility, and how companies buy patent portfolios and file patent lawsuits [3] in a manner that severely violates this principle. Perhaps a better solution would be a bond system ties to ideas futures, which would provide a more immediate payoff with less legal jujitsu [4].





C. As an added bonus, here is a podcast (courtesy of the NanoNerds YouTube channel) with Brian Bergstein from MIT Technology Review on the top ten emerging technologies of 2012. The continued development of cheap nanopore DNA sequencing technology is my favorite.

NOTES:


[2] here is a real-time update of the "Tweetscape" for this article. Interesting comments.

[3] A conflict termed the "patent wars". Interesting infographic here.

[4] The martial arts is figurative, but the legal maneuvering is quite real (see here for an example on the anti-commons). See diagrams above for more information. These are some ideas I have been developing, and stand in comparison to intellectual property-oriented patents.



February 19, 2013

Ratchets in Nature: a short review

A natural ratchet (similar to a simple machine-style ratchet, see Figure 1) can be defined as a mechanism that operates with one degree of freedom (forward and backward along an axis), but is constrained to exploit movement in only one direction (forward movement). This allows for nominally random processes to become directed without an external guide.

Ratchet mechanisms have been proposed for development, complexity, evolution, biophysics, and cognitive performance. Table 1 profiles nine different types of ratchet found in nature. There are likely many more natural processes with similar behavior which are not included here.

Figure 1. An animation of a ratchet mechanism. COURTESY: Wikipedia.

To illustrate how the ratchet metaphor has been applied in science, and to show the parallels between the various conceptual models, we will start with evolutionary ratchets (related to genetic background) and then move on to other types of natural ratchet (which are more directly related to energetics and movement).

Table 1. Different types of ratchet in nature (click to enlarge).
1 instance of a Brownian ratchet (example from actin dynamics, see [1]).

Evolutionary ratchets map the degree of movement freedom in a mechanical ratchet to increases and decreases in mutability and/or fitness (e.g. axes of variation). These fluctuations are then constrained to net increases in these variables.

To explain apparent directionality in evolution, three ratchet-like mechanisms (type I) have been explained: the epistatic, Muller’s, and cognitive ratchets. The epistatic ratchet is driven by epistatic interactions, so that mutations key to defining functional changes depend on corresponding mutations in genes of smaller effect [2]. For Muller’s ratchet, high mutation rates and neutral processes work together to produce a bias towards genotypes with a greater number of mutations [3].

In the case of both epistatic and Muller’s ratchets, mutational change becomes directional [4] rather than a random walk [4.1]. While this type of mutational change appears at first glance to be directed in some top-down manner, Maynard-Smith and Szathmary [4.2] show that it can be spontaneous by proposing a ratchet-like process called contingent irreversibility. In a similar but goal-directed manner, the cognitive ratchet works at the scale of behavior, and relies on anticipatory (behavioral) abilities for certain behaviors to drive further evolution of these abilities over longer time-scales [5].

Thermal ratchets (type II) are an instance of a Brownian ratchet, which are driven by Brownian (or quasi-random) noise [6]. In Huxley and Simmons [7] describe how thermal fluctuations allow for myosin heads to bind actin filaments under strain. This configuration generates tension and ultimately movement (e.g. kinesis). These observations were incorporated into the dominant theory of how muscle fibers contract (e.g. sliding filament theory – see Figure 2). While other types of natural ratchet are largely metaphorical, the physics of type II natural ratchets are the most similar to the physics of a simple machine-style ratchet.

Figure 2. A visual description of sliding filament theory (e.g. a thermal ratchet that drives contraction). COURTESY: Engrade.

The next two types of ratchet (type III) involve the transmission and expression of genetic material, respectively. In the case of a gene transfer ratchet, the ratchet mechanism is used to explain the acquisition of bacterial genes by Eukaryotes [8]. Theoretically, it is suggested that early Eukaryotes acquired bacterial genomes from the bacteria consumed as food. Enhancer action ratchets push a genome's regulatory machinery towards bistability for chromatin markers of specific regulatory regions, which further enable changes in gene expression during a biological process [9].

The last three types of ratchet (type IV) have relevance to cellular and organismal movement. The directed tissue movement ratchet is driven by selectively-times pulsed forces that occur during tissue differentiation and organization in development [10]. The filament-pulling (diffusive) ratchet relies on a protein’s interactions with the geometry of cell bodies to enable functions such as DNA segregation during mitosis [11]. Figure 3 demonstrates this in an ex vivo setting. Finally, bacterial motors are ratchet-like mechanisms used to enable bacterial motility, usually through a flagellar structure [12].

But what enables directional behavior what are essentially undirected processes? In some cases (such as epistatic effects or Brownian ratcheting), a mechanism called stochastic resonance might be responsible [13]. Stochastic resonance (see Figure 4) involves the emergence of order by adding a noisy signal to a process which is already embedded in noise. This provides a route to order from chaos without any sort of intelligence.

And while there are no hard and fast rules to being noisy, the basic idea is that randomness can help define (or at least constrain) the system of interest [14]. A second possible mechanism involves a source of information acting as driver of the ratcheting mechanism. This is, in principle at least, similar to the Szilard engine that is supposed to provide directionality to entropic processes [15].

Figure 3. Instances of geometry sensing and the filament-pulling (diffusive) ratchet. TOP: diffusive coupling at different constants (from Supplementary Movie 8 in [11]). BOTTOM: Min protein on various membrane geometries (from Supplementary Movie 6 in [11]).

Figure 4. An example of stochastic noise (and resonance) in visual stimuli. Add white noise to the image, and it contributes to resolution of the underlying pattern. COURTESY: Wikipedia.

Full Citations and Notes:

[1] Carlsson, A.E.  Actin dynamics: from nanoscale to microscale. Annual Reviews in Biophysics, 39, 91-110 (2010).

For a more general review, please see this paper: Reimann, P. and Hanggi, P.   Introduction to the physics of Brownian motors. Applied Physics A, 75, 169-178 (2002).

[2] Bridgham, J.T., Ortlund, E.A., and Thornton, J.W.  An epistatic ratchet constrains the direction of glucocorticoid receptor evolution. Nature, 461, 515-519 (2009). See also the related concept of constructive neutral evolution (CNE):

[2.1] Lukes, J., Archibald, J.M.,  Keeling, P.J., Doolittle, W.F., and Gray, M.W.   How a neutral evolutionary ratchet can build cellular complexity. IUBMB Life, 63(7), 528-537 (2011).

[2.2] Atkins, A.R. and Lambowitz, A.M.   A protein required for splicing group I introns in Neurospora mitochondria is mitochondrial tyrosyl-tRNA synthetase or a derivative thereof. Cell, 50, 331–345 (1987).

[2.3] Stoltzfus, A  On the possibility of constructive neutral evolution. Journal of Molecular Evolution, 49(2), 169-181 (1999).

[3] Muller, H.J.  The relation of recombination to mutational advance. Mutation Research, 1(1), 2–9 (1964).

[4] Evolutinary ratchet mechanisms are closely tied to random and/or neutral processes, as demonstrated in these two references:

[4.1] Codling, E.A., Plank, M.J., and Benhamou, S.  Random walk models in biology. Journal of the Royal Society Interface, 5(25), 813-834 (2008).

[4.2] Maynard Smith, J. and Szathmary, E.   The Major Transitions in Evolution. Oxford University Press, Oxford UK (1995).

[5] Riegler, A.  The Cognitive Ratchet: the ratchet effect as a fundamental principle in evolution and cognition. Cybernetics and Systems, 32, 411–427 (2001).

[6] Longtin, A.  Stochastic dynamical systems. Scholarpedia, 5(4), 1619 (2010).

[7] Huxley, A.F. and Simmons, R.M.  Proposed Mechanism of Force Generation in Striated Muscle. Nature, 233, 533-538 (1971).

[8] Doolittle, W.F.  You are what you eat: a gene transfer ratchet could account for bacterial genes in eukaryotic nuclear genomes. Trends in Genetics, 14, 307-311 (1998).

[9] Narula, J., Smith, A.M., Gottgens, B., and Igoshin, O.A.  Modeling Reveals Bistability and Low-Pass Filtering in the Network Module Determining Blood Stem Cell Fate. PLoS Computational Biology, 6(5), e1000771 (2010).

[10] Solon, J., Kaya-Copur, A., Colombelli, J., and Brunner, D.  Pulsed Forces Timed by a Ratchet-like Mechanism Drive Directed Tissue Movement during Dorsal Closure. Cell, 137, 1331-1342 (2009).

[11] Schweizer, J., Loose, M., Bonny, M., Kruse, K., Monch, I., and Schwille, P.  Geometry sensing by self-organized protein patterns. PNAS, 109(38), 15283-15288 (2012).

[12] Di Leonardo, R., Angelani, L., Dell’Arciprete, D., Ruocco, G., Iebba, V. Schippa, S., Conte, M.P., 
Mecarini, F., De Angelis, F., and Di Fabrizio, E.  Bacterial ratchet motors.PNAS, 107, 9541-9545 (2010).

[13] Rouvas-Nicolis, C. and Nicolis, G.  Stochastic resonance. Scholarpedia, 2(11), 474 (2007).

[14] Wimsatt, W.  Randomness and perceived randomness in biological systems. Synthese, 43, 287-329 (1980). 

Interesting linkages between randomness (in the algorithmic sense) and evolutionary biology from a biologist's point of view.

[15] Parrondo, J.M.R.  The Szilard engine revisited: entropy, macroscopic randomness, and symmetry breaking phase transitions. Chaos, 11(3), 725-733 (2001).

Also see this Cosmic Variance blog post on the connection between information and thermodynamic entropy: Carroll, S.  Using Information to Extract Energy. Cosmic Variance blog. November 22 (2010).

February 11, 2013

A sparse, anti-fragile universe.....

This article is being cross-posted [1] from my micro-blog, Tumbld Thoughts.

Not a particularly sparse universe, by the way. But a home of sparse variables? Perhaps.

And now, dispatches from an antifragile universe [2]. Nassim Nicholas Taleb has a guest article in Wired (entitled "Beware the Big Errors of Big Data") in which he warns against the use of sparse variables [3] in so-called high-throughput datasets.



NOTES:
[1] also re-posted to the Mathematica group on Tumblr.

[2] N.N. Taleb  "Antifragile: things that gain from disorder". RSA lecture here. I've yet to decide whether Taleb is the Rasputin or the Tesla of analytics. Regardless, here is a video from the New York Public Library speaker series featuring Taleb discussing the concept of anti-fragility with cognitive psychologist Daniel Kahneman.


[3] variables that have a high signal-to-noise ratio. Or, why sometimes Watson gives ridiculous answers. Generally speaking, the more variables you have in an analysis, the greater the number of spurious correlations you must contend with. This is quite similar to Bellman's "curse of dimensionality".

February 9, 2013

Notes From the TSP Revolution

This is being cross-posted from my micro-blog, Tumbld Thoughts.


Here is a link [1] to the latest research on the traveling salesman problem (TSP). The TSP [2] involves visiting a set of cities using the shortest path possible while visiting each city only once (e.g. finding the shortest route). Recent research has demonstrated that by using the Christofides' algorithm, good approximations to an solution (at most 50% of the true shortest route) are possible [3]. Solutions to the TSP can be applied to a wide range of problems, including logistics, phylogenetic analysis, and power grid optimization.



NOTES:
[1] New directions in TSP research (website hosted by Georgia Tech). The first picture shows a TSP tour on a set of points resembling "Mona Lisa". The second picture (map of the United States) is representative of a more typical TSP problem (very large set size).

[2] The TSP is an NP-hard graph optimization problem, which requires innovative algorithmic solutions such as the Christofides algorithm or ant colony optimization (ACO). An example from the ACO literature:

Dorigo, M. and Stutzle, T.   Ant Colony Optimization: Overview and Recent Advances. In "Handbook of Metaheuristics", M. Gendreau and J.-Y. Potvin eds, International Series in Operations Research and Management Science, Springer, Berlin (2010) Chapter 8.

In a response to this post, I received this response from Minus-Five:
"Interesting article, but Christofides’ algorithm (or its analysis) is not a novelty: What’s actually new here is the discovery that it can be improved, if only by an epsilon (so far)". 
[3] Klarreich, E.   Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem. Wired Science, January 30 (2013).

February 5, 2013

Collective Properties of Cellular Identity, new arXiv paper

Here's a paper of mine recently accepted to the arXiv, cross listed under the q-bio.GN and q-bio.QM categories:


Collective Properties of Cellular Identity: a computational approach

This is independent work I did while in the Cellular Reprogramming Laboratory (and the first paper under the Orthogonal Research affiliation). The data consist of secondary analysis (not quite a formal meta-analysis, but similar) conducted on 45 microarray experiments. In doing so, I employ a unique set of analytical techniques (e.g. soft classification) and evaluate the general tendencies and patterns that constitute cellular type. For example, what constitute differences and commonalities among a range of pluripotent (e.g. stem-like) cell type? Some of the analyses were done using MATLAB, the code for which (disclaimer: use at your own disappointment) can be found at Github. See the cartoon graphic below and full paper for more information.


FYI, Nature News recently ran a feature on the potential of arXiv for the publication of results in the genetics and biology communities. arXiv: no longer just for physicists anymore!



Printfriendly