BEACON Researchers at Work: Engineering life

This week’s blog post is by University of Washington graduate student Leandra Brettner.

LeandraAll living organisms share a universal programming language—DNA. Long strings of unit molecules A’s, T’s, C’s and G’s dictate the unique traits of each individual, but the code is read ubiquitously across each species. This means that a gene that encodes a protein in one organism would encode the same protein if transplanted to another creature. Synthetic biologists use this property to engineer life by doing just that, rearranging genes from different species to program new behaviors into organisms. I am a synthetic biology graduate student in the lab of Professor Eric Klavins, and I work with genetically programmed bacteria, specifically Escherichia coli.

Microbes such as viruses, bacteria and yeast, are cheap and easy to grow, making them excellent platforms for synthesizing traditionally expensive organic chemicals such as fuels, pharmacologicals, and commodities like plastics. By performing the chemistry to create these products in microorganisms, we can potentially both decrease cost and increase sustainability and performance. Researchers like Jay Keasling at UCSF and Angela Belcher at MIT are demonstrating the amazing utility of living chemistry by manufacturing drugs such as artemisinic acid in yeast and building record breaking batteries out of viruses.

However, when we introduce foreign behaviors into cells, we are competing with millions if not billions of years of evolutionary history. Microbes, like all organisms, work hard to maintain the energy balance that supports life. Synthetic programs mess with that equilibrium, limiting the engineering complexity we have currently been able to achieve.

I work on developing ways to increase the complexity of engineered behaviors in microbes by isolating them into working groups—kind of like how factories use assembly lines, everyone has a specific task that contributes to the whole. These division of labor schemes are seen through every hierarchy of biology, from symbiotic bacteria to eusocial insects.

Our system’s goal is to digest complex carbohydrates like those in plant waste and turn it into usable biomass that can go towards producing carbon-based products like the biofuels and therapeutics mentioned, further reducing the cost and making production carbon neutral.

schematic of systemThe population of engineered bacteria start out in a consumer state where their only job is to grow and reproduce. Then, every so often, a cell will switch to an altruistic state where it produces an enzyme that breaks down cellulose and lyses to deliver the goods to the extracellular environment. The digested sugars can then be used as food for the consumer cells.

This cooperative architecture has allowed us to build in the complex behavior of novel nutrient use that can be coupled with chemical production in the future.  

However, this system suffers from an interesting form of community evolutionary instability called “the tragedy of the commons.” In well mixed culture, any variants that arise that cease to perform the cooperative behavior (cheaters) can still reap the public good provided by the altruists. Because they fail to lyse, the cheaters have an increased fitness advantage and can sweep the population—but to their ultimate demise. Without the altruists, cellulose digestion comes to a halt and the population crashes. Previous work has shown that if, however, there is some spatial organization to the environment, the communal benefit applies only to nearby, closely related cells who are likely fellow altruists. The cheaters are left stranded with limited or no access to the resource. This phenomena, dubbed kin selection, propagates the cooperative behavior through many generations. Members of Professor Ben Kerr’s lab are currently working with my system to investigate if they can evolve strains that exhibit increased cooperation by propagating cell lines in structured environments.

I look forward to continuing to collaborate with the Kerr lab, and potentially extending their research to the design and tuning of new synthetic organisms.

For more information about Leandra’s work, you can contact her at leandra dot brettner at gmail dot com.

Posted in BEACON Researchers at Work | Tagged , , , , , | Leave a comment

Meet the 2014 BEACON Distinguished Postdocs, Chandra Jack and Will Soto

This year, BEACON was fortunate to be able to appoint TWO new Distinguished Postdoctoral Fellows. Meet Chandra Jack and Will Soto!

Chandra Jack

