Computing with chromatin modifications

A few months ago my friend and former Millennium colleague Barb Bryant submitted a manuscript on “Chromatin Computing” for publication. She sent me a preprint, and we started thinking about what we could do together with the ideas she had put forward. Barb and I have since worked together on early versions of these problems, and today we (strictly speaking, Barb) gave a talk at ISMB on some of the results.

Graph with a Hamiltonian Path from 0 to 6

There is one path through this directed graph from node 0 to node 6 that goes through each node exactly once

What Barb did in her paper was very imaginative: she showed, formally, that modifications of chromatin could serve as a universal computing engine following a set of string rewriting rules. Seeing chromatin dynamics in this way is refreshing. One begins to think about what rules underlie chromatin mark changes that actually occur in cells, and how those rules affect biological outcome. In principle, chromatin states could potentially be engineered to solve real problems and thus form a novel type of synthetic biological computer.

There’s a lot more to it, but what we’ve been doing in the last few months is not building biological systems, but extending the ideas using in silico implementation of a chromatin computer. We have a simulator that we can use to understand how rule sets can be used to solve different problems. We’ve solved the original Hamiltonian path problem of Leonard Adelman (recapitulated in Barb’s paper) in a number of different ways. These include several non-deterministic solutions (my student Li Chenhao developed a compact and elegant representation) and a deterministic approach that performs a depth-first search of the graph but requires rules that operate on several regions of chromatin at once (like real complexes that form loops).

Barb’s talk was packed, and we both answered questions. We showed several animations of different solutions to the Hamiltonian path problem using a chromatin computer. The original and modified stochastic solutions animations are fun to watch, but the multi-site rule solution comes with a soundtrack if you use Google Chrome.

There are a bunch of ways we’d like to take this work. One clear challenge is to understand better how chromatin dynamics can be represented in a chromatin computer, starting with mining data available on real chormatin modifying complexes. Another is to implement learning systems using chromatin computers, and apply them to a range of problems. A third is to scour the details of chromatin dynamics for biological inspiration to real problems in computation (Ziv Bar-Joseph’s work is a good model for this).

Finally, there are obvious synthetic biology applications, such as building a biological chromatin computer to solve problems on a dish instead of on a chip. That’s a tall order, but something we can explore first by simulation.

Update: slides are posted on SlideShare

Support Sam Husseini, journalist

This is not a political blog, but it’s the space I have, so occasionally there will be rants on issues or people I feel strongly about.  This is one, about my friend Sam.

Sam Husseini and I went to college together back in the 1980s. I tried to teach him to play guitar, he tried to get me to read Chomsky. Sam grew up in New York. When Sam and his father became naturalized US citizens during Sam’s junior year, Osama Farid Husseini briefly became Samuel Frank Hennessy; we bought him a bottle of liquor and a book of Irish pub jokes so he could learn the heritage of his temporarily adopted surname.

After graduation, Sam, who majored in Applied Mathematics (Computer Science) worked at Moody’s, which he disliked, but rather than taking a job offer with JP Morgan gave up his corporate career for independent journalism. It was a radical career shift, but characteristic of Sam made with reflection and thought. For Sam is, as much as anyone I know, a reasonable person. For about a year after that choice Sam stayed with me and some friends in New Haven, where he did some substitute teaching, and traveled back and forth to New York. During this time he was beginning his long work with FAIR, the persistent New York based media watchdog group. Eventually, Sam went to serve as Communications Director for the American-Arab Anti-Discrimination Committee, and then the Institute for Public Accuracy, which tries to provide alternative voices to the echo chamber of well funded think tanks inside the Beltway.

Sam was one of two groomsman at my wedding, and we’ve remained close despite global movement. We don’t always agree on politics, but that’s at least partly because Sam is fearless. Being a liberal (as I am) is much easier than advocating radical alternatives (as Sam does), especially when your vocation is to speak truth to power. But, once again, Sam is a person of reason and hope, optimistic about individual ideals and imaginative about politics: see his cleverly conceived VotePact for an example.

Just over a week ago, Sam was expelled from the National Press Club, where he was a longstanding member, for agitating. He asked a question about the legitimacy of the Saudi government to the former head of Saudi intelligence. Imagine, a journalist asking an uncomfortable question! Now, I can’t say I would have asked the question Sam asked in exactly the way he asked it, but at heart it’s a damn good question. The context, as Sam introduced his question, was the legitimacy of the Syrian government. Many mainstream journalists are asking questions about the legitimacy of the Syrian government. Those questions are being asked now, and not earlier, because the governments that have been supporting Syria are only now unwilling to defend or ignore Syria’s actions, as it turns it guns on its own people and their aspirations. The guns fire, the governments withdraw their support, and journalists at the National Press Club are able to discuss whether Syria’s government ever had basis for legitimacy.

If the Syrian government’s basis for legitimacy was always a fiction, what of the Saudis? In Chomsky’s anarchism, and perhaps Sam’s radicalism, the answer might be self-evident but apparently the question itself was too much for the National Press Club, who want their luncheons digested undisturbed. Perhaps the National Press Club only wants their members to ask questions wrapped in shiny packages, with “pretty please”, the way we teach children to make requests of adults. That was my first thought. But they don’t. As Sam points out in his open letter to the Press Club, he had been at least as animated and vigorous when asking questions of the Austrian neo-Nazi Jörg Haider, with a hearty support from the NPC moderator. So the problem for the NPC is clearly not who is doing the agitating, but who is being agitated.

Despite the title of this post, I’m not sure what ordinary, non-journalists can do to support Sam, except make our voices heard.  I’m open to suggestions.

The David Allen experience

I had never flown the now defunct America West before flying to Phoenix in the early fall of 1999, but I was aware of its nickname as “America’s Worst”. When I found my seat, I immediately noticed there was no overhead air vent: how cheap does a commercial airline have to be to save on basic ventilation? I was hating this trip before the plane pulled away from the gate.

My brooding was interrupted by the arrival of the person assigned to sit next to me, who was as sanguine and relaxed as I was stressed. I noticed his elegant leather flight bag and his practiced, effortless preparation for takeoff. I had traveled enough by then to know that experienced travelers didn’t usually spend cross-country flights in conversation with strangers, but five hours of complete silence could also be awkward. So when he took his seat, I just said “you must travel a lot”. Continue reading

When kids fall in love with reading

October seems to be all about reading. I’m not sure how this has gone international: I understand October is National Reading Group Month in the USA, and November is National Novel Writing Month. But here in Singapore, both our kids school and the American Club children’s library are hosting October reading events for kids. They tally the number of pages read, and the results count either for charitable fund-raising or for a prize. These kinds of things always leave me a bit ambivalent: one would like to think that such contests would encourage reading, but if the child puts the effort in just to win, and doesn’t come out on top, does it backfire and leave them embittered? There are good arguments that it might.
Continue reading