Ed's Big Plans

Update: Matthew has found an even more thorough review paper that discusses computer assisted synthetic biology approaches — it can be found at doi:10.1016/j.copbio.2009.08.007.

The iGEM competition year is running to a close. The teams are headed into November 2010 and have roughly one month left before attending the conference. I’m personally not attending the conference this year — I think the undergraduates will get more out of the experience.

The current year sees our continued efforts to precipitate a dedicated software team — a functioning autonomous unit that will serve to supplement and enhance Waterloo’s impact in the iGEM competition. More importantly, we’re going to do some very interesting science. We’ve had some success talking with other student groups across campus — notably, we should probably talk with the student IEEE/CUBE chapter when we have more work completed. We had involved BIC as well, however, it was early on and we had even less ground to stand upon ( — the primordial software team was mostly interested in BioMortar and BrickLayer at the time — the later project having been taken up by the iGEM Coop students as in Python this year).

This whole BioCompiler business started when Matthew uncovered a nice candidate problem: the compilation of a schematic for behaviour to a fully functioning synthetic biological circuit. Let’s be as precise as we can be here. I mean to say, we will take a description (which could resemble a piece of formal language source code) — and have it compiled into the sequence of BioBricks that will produce the desired behaviour.

This idea has been approached by several groups before — but each time, a different subproblem was considered (this is a reorganization of Matthew’s very nice list here).

• Synthetic biology programming language: Genetic Engineering of Living Cells (GEC) (Microsoft Research) is a project that hones in on a formal language specification.
• Synthetic biology computer assisted design (CAD): Berkeley Software (iGEM 2009) created a suite of items — Eugene (formal language for synthetic biology), Spectacles (visualizer integrating parts with their behaviours), Kepler (a dataflow broker). As well, Berkeley is responsible for the award winning Clotho (iGEM 2008 – Best Software Tool) which is a workbench that connects with the parts registry database (amongst other possible resources).
• Systems biology pathway reaction simulation: Systems Biology Markup Language (SBML), Systems Biology Workbench (SBW) and Jarnac are a set of tools that perform systems biology analysis (which we consider to be an output of synthetic biology). SBML is the formal language, Jarnac is a reaction network simulator (which utilizes JDesigner as a front end) and SBML is a dataflow broker between SBML and Jarnac.
• BioBrick specific pathway simulation: Minnesota’s Team Comparator (iGEM 2008) created SynBioSS — a tool which estimates the concentration of reactants and products given the appropriate BioBricks on a simulated circuit.

Update — here are a few more items thanks to Matthew Gingerich, George Zarubin and Andre Masella.

• Molecular biology and bioinformatics analysis: The European Molecular Biology Open Software Suite (EMBOSS) is a toolkit developed by the European Molecular Biology Network (EMBnet) for bioinformatics. This might not be immediately relevant, but it is interesting. EMBOSS is actually relatively complete. More distantly along this vein, there’s also Bioconductor which focuses mostly on microarray analysis and is implemented in R.
• More synthetic biology computer aided design (CAD): TinkerCell is a GUI-driven piece of software that supports extension with C++ and Python. TinkerCell along with the suite created by Berkeley Software are the two most promising target systems in which to integrate BioCompiler. Finally, there’s GenoCAD which appears to be in an early phase of development — this software looks to emphasize construction with correct syntax and attribute grammars — I’ll have to read more about this.
• Formal laboratory protocol description: BioCoder is another Microsoft research project — the designed language aims to be both human readable and complete for automation. It reminds me of standard operating procedures (SOP) with greater precision. While BioCoder compiles from protocol to automation, we’ll be compiling to circuitry and protocol. BioCoder will give us some insights about the kinds of protocols that others are thinking of.

There is of course more software, but these are the items that we have become most familiar with — that we like — and that we consider to be standards toward which our own work should strive.

Two interesting problems arise when we think about these subproblems. First, the programming languages specified (including Eugene from Berkeley’s CAD suite) are exactly what they claim to be. Formal specifications. This is possible because of how concrete they are. They literally document what a synthetic biology circuit is. But this isn’t too different from what humans have been doing in iGEM all along. Second, the synthetic biology items don’t really seem to talk to the systems biology items — whereas we expect that the two — being input and output — to be inextricably linked. I explain my thoughts on the two below.

Why a programming language?

Andre enlightened me to this the other day. Humans invented programming languages to do two things. On an arrow running from the concrete toward the esoteric, we have the practical concern of compressing the amount of code that we want to write while retaining our programs’ expressiveness. This is the origin of macro systems such as COBOL. On an arrow pointing in the reverse — from the cerebral abstract down to the literal — we have the theoretical concern of mathematical beauty, of completeness. This is the origin of such functional languages like Lisp. For humans to have any hope of creating such a Lisp-like language for synthetic biology — we would need to understand all of the reactionary nuances about it, the system with which we tamper — at least inasmuch as a painful heuristic approximation. This is a feat we are no where near completing though footholds are managed with systems biology.