ChandraChandra started working in the Strassmann-Queller lab at Rice University as an undergraduate in the summer after her sophomore year to earn money while volunteering as a member of the Rice EMS. That summer she began research looking at kin discrimination between different genotypes of Dictyostelium purpureum. Originally planning to go to medical school, Joan got her hooked on all things dicty, so she spent a year after graduating as a technician before beginning graduate work in the same lab. She received her PhD in evolutionary biology where her thesis work explored how the population structure of D. discoideum is affected by interactions with related species and with other members of the same species.

Now at MSU, Chandra joined the Friesen’s lab in the plant biology department in August. She was really interested in Maren’s research exploring the mutualism between plants and rhizobia, as well as the many methods being used in the lab. However, she isn’t sure if Maren would have accepted her if she knew her plant reputation included losing one cactus and killing another.

(Currently all of her plants are alive and accounted for.)

Her research will address the role of PMI (Plant-Microbe-Insect) interactions in driving rapid evolution using Medicago polymorpha. She will compare the response of different genotypes of M. polymorpha from its native habitat in Europe to those of invasive genotypes found in North America when they interact with local (N. American) herbivores and rhizobacteria from both environments to look for evidence of genetic variation and to see if genetic variation between the two genotypes results in changes in gene expression. She will also create models that investigate the role of PMI interactions on the relationship between gene expression and plant fitness. Chandra’s work will determine the importance of multitrophic level interactions on rapid evolution and the success of invasive species as they enter new territories.

For more information about Chandra’s work, you can contact her at chandra dot jack at gmail dot com.

Will Soto

Will Soto

Will received his B.S. in biology from California State University, Fresno. Will developed an enthusiasm in microbiology in high school biology classes but became fascinated with evolution as a subject while at CSU, Fresno. Learning about the geological history of the fossil record and the rich biological diversity that evolved through adaptive radiations was exciting to Will. Evolution’s great stories like the “Age of Fishes,” “hopeful monsters,” the Cambrian Explosion, and mass extinctions were intriguing to Will. Additionally, learning about evolution made Will wonder why there were no freshwater echinoderms or freshwater cephalopods, given the tremendous biodiversity of these taxonomic groups. “Evolution has a great folklore and causes one to wonder about the rest of the natural world,” says Will. Will’s interests in microbiology and evolution merged into one. Will was especially interested in prokaryotes due to their colossal genetic and metabolic diversity.

After graduation from CSU, Fresno, Will spent two years in Fred Cohan’s lab at Wesleyan University, where he studied bacterial evolution. “It was in Fred Cohan’s lab that I learned about microbial experimental evolution and developed an interest for the work of Rich Lenski, Al Bennett, and Mike Travisano,” says Will. “When I read the Nature paper by Rainey and Travisano (1998) about adaptive radiation with Pseudomonas fluorescens, I was completely thrilled,” states Will. “Wrinkly spreaders and fuzzy spreaders; here’s another cool story,” he adds. After leaving Wesleyan University, Will entered a PhD program at New Mexico State University in Las Cruces in Michele Nishiguchi’s lab, where he studied the sepiolid squid-Vibrio mutualism. Will pursued a microbial experimental evolution project, where he serially passaged Vibrio fischeri through a novel squid host. “I took a V. fischeri strain indigenous to the Hawaiian bobtail squid (Euprymna scolopes) and serially transferred it through the Australian dumpling squid (Euprymna tasmanica),” claims Will. “I had a great PhD advisor who allowed me complete freedom. I also had a fantastic graduate committee,” says Will. Kathy Hanley, Geof Smith, John Gustafson, and Michele Nishiguchi were all on Will’s dissertation committee. Kathy Hanley is a superb evolutionary biologist, while Geof Smith and John Gustafson (now at Oklahoma State University in Stillwater) are spectacular microbiologists. Michele Nishiguchi provided the expertise on host-microbe interactions, along with the sepiolid squids and bioluminescent V. fischeri.

