Design Philosophies of Developer Tools

Clojure hacker Stuart Sierra wrote an insightful piece on the design philosophies of developer tools. His conclusions are paraphrased here:

Git is an elegantly designed system of many small programs, linked by the shared repository data structure.

Maven plugins, by contrast, are not designed to be composed and the APIs are underdocumented. With Maven, plugins fit into the common framework of the engine, which strikes me as maybe a more difficult proposition than many small programs working on a common data structure.

Of the anarchic situation with Ruby package management (Gems, Bundler, and RVM) Sierra says, “layers of indirection make debugging harder,” and “The speed of development comes with its own cost.”

Principles

• Plan for integration
• Rigorously specify the boundaries and extension points of your system

...and I really like this idea:

• The filesystem is the universal integration point
• Fork/exec is the universal plugin architecture

Phenotypic constraints drive the architecture of biological networks

Biological networks are often compared to random networks in terms of properties like degree distribution, clustering, robustness and over-representation of network motifs. In a talk this morning, Areejit Samal, a Postdoctoral Fellow in the Price lab at ISB, proposed a new null model based on Markov Chain Monte Carlo (MCMC) sampling to generate realistic benchmark ensembles for metabolic networks and gene regulatory networks. Based on this improved background model, the conclusion is that “phenotypic constraints drive the architecture of biological networks”, which is also the title of the talk.

doi:info:doi/10.1371/journal.pone.0022295.g004

Applied to the metabolic model of E. coli, the sampling technique involves two steps. In the swap step, a reaction is removed from the network and a new reaction is drawn randomly from the KEGG database to replace it. The proposed new network is then tested by flux-balance analysis. If the new network is viable, it is accepted. If not, it is rejected. So, only networks that are biochemically plausible are sampled.

The technique has implications for systems and synthetic biology as well as evolutionary theory. By approximating the space of all possible networks that might lead to a viable functioning organism, we can better understand what properties these networks have, and maybe better design new networks. By changing the acceptance criteria to enforce viability in a second environment, the algorithm nicely models the evolutionary emergence of modularity.

Samal also showed the same general algorithm applied to the gene regulatory network controlling flowering in Arabidopsis.

I especially appreciated seeing a really cool application of Markov Chain Monte Carlo sampling, a topic covered only a couple weeks back in the Probabilistic Graphical Models class.

Links

• Randomizing Genome-Scale Metabolic Networks, Areejit Samal, Olivier C. Martin (2011)
• Environmental versatility promotes modularity in genome-scale metabolic networks (2011)
• Genotype networks in metabolic reaction spaces (2010)
• Neutralism and selectionism: a network-based reconciliation, A. Wagner (2008)
• The road to modularity, G. Wagner (2007)

Maximum expected utility decision rules

Week 6 of the Daphne Koller's Probabilistic Graphical Models class looks at Decision Theory, which integrates the concept of utility functions from economics into our models. I'm getting flashbacks of Dr. Welsh's Econ 101 in Schwab Auditorium.

In the Influence network below, we're making a decision about whether to found a company. Our success is determined by market conditions, which we can't observe. But, we can observe the results of a survey, which will give us some information on which to make our decision. So, how would you find the optimal decision rule?

The factor fm represents the probability that market conditions (var 1) are good (3), fair (2) or poor (1).

fm.var =  1
fm.card =  3
fm.val = [0.5 0.3 0.2]
PrintFactor(fm)
1 
1 0.500000
2 0.300000
3 0.200000

The factor fsm represents the results of a survey (var 2) given the underlying market conditions (var 1).

fsm.var = [2 1]
fsm.card = [3 3]
fsm.val = [0.6 0.3 0.1 0.3 0.4 0.3 0.1 0.4 0.5]
PrintFactor(fsm)
2 1 
1 1 0.600000
2 1 0.300000
3 1 0.100000
1 2 0.300000
2 2 0.400000
3 2 0.300000
1 3 0.100000
2 3 0.400000
3 3 0.500000

The factor fufm represents the utility function, given the market conditions (var 1) and the decision to found (var 3) a company, yes (2) or no (1).

fufm.var = [3 1]
fufm.card = [2 3]
fufm.val = [0 -7 0 5 0 20]
PrintFactor(fufm)
3 1 
1 1 0.000000
2 1 -7.000000
1 2 0.000000
2 2 5.000000
1 3 0.000000
2 3 20.000000

Compute mu of F, S by taking the factor product of factors representing the market, survey and utility function, then summing out over all possible market conditions (var 1).

PrintFactor(FactorMarginalization(FactorProduct(FactorProduct(fm, fsm), fufm), [1]))
2 3 
1 1 0.000000
2 1 0.000000
3 1 0.000000
1 2 -1.250000
2 2 1.150000
3 2 2.100000