So here we are, BioCOBOL is the first step. A developing simple — though complete macro-like system that is in league in terms of abstraction with the programming language / CAD -like projects we’ve seen thus far. Only, we aim to increase the efficiency of circuit design; so that the programming language is not a literal mapping of the human document — rather, it is an explanation of behaviour. We will abstract it ever so slightly with each iteration of development — departing further and further away from CAD. A subteam headed by Brandon is currently developing the syntax and search algorithms required for the job — Brandon suggests that a weighted traversal of valid circuits should form our algorithmic primitive. My subteam is attempting to characterize as many known circuits in iGEM as possible — analyzing what pieces of input (stimuli: chemical concentrations, gradients, quora, oscillators) may be compressed for their common usage — what function prototypes already exist ( — reacts to an input: promoters) for compression — what the standard outputs are (analogy to printing error messages: GFP-family) etc. — again in the effort to realize what is losslessly compressible. Our software should eventually provide the correct laboratory protocol as well.

In this sense, we are respecting what a compiler is before we even approach more sophisticated compilation: it transforms a document in one language to another.

Incidentally, I should mention that Jordan and George are working on a modelling problem with the lab team — I’m not clear on the specifics, but I take it they want to pull out some differential equations on a set of promoters.

Why do we care that Synthetic Biology logic should talk to Systems Biology logic?

Finally, it is clear that we will eventually want to become even more abstract — even more mathematically complete, even more expressive. While we may never know enough about systems biology to create BioLISP (in our lifetime), we expect there to be sufficient research for us to discover — and perhaps research we can conduct ourselves to come ever closer. Systems biology allows us to think about synthetic biology in terms of reaction concentrations; free energy etc.. It gives the notion of compilation its own ground; the ground we want to cover. Imagine the perfect BioCompiler — stating the a problem to be compiled in terms of the input and output of the system. Let’s be precise here: I mean to say, the products and reactants or behaviour of our circuit. Let us describe what our circuit will do instead of what our circuit is made of. This — the missing link, this compiler — is the logical final step of BioCompiler.

Brief: This is the fourth semester of the PhD program I’ve found myself enrolled in. Here’s a quick rundown of what I’ll be up to this time around now.

• Thesis proposal defense on Oct. 8th — Symmetrical protein phylogeny and engineering (final title) — I’m ready to have it torn apart by the committee
• TA BIOL 208 — Analytical methods in molecular biology; will be marking midterms next week in a tiny yet well lit room with half a dozen TAs. I’ll bring coffee.
• Scholarship applications just completed. They’re both to be submitted next week — wish me luck!
• BioCompiler (UW iGEM) moving along much faster thanks to Matthew‘s hard work writing up the first AND second drafts of the project outline — sidestep: it’s going to be more like BioMacro for a long time first.
• Taking BIOL 614 — Bioinformatics tools; and possibly CHEM 731 — Protein design and engineering. I’m happy that BIOL 614 complements the CIS 6060 bioinformatics course I took at Guelph.

It looks to be a full semester.

Brief: I encourage anyone who wants to play to do so– this is the second year that the Intelligent Systems Challenge has existed. If I had a little more time and a team, I’d do this Registration has still yet to open so go read up on natural language processing and state failures.

Matthew‘s part of a team that’s participating again this year

I’ve been so out of the loop with iGEM over the last month. I’ll need to figure out how to get back into the swing of things, probably starting with the post mortem meeting on Tuesday. Generally, since no new maths could be put on the table that actually encompassed the problem well– the brute force approach was kicked into high gear with a few more filters to increase the probability of success.

Call these “System Filters” since they aren’t really based on biologically significant concepts, really just sanity checks that are conceptually consistent with the project (i.e. we’d run out of hard disk space otherwise…). Significantly, Matthew implemented “Blank Stare”, which destroys reactants that exceed a given length (thus preventing them from hogging the CPU looking for less parsimonious solutions). Less significant were Andre’s “Lone Gunman” which deletes arbitrary chromosomes with stochastic efficiency and my “Tag” which prevents chromosomes from cross reacting.

(On second thought, “Tag” IS a “Biological Filter” not a “System Filter” because it removes redundancy by implementing the rule that we only admit bacteria that have exactly one chromosome.)

I should mention that “significance” above isn’t about the triviality of the code, it’s about the amount of anticipated efficiency boon we’d gain from an item’s deployment.

Tomorrow’s post mortem will continue the work I’ve started on our iGEM 2009 Wiki Modelling page… We’ll decide what we want to mention, how close we got to our solution and figure out how to precisely characterize the problem space uncovered by our various attempts.

Additionally, we should probably discuss the relevance of John’s attN site cloning and tests to see if the operators show any sign of degeneracy, and which ones in particular.

Finally, I should mention that Brandon has been working on a C++ port of the whole application we wrote in Python to elucidate how much the virtual machine impacted the performance of our solver– the team is quite divided on this idea with a big half (myself included) thinking that the exponential growth due to the algorithm is the greater factor– Brandon may have some answers for us when it’s up and running.

Andre and Brandon

I’ve been away recently, so this task has apparently been uptaken by Jordan. The reverse-hashing integer-to-sequence function to be done for modeling was formalized a bit more in a meeting about two weeks ago, and I’ve yet to be briefed about what form it’s taken in yesterday’s meeting.