In 2012, Will became a postdoctoral teaching fellow funded through a grant from the Howard Hughes Medical Institute. He had two excellent postdoc advisors, Mike Travisano and Robin Wright. “I was delighted to be in Mike Travisano’s lab, as he was one of my grad school heroes!” says Will. In Mike’s lab, Will learned the tricks of the trade to microbial experimental evolution. Robin Wright mentored Will in the value of active learning, science education, and how to incorporate research into undergraduate education. “At the University of Minnesota-Twin Cities, I got to teach in an active learning classroom for the first time alongside Robin Wright. The experience was invaluable!” claims Will. 

Here at Michigan State University, as BEACON postdoc fellow, Will is working with Chris Waters on developing host infection models between disease-causing marine bacteria (e.g., Vibrio harveyi) and invertebrate hosts (e.g., shrimp) for microbial experimental evolution projects. “Chris and I are trying to take microbial experimental evolution with vibrios to aquaculture,” states Will. Will concludes, “I don’t understand why more microbial experimental evolution work hasn’t been done with the Vibrionaceae. This bacterial family has much to offer in studying evolutionary biology.”

For more information about Will’s work, you can contact him at wsoto at msu dot edu.

Previous recipients of the BEACON Postdoctoral Fellowship are Annat Haber (2013) and Joshua Nahum (2012).

Posted in BEACON Researchers at Work | Tagged | Leave a comment

BEACON Researchers at Work: Using evolution to update old software

This week’s BEACON Researchers at Work blog post is by MSU graduate student Erik Fredericks. His first BEACON blog post is here.

Erik FredericksEngineers in industry are often given the somewhat daunting task of updating legacy software systems. Consider, for a moment, a piece of software used on a daily basis at a particular company, say, Initech. This software was programmed roughly twenty years ago by an engineer that has since left the company, leaving only cryptic comments and mostly unreadable software requirements. However, the importance of this software is paramount to Initech’s success, given its near-ubiquitous use throughout the corporation.

Times have changed over the past 20 years, Initech has gone through some changes, and our software package is quietly reaching the end of its usefulness. However, everybody still continues to use it, even though it is no longer as useful as it once was. Conveniently, a new engineer has been hired and is given his first task: update the software system, thereby extending its effective lifetime. Everybody is already used to it, the TPS reports it generates are spot-on, re-training all employees would be cost-prohibitive, and really, how hard can it be to update software?

After spending weeks gathering new requirements, analyzing the source code, and evaluating the overall state of the framework, our engineer has determined that the easiest way to fix the software system is to use software composition. Composition is a reuse technique for introducing new functionality into existing systems by reusing existing modules from other software systems. For instance, security can be added to a web application by composing in a security module that has been written for another application, where the composition is enabled by transforming the existing data into the format required by the new security module. Moreover, the data being returned must also be transformed into the format required by the legacy application.

Even though the code for the new module has already been written, there still remains many different ways in which to compose the module. For instance, how exactly should the legacy software system send data to the module? How should the data be returned? Is it even written in the same programming language? There are innumerable approaches for transforming data, and our software engineer would rather not spend the extra time and effort figuring out how to accomplish this task. Our engineer decides that an automated approach is best. Enter, context-free grammar-based genetic programming (CFG-GP).

CFG-GP is a search-based technique for automatically generating programs, similar in fashion to the standard genetic program. It comprises a population of candidate solutions that are evolved over time towards a particular goal or set of goals. CFG-GP differs from standard genetic programming in the solution representation. Particularly, each possible solution defined for the genetic program is specified by a context-free grammar. The grammar imposes a structure on generated solutions, effectively reducing the amount of invalid programs typically generated by a normal genetic program and also reducing wasted computing time. For composition, the grammar provides a structure for the many different ways in which data can be transformed for a particular programming language.