We can build our decision rule by walking down all possible survey results (var 2) and selecting the decision to found or not which maximizes expected utility. See the red circles at the bottom of the diagram.

We can make a decision factor, which depends on the survey (var 2). We'll fill in dummy values, for now.

fd.var = [3 2]
fd.card = [2 3]
fd.val = ones(1,prod(fd.card))

Now, we can use the code from the programming assignment to compute the optimal decision rule and the expected utility it yields.

marketI.RandomFactors = [fm fsm]
marketI.UtilityFactors = [fufm]
marketI.DecisionFactors = [fd]
[meu optdr] = OptimizeMEU(marketI)
meu =  3.2500
optdr =
  scalar structure containing the fields:
    var  =       3   2
    card =       2   3
    val  =       1   0   0   1   0   1

The Scalable Adapter Design Pattern for Interoperability

When wrestling with a gnarly problem, it's interesting to compare notes with others who've faced the same dilemma. Having worked on an interoperability framework, a system called Gaggle, I had a feeling of familiarity when I came across this well-thought-out paper:

The Scalable Adapter Design Pattern: Enabling Interoperability between Educational Software Tools, Harrer, Pinkwart, McLaren, Scheuer, IEEE TRANSACTIONS ON LEARNING TECHNOLOGIES, 2008

The paper describes a design pattern for getting heterogeneous software tools to interoperate with each other by exchanging data. Each application is augmented with an adapter that can interact with a shared representation. This hub-and-spokes model makes sense because it reduces the effort from writing n(n-1) adapters to connect all pairs of applications to writing one adapter per application.

Scalability refers to the composite design pattern, implementing (what I would call) a more general concept, that of hierarchically structured data. If you've ever worked with large XML documents, calling them scalable might seem like an overstatement, but I see their point. XML nicely represents small objects, like events, as well as moderately sized data documents. The same can be said of JSON.

Applications remain decoupled from the data structure, with an adapter mediating between the two. The adapter also provides events when the shared data structure is updated. A nice effect of the hierarchical data structure is that client applications can register their interest in receiving events at different levels of the tree structure.

The Scalable Adapter pattern combines of well established patterns - Adapter, Composite and Publish-subscribe yielding a flexible way for arbitrary application data to be exchanged at different levels of granularity.

The main difference between Scalable Adapter and Gaggle is that Gaggle focused on message passing rather than centrally stored data. The paper says, "it is critical that both the syntax and semantics of the data represented in the composite data structure...", but they don't really address what belongs in the "Basic Element" - the data to be shared. Gaggle solves this problem by explicitly defining a handful of universal data structures. Applications are free to implement their own data model, achieving interoperability by mapping (also in an adapter) their internal data structures onto the shared Gaggle data types.

The Scalable Adapter paper breaks the problem down systematically in terms of design patterns, while Gaggle was motivated by the software engineering strategies of separation of concerns and parsimony, plus the linguistic concept of semantic flexibility. It's remarkable that the two systems worked out quite similarly, given the different domains they were built for.

Sage Bionetworks Synapse

Michael Kellen, Director of Technology at Sage Bionetworks, is trying to build a GitHub for science. It's called Synapse and Kellen described it in a talk at the Sage Bionetworks Commons Congress 2012, this past weekend: 'Synapse' Pilot for Building an 'Information Commons'.

To paraphrase a Kellen's intro:

Science works better when people build off of each other's works. Every great advance is preceded by a multitude of smaller advances. It's no accident that the invention of the printing press and the emergence of the first scientific journals coincide with the many great scientific discoveries of the age of enlightenment. But scientific journals are stuck in a paradigm revolving around the printing press. In other domains, namely open source software, people are more radically reinventing systems for sharing information with each other. Github is a collaborative environment for the domain of software. Synapse aims to be a similar environment for medical and genomic research.

The Synapse concept of a project packages together data and the code to process it. I tried to download the R script shown in the contents and couldn't, either because I'm a knucklehead or because Synapse is a work in progress. On the plus side, they give you a helpful cut-n-paste snippet of R code in the lower right corner to access the project through their R API. When this is fully implemented, it could provide a key piece of computing infrastructure for reproducible data-driven science.

Sage intends to explore ways of connecting to traditional scientific journals. Picture figures that link to interactive visualizations or computational methods that link to code. I'm a big fan of the "live document" concept and it would be great to see journal articles evolve in that direction.

An unintended consequence of NGS, Robert Gentleman points out, is that the data is too big for existing pipes. Any concept of a GitHub for science will have to incorporate processing biological data in the cloud. I could imagine a Synapse project containing data sets, code and a recipe for standing up an EC2 instance (or several). At a click, a scripted process would run, bootstrapping the machines, installing software and dependencies, running a processing pipeline, and visualizing the results in a browser. How would that be for reproducible science?