Update: Andre tells me that Jordan did in fact finish the sources, and everything ran overnight– however, the exponential explosion that we were afraid of ended up occurring; the present algorithm (part of which is described below) ran to the fourth iteration and well, would continue to run for a few weeks had it not been stopped… It looks like there’s ever more need for a working bottom-up approach…

Getting to absolute basics, this reverse hashing function converts positive integers to a sequence of arbitrary base strings– actually, I want to describe the general form of this function in case I need it in future. So if we know the size of the alphabet used for each character of a string, we can give each character a unique ordinal value. Two examples follow…

Brandon and Matthew


#Latin Alphabet (as used in English)
(A, 1), (B, 2), (C, 3), (D, 4) ... (Y, 25), (Z, 26), (null, 0)

#Nucleotides
(A, 1), (C, 2), (G, 3), (T, 4), (null, 0)

If we want to represent a string, we’d simply substitute the integer for the character.

#BADEGG
214577

#AGGCTT
133244

Bredth First Search Sphere

Bredth First Search Sphere [figure]… Andre used this chalkboard diagram to illustrate to Chong that this encoding conveniently increases in sequence length– we could consider this cardinality, or radius, or more importantly, the number of hops on a graph representation– when this problem is considered in lexicographic ordering, the implied algorithm is a bredth-first traversal.

We ran into a problem– this would at most represent one string. Brandon came up with a workaround, the notion of stealing characters from a sequence based on the modulus of its index! So, if we wanted to encode three strings, then every character at (index%3 = 0) belongs to string A. Strings B and C would then occupy (index%3 = 1) and (index%3 = 2) respectively.

Examples:

#Encode BADGE, FEED and AI together
#Pushes together as... BAA AEI DEx GDx Exx
#Where lowercase 'x' is null.
211159450740500

So that null symbols are inserted to preserve the correct location of each symbol.

3D 3Layer Cake

3D 3Layer Cake [figure]… An alternative approach to the encoding is to produce a triplet of integers instead of interweaving them; to farm out the sequences to be operated on, one would keep the entire domains of any two of the three sequences, while distributing the third; actually– this can still be done with the present encoding scheme, just farm out a fraction of the sequences based only on certain indexes of each sequence (the indexes satisfying the modulus math statements above). Abstractly, we can think of this as a three-dimensional cake where one dimension is distributed in layers– a three-serial-CPU-farm would consume a three-layered cake.

There’s one other thing I haven’t quite discussed, and that’s sequence sensitivity– Some sequences are masked so that the location of a certain integer implies a different entity depending on their position in their string– I’ll leave that for another post though.

I’ll have to discuss the bottom-up approach we’re going to try next– or not try at all since the modeling team is running very short on time; doing things by hand would either require inspiration, a marvel of human savant-like adduction or incredible luck… Jordan apparently demoed the algorithm by hand at the meeting I missed and showed the normal human mind can’t cope with the growth of the problem either…

Jordan playing a first person shooter...

Matthew also has a post about Recombinatron & Big Bang Day here.

‘Big Bang Day’ was this awesome Saturday morning where a bunch of the UWiGEM modeling folks came together and integrated our modules together. We ended up delegating more work, understanding the problem better and fixing up some of the logic in the big picture. After everyone had filed in and we managed to figure out how to synchronize with the SVN…. and after I managed to break the SVN and fix it again (thankfully!), it was time to get to work. I think the project as it stands right now is more or less done unless Giant Scaffold manages to find something that needs fixing.

The big picture was simplified to three giant objects that passes a big bag of DNA to one another in sequence.

The DNA bag is actually a list of DNAClass Objects (DNAObjects)– We decided not to create our own collection… there’s already a Python list. The Giant Scaffold module controls the movement of the DNA bag or subset there of from storage to Operators to Filters.

I was working with the Operators team– Basically, Matthew finished our team’s work because I managed to get swamped with thesis defense preparations, and Andre managed to take down the UWiGEM server.

(Andre incidentally has a post about taking down servers and making backups here.)

The Operators team ended up producing two big functions (and their little internal functions) and one support function.

reactOneStrand(DNAObject) – Produces a list of resultant DNAObjects when the integrase enzyme is used on a single strand of DNA– this function may produce a one-list, two-list or three-list of DNAObjects. One-lists result from inversion (indirect) reactions, two-lists result from excision (direct) reactions, and three-lists result from palindromic operators.

reactTwoStrands(DNAObject, DNAOther) – Produces a list of resultant DNAObjects when two strands of DNA are reacted together with integrase.

The Filters team split their filters into three big enclosing functions– these three functions are equivalent to categories based on the likelihood that a given event would happen in a cell (Frequent, Moderate, Infrequent).

I unfortunately had to leave roughly 2.5 hours into Big Bang Day on other business but was happy to continue the madness online and on a subsequent Monday.

And now… some more photos…

Look! Everyone’s on their laptops– gee, I didn’t know they had Python on computers now!

Wylee, Brandon and Jordan are all part of the Filters team.

Chong is part of the Giant Scaffold team. Matthew and Andre are part of the Operators team.