As with a typical genetic program, CFG-GP must also specify a fitness function to guide the search process towards an optimal solution. In our case, we leverage software preconditions and postconditions, along with common software engineering metrics, to guide the search process. Preconditions and postconditions define the conditions necessary for a module to be invoked within a program. For example, preconditions can define the data type and order of method parameters, and postconditions can define a method return value or the state of the program following invocation of the method. Together, preconditions and postconditions define what exactly is required for a method to be used by a program, enabling us to use it as part of the fitness function. In our case, candidate solutions must satisfy all preconditions and postconditions.

For example, we may wish to define preconditions and postconditions for a new security module, particularly for encrypting data to be sent to a server. A sample encryption module we wish to compose is defined as follows, in which the encryption function accepts two strings and a string pointer, and returns a boolean value:

<bool> openssl_private_encrypt(String data,
                               String &encrypted,
                               String private_key)

We now define the preconditions and postconditions necessary to compose this module. Particularly, the module preconditions represent the format the data is required to be in prior to module invocation. Essentially, we are interested in the parameters accepted by the module:

  • STRING: data_in
  • POINTER: data_out
  • STRING: key

Next, the postconditions for the module must be defined to represent the state of the data following invocation of the module. Here, we are interested in what the module returns back to the legacy software system:

  • BOOLEAN: return_value

Using these preconditions and postconditions, coupled with further definition of data available and state of the legacy software system prior to and following module invocation, we can successfully compose the security module.

Common software engineering techniques also help to guide the search process at a high level, enabling an engineer to fine-tune the set of optimal solutions. For instance, minimizing the amount of extra function calls, data dependencies, or amount of generated code may be required on systems that have limited memory available. Obfuscation of generated code may also be of interest for high-security systems. Satisfaction of preconditions and postconditions ensures that generated composition strategies are successful, and tailoring of solutions with software engineering techniques can tailor composition strategies for the needs of the engineer.

Thus far, our engineer has created a grammar detailing possible composition strategies, specified the preconditions and postconditions necessary to compose the new module, and executed SAGE to generate a set of optimal composition strategies. It seems that far more work has been incurred by setting up and running SAGE than would have been required to simply hand-code the composition. The benefit, however, is that SAGE can now be run for nearly any composition that the engineer may need to perform in the future. The defined grammar now forms a basis for any future compositions and can be easily extended to other domains that the engineer may encounter. Furthermore, SAGE can also automatically generate valid code in whichever language is required, enabling the engineer to simply copy and paste the generated composition strategy into the legacy framework.

For more information about Erik’s work, you can contact him at freder99 at msu dot edu.

Posted in BEACON Researchers at Work | Tagged , , , , | Comments Off

BEACON Announces Search for the John R. Koza Endowed Chair in Genetic Programming

A generous gift to BEACON and MSU by Dr. John R. Koza, the acknowledged founder of the field of genetic programming and author of four books on that subject, has endowed this chair, aimed at recruiting one of the leaders in the field as a new MSU faculty member and BEACON contributor. This endowed chair will help to build BEACON’s strength in evolutionary computation during its second five years as an NSF Science and Technology Center, and help to sustain BEACON after the STC funding is over. BEACON’s other endowed chair, the Koenig Chair, is held by Prof. Kalyanmoy Deb, an acknowledged leader in multiobjective evolutionary optimization, and we hope to fill the Koza Chair in GP with someone similarly distinguished in the field of GP. Together, these chairs will play an important role in strengthening BEACON’s long-term contributions to the field.

Full information about the position is available here.

BEACON’s leaders and members join in thanking Dr. John Koza for this marvelous sustaining gift!

Posted in Job Openings, Member Announcements | Tagged , , | Comments Off

BEACON Researchers at Work: Improving Search Quality in Genetic Programming

This week’s BEACON Researcher at Work blog post is by MSU graduate student Armand Burks.

About Me