Michael Kellen's blog has a bunch of interesting stuff about why building a GitHub for biology is more fun than selling sheets. I bet it is.

Interactive Dynamics for Visual Analysis

“To be most effective, visual analytics tools must support the fluent and flexible use of visualizations at rates resonant with the pace of human thought.”

This comes from a recent paper by Jeffrey Heer of Stanford's Visualization Group and Ben Schneiderman titled Interactive Dynamics for Visual Analysis in ACM Queue, following up on another Queue article from 2010 by Jeffrey Heer, Michael Bostock and Vadim Ogievetsky, A Tour Through the Visualization Zoo. The Interactive Dynamics article categorizes aspects of visual analysis that deserve careful consideration when designing visual analysis tools.

Taxonomy of interactive dynamics for visual analysis

• Data and View Specification
  • Visualize
  • Filter
  • Sort
  • Derive (values or models)
• View Manipulation
  • Select
  • Navigate (zoom, drill-down)
  • Coordinate (linked views)
  • Organize (multiple windows)
• Analysis Process & Provenance
  • Record
  • Annotate
  • Share
  • Guide

Heer and collaborators created a series of software libraries for interactive visualization: prefuse, flare, Protovis and D3. These frameworks are designed to "represent data to facilitate reasoning", "flexibly construct representations" and "enable representational shifts" or transformations.

Protovis, which I've fooled around with a bit, is a functional domain specific language for data visualization. It's successor, D3 (Data Driven Documents), is an adaptation that increases performance and expressivity by making more direct use of the model (the DOM) inherent in the browser.

Jeffrey Heer spoke recently at the University of Washington (video available) about his research, citing as an early influence a 1962 paper by John W. Tukey titled The Future of Data Analysis.

In some ways, Heer nicely echoes themes from Hadley Wickam's talk on Engineering Data Analysis.

Data analysis pipeline:

Heer outlines an iterative process with these steps: Acquisition > Cleaning > Integration > Visualization > Modeling > Presentation > Dissemination.

Also from the Interactive Dynamics paper:

“In concert with data-management systems and statistical algorithms, analysis requires contextualized human judgments regarding the domain-specific significance of the clusters, trends, and outliers discovered in data.”

I've been a Jeffrey Heer fan-boy for some time, starting with his 2006 paper, Software Design Patterns for Information Visualization. Those interested in learning data science skills could do a lot worse than study Jeffrey Heer's work.

More papers

• GraphPrism: Compact Visualization of Network Structure
• Orion, a tool for network modeling and analysis
• Wrangler, a declarative data transformation language
• Stanford Vis group papers
• Interactive High-Dimensional Data Visualization (Buja 1996)

Probabilistic graphical models

I'm taking Daphne Koller's class on Probabilistic Graphical Models. Wish me luck - it looks tough. So, first off, why graphical models?

The first chapter of the book lays out the rational. PGMS are a general framework that can be used to allow a computer to take the available information about an uncertain situation and reach conclusions, both about what might be true in the world and about how to act. Uncertainty arises because of limitations in our ability to observe the world, limitations in our ability to model it, and possibly even because of innate nondeterminism. We can only rarely (if ever) provide a deterministic specification of a complex system. Probabilistic models make this fact explicit, and therefore often provide a model which is more faithful to reality.

More concretely, our knowledge about the system is encoded the graphical model which helps us exploit efficiencies arising from the structure of the system.

Distributions over many variables can be expensive to represent naively. For example, a table of joint probabilities of n binary variables requires storing O(2ⁿ) foating-point numbers. The insight of the graphical modeling perspective is that a distribution over very many variables can often be represented as a product of local functions that each depend on a much smaller subset of variables. This factorization turns out to have a close connection to certain conditional independence relationships among the variables - both types of information being easily summarized by a graph. Indeed, this relationship between factorization, conditional independence, and graph structure comprises much of the power of the graphical modeling framework: the conditional independence viewpoint is most useful for designing models, and the factorization viewpoint is most useful for designing inference algorithms

An Introduction to Conditional Random Fields by Charles Sutton and Andrew McCallum

Bayesian networks and Markov networks (aka Markov random fields) are the two basic models used in the class, the key difference being directed vs. undirected edges. In a Bayesian network, the edges are directed while they are undirected in a Markov network.

How are these different kinds of graphic models related? Let's hope we'll find out.

There's a study group meetup here at the Institute for Systems Biology (and maybe other locations) on Thursday night. Come join us, if you're in Seattle and you're doing the class.

Supplemental reading

• Inference in Bayesian networks
• What is a hidden Markov model?, a primer by Sean Eddy
• Rabiner's Tutorial on Hidden Markov Models
• Octave Cheat Sheet. Like Andrew Ng's Machine learning class, the PGM class uses Octave, too.