PortraitAs a young “army brat,” I was always fascinated with learning how things worked. Trying to figure out how my toys worked, I often found myself amidst a pile of plastic pieces, wires, and motors, desperately trying to perform the magic trick of transforming those pieces back into one while my parents remained none the wiser. To this day, I am still not sure if I ever became more skilled at this trick or at making the toys disappear altogether. Either way, I became a better magician, and my interest in how things worked only grew.

It was this same fascination that led me to study Computer Science, as I could not only safely break things to understand them, but I could also create things from scratch. During my undergraduate studies at Alabama State University, I gained exposure to research through the Historically Black Colleges and Universities Undergraduate Program (HBCU-UP). This program ultimately led me to Michigan State University, where I first learned about Evolutionary Computation. From there, it was “love at first sight.” I was able to make things, break things, and let things evolve, all through the power of research!

My Current Research in Genetic Programming

My current research deals with combating premature convergence in Genetic Programming (GP). Before I delve into premature convergence, a brief summary of Genetic Programming is necessary. GP can be thought of as a special type evolutionary algorithm, where one of the main goals is to automatically create computer programs through evolutionary processes. GP evolves a population of computer programs, where programs are typically executed on an optimization problem and compared based on how close they are to solving that problem.

GP genotypeThe major difference between GP and most evolutionary algorithms is way in which the genotype (genetic makeup) of a program is represented in GP. In the most basic form of GP, genotypes are represented by a tree structure because it lends itself well to the creation of programs. As a concrete example, the figure at right shows the genotype of a program that encodes the mathematical expression: x2 – 1. When this tree’s genetic code is executed, the function nodes (* and -) operate on the terminal nodes (the input variable x and the constant value 1) to produce an output value. The evolutionary process breeds programs from the evolving population by combining their genetic material in order to discover new programs.

Premature Convergence in Genetic Programming

Premature convergence is one of the biggest problems in Genetic Programming, and evolutionary algorithms in general. To sum it up, premature convergence can be thought of as evolutionary stagnation. Since GP is often applied to optimization problems, one way to gain insight into the difficulty of such a problem for GP is to consider the enormity of the problem’s search space (the large number of possible computer programs that could be generated in attempt to solve the problem). Premature convergence takes place when the population quickly becomes so similar that the algorithm can no longer effectively explore the search space. At this point, it is often very difficult or even impossible for the population to improve in fitness (breed better programs). There are several reasons why this occurs, but the loss of genetic diversity is one of the most notable.

This is a particularly interesting problem in GP because of the tree-based genotype. Previous research has confirmed that not only do traditional GP populations very quickly lose genetic diversity in general, but a large contiguous portion of most of the trees become completely identical in a top-down fashion. This has a very profound and stifling impact on the effectiveness of finding solutions to difficult problems.

Combating Premature Convergence and Improving Search Quality

Fortunately, a lot of research has gone into combating premature convergence, and a lot of great strides have been made towards improving search quality. One example from the evolutionary computation literature is the Age-Layered Population Structure (ALPS). The main idea of ALPS is to use a special concept of age to divide the population into several layers. This allows new genetic material to be effectively inserted into the population and flow upwards from the bottom, while older genetic material evolves and improves as it makes its way towards the topmost layers. This helps to keep the population from becoming too genetically similar while it explores the search space. ALPS and other techniques have been successfully demonstrated in a number of problem domains.

Although there have been a lot of improvements that address premature convergence with varying degrees of success, I believe that there is still a lot of room to do better, and this is my current research focus. It is known that techniques designed to combat premature convergence often incur the cost of taking longer to find the optimal solution to a problem, although these approaches generally increase robustness (the reliability of finding optimal solutions). This is because these approaches avoid prematurely converging by aggressively exploring new areas of the very large search space instead of focusing in on one particular area. With this in mind, one of my research questions is: can we design robust algorithms that are capable of effectively avoiding premature convergence while still finding the optimal solution faster?

For more information about Armand’s work, you can contact him at burksarm at msu dot edu.

Posted in BEACON Researchers at Work | Tagged , , , , | Comments Off