BEACON Researchers at Work: Investigating the dynamics of diversification in chipmunks

This week’s BEACON Researchers at Work post is by University of Idaho graduate student Brice Sarver.

Photo of Brice SarverSpeciation, the set of processes through which new species arise, is one of the central areas of biological study.  It is easy, relatively speaking, to come up with models of how new species could arise, but it is much more complicated to validate these theories with data from natural systems.  Ideally, biologists want to develop models that 1) are supported by what we know about genetics thus far and 2) produce testable hypotheses that we can investigate using data from nature.

I became interested in speciation during my undergraduate career at Washington University in St. Louis, where I designed a study program focused on integrating philosophy, philosophy of science, and evolutionary biology.  This was a natural union, because speciation research draws from all of these fields.  This background, combined with a collaboration in fungal systematics with Dr. Kerry O’Donnell at the USDA’s Agricultural Research Services, was my impetus for pursuing an advanced degree in biology.

After graduation, I began to pursue a Ph.D. in Dr. Jack Sullivan’s lab at the University of Idaho. The Sullivan Lab uses chipmunks as a model system to test hypotheses related to speciation.  There are 25 species of chipmunks, 23 of which are located in western North America.  Chipmunk species are notoriously difficult to differentiate due to their similarity.  However, some morphological characters, such as the male genital bone (baculum), have proved instrumental in telling one species apart from the next.  Because of this, we can determine which species a particular chipmunk is when trapped.

Phylogenetic tree of chipmunks

Phylogenetic estimation of the relationships among chipmunk species. To the right of each name is a representation of their baculum, the male genital bone.

Two species of chipmunks were included as part of a Sullivan Lab phylogeographic survey of Pacific Northwest forests: the yellow pine chipmunk (Tamias amoenus) and the red-tailed chipmunk (Tamias ruficaudus).  Analysis of a portion of their mitochondrial DNA revealed something surprising: these two species were and are exchanging mitochondrial genes, and they are doing so frequently.  This phenomenon, called mitochondrial introgression, is common among hybridizing mammals.  Upon further analysis, it was discovered that these two species are the second-most distantly related among the 23 in western North America.  Even more interestingly, these species show a recurring pattern of asymmetrical introgression: mitochondrial DNA moves from one species (or a subspecies) into a different species (or subspecies), and not vice versa.  Additional samples provided by collaborator Dr. John Demboski at the Denver Museum of Nature and Science reveal that mitochondrial introgression is rampant among chipmunks in the Southern Rocky Mountains as well.  This system is composed of six species.  Two of these species are isolated from others (allopatric) and do not exchange genes; the other four experience rampant introgression, though it does not appear to be asymmetric.   These Southern Rocky Mountain species are also more closely related than the yellow pine and red-tailed chipmunks described above.

Introductory biology students are often taught that the presence of reproductive isolation can be used to separate one species from another.  Furthermore, the easiest and most often-taught way to think about new species arising is in allopatry: a population is split into two by some kind of barrier (say, a river), the two populations accumulate changes, and, ultimately, they are no longer able to produce offspring when they come back into contact.  Chipmunks have many well-characterized species despite being able to interbreed, and there is still movement of genes (gene flow) between species currently.  How can we reconcile these views?

Ongoing work in the speciation field includes formulating “divergence with gene flow” models.  These models attempt to explain diversification in the face of ongoing genetic exchange between speciating lineages; they focus on how divergence takes place across the genome.  One model, originally described by Wu (2001), is useful for thinking about speciation in this light.  We know from previous work dating back to the first half of the 20th century that some hybrids can perform poorly as the result of negative interactions among genes from different species (antagonistic epistasis).  As genomes diverge and one species begins to form two, small regions of epistatic incompatibility can arise.  As time progresses, these regions can expand to form larger regions of incompatibility that are difficult to break down.  As a result, the amount of gene flow between species begins to slow down until it stops.  The two species are now “good “ species in a traditional sense, unable to interbreed.

Model

An example of a divergence with gene flow model based upon Wu (2001). Examples of chipmunk species and subspecies that correspond to the four stages are to the right.

In order to look at how much introgression is taking place across the entire nuclear genome, we have to use more modern genomic techniques.  In collaboration with Dr. Jeffrey Good at the University of Montana, we are using targeted sequence capture techniques to determine the DNA sequence of thousands of genes across the genome in the Southern Rocky Mountains chipmunk system.  One goal of this study will be to assess how divergence in the nuclear genome takes place in light of rampant mitochondrial introgression.  In order to do this, we will look at thousands of single base changes in the DNA (single nucleotide polymorphisms, or SNPs) in order to track the quantity of genetic material being exchanged between species.  This will also allow us to look at the kinds of genes that are able to move between species easier than others.  We would expect that species that are more closely related would have higher rates of gene transfer than those that are more distantly related, since the divergence with gene flow model of speciation predicts that the amount of gene flow will decrease with the time since the species split.  Ultimately, this project, combined with others in my dissertation, will provide empirical support or refutation for current models of divergence with gene flow and provide insight into the process of how new species form.

For more information about Brice’s work, you can contact him at bsarver1337 at gmail dot com.

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

Third graders take action to save the striped hyena

Photo of third graders holding a "save the striped hyena" signRecently, MSU postdoc and BEACONite Aaron Wagner received a call from a group of third graders at Riverside Elementary School in Oneonta, New York, asking to talk with him about how to save the striped hyena. Their teacher, Mr. Ken Sider, explains:

During our social studies unit on Kenya, we read an article from a Kenyan newspaper about two children who found “kittens” on their way to their rural school between Mombasa and Tsavo National Park. They took the small animals to a game warden who identified the animals as striped hyena cubs, not kittens. This incident became big news in Kenya because the striped hyena is an endangered species. We then watched a news program about this story on KTN (Kenya Television News). The kids were immediately in love with the cubs.

Riverside Elementary School students skype with Dr. Aaron Wagner

At a class meeting, Jasmine asked if the striped hyena would still be alive when she is a grown up. No one knew the answer. This was the conversation that shifted our class’s attention to the plight of the striped hyena. The class immediately decided to do something to help. We split up into groups and did research. We expected to find an organization dedicated to protecting and saving the striped hyena, but we found none. We amassed a fine collection of facts and photographs, but no easy route to saving the hyena. I worked with a small group of third graders during our computer lab time to identify sources of support for our project. We happened upon a scientist named Dr. Aaron Wagner whose study of striped hyena social organization and ecology has secured his position as a striped hyena expert in the United States. Dr. Wagner’s article in the scientific, peer-reviewed journal Animal Behaviour, was a source of helpful information. We were able to read many parts and understand them! Additionally, Dr. Wagner has an informative website describing and illustrating his work. We studied his video clips of recordings of striped hyenas filmed during his field work in Kenya.

Save the striped hyena! (Click to enlarge)

Aaron spoke to the class over Skype and answered all of their questions about striped hyenas and the best way to help save them. They are now working to petition the Wildlife Conservation Society to devote resources and attention to saving this threatened species.

On December 8, the class took their Save the Striped Hyena! campaign to SUNY Oneonta, where they participated in the “Sounds of Africa” celebration, a festival dedicated to West African culture. The students got to see professional drummers and dancers, eat West African food, and meet many other students, teachers, and professors from our area. Before performing on their class set of djembes, the students handed out flyers with information about the striped hyena and asked people to contact the Wildlife Conservation Society for support. They carried their Save the Striped Hyena sign and waited impatiently for their turn to perform. The audience was very impressed by their 8-minute performance which included simple rhythms, call and response, two-part rhythms, West African beats, and a school cheer performed on drums. They were a hit in their striped hyena t-shirts.

The third graders have also worked to put together a “glog,” which is a kind of interactive poster, to help educate people about the striped hyena through a multidimensional, multidisciplinary, and multimedia experience. You can see the glog below, or click here to see the full size!

BEACON is very impressed by these students, and we are proud to help them in their educational and outreach efforts.

Posted in BEACON in the News | Tagged , | Leave a comment

BEACON Researchers at Work: Nutrition limitation's role in phytoplankton evolution

This week’s BEACON Researchers at Work blog post is by MSU graduate student Megan Larsen.

Photo of Megan LarsenWe all know that the world is more complex than the simplified systems and questions we use in laboratories. And yet, as scientists we have to ask these simplified questions in order to understand the more complex interactions in the natural world.

One of the qualities that most drew me to science, and particularly microbiology, was being able to strip a complex system down to its core, and then reassemble that puzzle with newly acquired pieces to provide a clearer view of the system. I started my scientific career in biochemistry at Nebraska Wesleyan University, learning the chemical structures of compounds involved in cellular processes such photosynthesis and metabolism.  While learning about these processes, I was also learning broad ecological concepts and theories about resource competition and predator-prey dynamics. Now, as a graduate student in Jay Lennon’s lab at the Kellogg Biological Station, my research centers on synthesizing each of the parts I learned as an undergraduate into a population and community context involving aquatic microbes. 

Within a given environment, species interactions result in complex interactions, often fueled by the local environmental nutrient conditions. Nutrient composition is one of the most important regulatory factors governing population and community assembly in nature. In many cases, microbial organisms mirror environmental conditions internally, thus the cellular stoichiometry or nutrient composition within the cell reflects that of the environment and strongly influences growth and reproduction. Furthermore, bacterial populations are constrained by phage predation (phage are basically viruses that infect bacteria). Unlike their bacterial hosts, however, infecting phage require a specific nutrient composition to reproduce. Therefore, nutrient limiting conditions also, albeit indirectly, reduce phage reproduction.

I am interested in a series of different questions that range from population ecology to molecular and genetic mechanisms of resistance in bacteria. The central focus of my dissertation rests on understanding how stoichiometry (the balance between the organisms and their resources in the environment) influences the ecological and evolutionary feedbacks in species interactions, specifically between phytoplankton, known as cyanobacteria, and their viruses. In order to address these questions, I have setup a model system with the planktonic bacteria known as Synechococcus and a T4-like phage. Synechococcus, a unicellular cyanobacteria ranging in size between 0.5 – 2 µm, can be found throughout the world’s aquatic ecosystems and plays an integral role in net primary productivity and global nutrient cycling. In order to study ecological and evolutionary feedbacks, I decided to work with these ecologically important organisms in long-term continuous cultures, or chemostats. This experimental system allows me to continuously monitor changing population densities and host-phage evolution through time.

Photo of flasksRecent work has shown that phosphorus limitation strongly impacts both bacterial ecology and evolution, likely due to its biological importance in nucleic acid synthesis. In phage, phosphorus limitation has been shown to reduce reproductive capacity, likely due to the inability to produce enough nucleic acid for each new progeny. In a comparative study contrasting the effects of nitrogen (N) and phosphorus (P) limitation (based on N:P stoichiometric ratios), I found that long-term population dynamics and evolution of both host and phage are highly influenced by the local stoichiometric conditions.  Population densities were strongly altered, impacting not only the patterns but also population stability through time with P-limited dynamics more stable than N-limited.

Photo of two flasksPhage resistance in this particular chemostat experiment was selected for rapidly (within 9 days of exposure), regardless of the nutrient treatment, but spread through the population at different rates between the different nutrient limited environments. Infectivity patterns, generated by challenging bacterial and phage isolates through time and across treatments, are also strongly tied to the population dynamics suggesting that rapid evolution of bacteria is stoichiometrically dependent. Bacterial resistance to phage is easily detected with challenge experiments where phage strains are added to a given bacterial strain to assess their infection ability. In my assays with 96 well plates, [seen here], I am able to determine when resistance to infecting phage developed simply based on color; when a bacterial strain is susceptible, cells are unable to grow and the wells remain clear as compared to a resistant strain which grows into a dense pink culture.

Photo of assay platesThe qualitative differences in the infectivity patterns suggest that bacterial isolates are likely developing context dependent resistance mechanisms. In order to elucidate these potential differences, I will be identifying the underlying genetic mutations associated with simultaneous adaptation to nutrient limiting conditions and phage predation with whole genome sequencing. In genomic studies of a closely related organism, Prochlorococcus, researchers have found the presence of genomic islands, pieces of rapidly mutating, non-conserved DNA sequences that confer both resistance and adaptation to phosphorus limiting conditions. It is possible that similar adaptations exist in Synechococcus which may explain the bacterial susceptibility differences between the nutrient treatments.

Collectively, these results demonstrate that ecological and rapid evolutionary feedbacks between bacteria and phage are context dependent, strongly regulated by the local nutrient environment in the laboratory. These patterns may also hold true in natural settings. Furthermore, these results suggest that species interactions in N- or P- limited environments, such as the Pacific and Atlantic Oceans, respectively, may be drastically different due to the stoichiometric conditions alone.  As predicted by recent mathematical theory, nutrient limitation can act as a stronger selective force than predation
by phage, but this is contingent on the identity of the limiting nutrient and its biological significance. When considering all the pieces to this puzzle, it is crucial to consider eco-evolutionary feedbacks, mediated by environmental nutrient stoichiometry, when explaining and predicting microbial populations. 

If you’re interested in the work I do or have questions, feel free to send me an email (larsenm9 at msu dot edu) or check out my website.

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

BEACON Researchers at Work: If Sticklebacks Could Talk…

This week’s BEACON Researchers at Work blog post is by MSU postdoc Liliana Lettieri.

“My what a red throat you have, and such a blue belly!  You’ve got some impressive dance moves, and you’ve built a nice nest.”

Photo of Liliana LettieriIf stickleback fishes could talk, these are some things that we might overhear females saying to males as they check out prospective mates.  As a postdoctoral researcher in Jenny Boughman’s lab, I try to uncover which characteristics, or traits, make males competitive among other males and sexy to females.  

Some of these traits are stylized behaviors that are meant to get the attention of females looking for a place to lay their eggs.  These behaviors may be under strong sexual selection; choosy females determine who is successful, thereby imparting an evolutionary advantage to males with certain traits. We call traits like these signals; they have evolved to influence the behavior of another individual. 

Signals are particularly interesting to me, because they determine the outcome of interactions between organisms when they are communicating to one another. An individuals’ environment is made up of the natural features in its surroundings – what we might call the abiotic components, like the light, temperature, currents, soils and minerals. It is also made up of other organisms, the biota.  Both abiotic and biotic interactions may shape how signals are transmitted and received. Signals may be very easy to detect in some environments, but, in other environments, they may not stand out enough against the background. This means that the signal may not have the same behavioral outcome in a different environment, or when the primary receivers of the signal have shifted.  Because the environmental background can be so important for signaling, researchers often explore environmental characteristics or constraints when trying understand how signals work. This is especially true when we see rapid or repeated evolution of signals; in these cases similar environments may promote the evolution of similar changes. For instance, in my graduate school research, I discovered that repeated shifts in bold stripe colors among cleaner goby fishes in the Caribbean may be an example of evolved signals that contrast best against a new habitat to signal to predators. These signals may have changed in response to strong selective pressure from the biotic factors in the environment, on a particular background – a great example of natural selection on signal evolution.

Photo of experimental tankSo, signals can be under strong natural selection to both minimize risk (avoiding predators) and maximize gain (attracting mates) in the backdrop of the environment. They can also be under strong sexual selection from females of their own species. This takes us back to the sticklebacks! Jason Keagy, another postdoc on team Boughman, and I are particularly interested in uncovering which traits, including signals, lead females to choose males in a novel freshwater environment (lakes formed after worldwide massive deglaciation around 10,000 years ago). Evolutionary biologists would like to know why and how because it may help us to understand the mechanisms underlying evolution with strong selection. Part of the key to uncovering which traits are important may lie in the fact that success can happen in stages, for example 1) establishing a territory, then 2) building a nest, then 3) attracting a female.  Different traits may have different costs and benefits at each stage.  In order to try to tease apart the importance of male traits in male competition versus female choice, we are using some different density treatments in large outdoor enclosures where males and females interact during the mating season (Figure 1).

Photo of sticklebackAnother really amazing part of stickleback evolution is that repeated instances of two species, occurring in pairs, have independently evolved in (estimated) 10,000 year old lakes; the two biologically similar forms that biologists call benthic (living near the bottom of the body of water) and limnetic (living in the open, well-lit areas of the body of water) species pairs occur in many, many lakes around the world. Females of both types in these lakes have strong preferences for suites of traits that help them choose a mate of their own kind. As they swim through breeding grounds, males of both species are building nests and signaling to attract females, who lay their eggs in the nest and leave the father to do all the parental care (Figure 2).  Because females’ senses and preferences have also diverged in the different environments in which they live (up in the water column versus down near the vegetation on the bottom), the species pairs have pretty strong reproductive isolation – meaning that they are very unlikely to mate with each other. In trying to understand the mechanisms of evolution in action, we hope to uncover some of the selective agents that drive species divergence. In other words, we want to know why certain traits are particularly good at attracting mates.

Diagram of QTL mappingWe also want to know something about the genetic regions that control these traits, and to do this we use an approach called quantitative trait loci mapping (Fig 3). In order to do this, we have to make hybrids between a species pair.  This method allows us to make a genetic mosaic between two genomes, each carrying sets of traits that best attract mates of their own kind. By asking females to choose among males with these patchworks of traits, we can measure the relative success of males with combinations of traits. We can then use genetic markers smattered across the genome to correlate parts of the genetic blueprint with certain traits, as well as with overall reproductive success.  If suites of traits and reproductive success (a proxy for fitness) map to the same regions, that will give us an additional clue pointing toward traits that may be of particular importance.  We are particularly interested in the potential importance of suites of traits because multiple pairs of limnetics and benthics differ in multiple traits, including shape, color, size, and behavior. Is the evolution of suites of traits, as opposed to just single traits, important for establishing reproductive isolation?  We think it might be and we hope to use these sticklebacks to help us answer this question.  They can’t talk, but they can certainly tell us a lot about evolution in action!

For more information about Liliana’s work, contact her at lettieri at msu
dot edu.

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

BEACON Researchers at Work: Professional Scientist, Amateur Ambassador

This week’s BEACON Researchers at Work post is by MSU graduate student Rosangela Canino-Koning. 

Photo of Rosangela Canino-Koning“You study evolution? Oh, I don’t believe in that.”

Virtually every new graduate student has experienced that flash of panic when confronted by a well-meaning relative, asking that dreaded question, “What do you do?” Even if your topic of interest isn’t particularly specialized (and whose isn’t?), formulating a non-technical “elevator pitch” can be a daunting task. And when you start that pitch with, “I study evolution,” things can get dicey pretty quickly.

When we first start our research, our advisors, professors, and colleagues go to great lengths to paint a realistic picture of what a career in science entails. The long nights, the continual struggle with writer’s block, and the endless dry periods between epiphanies are described in exhaustive detail. Our teachers continually remind us that science is a game of bashing your head against a wall until you break through, and then running headlong right into the next wall. Jobs are few, failure is the norm, and success the exception, etc., etc.

But what they don’t tell us is that by accepting this path, we, for better or worse, become ambassadors for science. We become the face of scientific research to friends and family who may not have any other exposure to it. No matter how obscure your field, no matter how tiny your journal reading list, you still must find a way to explain to your mom what you learned this week.

Communication between scientists in the same field can be very difficult. Much more so is communication between scientists and non-scientists, where there is potentially a very large gap in terminology and education. For the study of evolution, the difficulty is multiplied by the fact that there are many people who misunderstand, or simply do not believe in, what we do. This can make the prospect of discussing our research with our families so terrifying that we carefully avoid the subject altogether rather than risk stepping on a conversational landmine. In the process, we miss a great opportunity to de-mystify our work.

Schematic comparing order of genes in two genomes

My research could be charitably described as esoteric. I study the effects of fluctuating environments on the genetic structures of self-replicating evolving computer programs. In particular, I test hypotheses about the kinds of genetic structures that evolve when the environment changes in cycles, and whether those structural changes promote faster evolution of new traits.  

In practice, this means that I spend a lot of time in front of the computer staring off into space with a blank document in front of me. On a good day, that document ends the day filled with notes and ideas for experiments, analysis of my results, and plans for what to do tomorrow. On a bad day, the page ends up filled with expressions of frustration with computer resources on the fritz, or painstakingly generated graphs that show no results. On the worst days, the document stays empty because nothing worthwhile got done.

But on the very best days, when I generate a figure that will form the basis of a new paper, or arrive at a new insight about a troublesome problem that I’ve been wrestling with, those are the days that make it all worthwhile. Those are the days that I achieve, in my own small way, the primary goal of science, which is finding out the truth about the world.

Scientists may study the mysteries of the universe, but we don’t need to be mysterious ourselves. My work is challenging, frustrating, and rewarding, just like any other line of work. I am highly trained, but so is a medical doctor, a lawyer, or an engineer. We aren’t all that different, and we all want the same things.

I suspect that many of our difficulties with communicating science to the public are self-inflicted. The stereotype of the scientist as white-robed scholar-priest continues to be perpetuated because we like how it fits. We like holding ourselves at a distance. This distance comforts us and reassures us that we are special, that we are smarter, and better than everyone else.

This comforting distance is what leads the public to call us elitist, and allows the opponents of reason to attack science with impunity. It is what allows the Anti-Vaccine, Global Warming Denial, and Creationist movements to flourish.

We can fight back by simply sharing our research more openly with our families and friends. The public’s image of scientists is already pretty battered, but a caricature can never stand up against a real breathing person. Sure, there may be a few uncomfortable moments during those first few conversations, but enthusiasm is infectious, and in the end, one person at a time, we can change people’s perceptions of who scientists are, and what it is that we are actually trying to do here.

For more information about Rosangela’s work, you can contact her at caninoko at msu dot edu.

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

BEACON scientists show how new viruses can evolve and become deadly

In the current issue of Science, researchers at Michigan State University demonstrate how a new virus evolves, which sheds light on how easy it can be for diseases to gain dangerous mutations.

Photo of Justin Meyer and Devin Dobias

Justin Meyer (right), MSU graduate student, led a team of researchers, including Devin Dobias, former MSU undergraduate student, that showed how new viruses evolve. Photo by G.L. Kohuth.

The scientists showed for the first time how the virus called “Lambda” evolved to find a new way to attack host cells, an innovation that took four mutations to accomplish. This virus infects bacteria, in particular the common E. coli bacterium. Lambda isn’t dangerous to humans, but this research demonstrated how viruses evolve complex and potentially deadly new traits, said Justin Meyer, MSU graduate student, who co-authored the paper with Richard Lenski, MSU Hannah Distinguished Professor of Microbiology and Molecular Genetics.

“We were surprised at first to see Lambda evolve this new function, this ability to attack and enter the cell through a new receptor – and it happened so fast,” Meyer said. “But when we re-ran the evolution experiment, we saw the same thing happen over and over.”

Diagram of OmpF protein

Ribbon diagram of the OmpF protein, Lambda's new pathway into E. coli.

This paper follows recent news that scientists in the United States and the Netherlands produced a deadly version of bird flu. Even though bird flu is a mere five mutations away from becoming transmissible between humans, it’s highly unlikely the virus could naturally obtain all of the beneficial mutations all at once. However, it might evolve sequentially, gaining benefits one-by-one, if conditions are favorable at each step, he added.

Through research conducted at BEACON, MSU’s National Science Foundation Center for the Study of Evolution in Action, Meyer and his colleagues’ ability to duplicate the results implied that adaptation by natural selection, or survival of the fittest, had an important role in the virus’ evolution.

When the genomes of the adaptable virus were sequenced, they always had four mutations in common. The viruses that didn’t evolve the new way of entering cells had some of the four mutations but never all four together, said Meyer, who holds the Barnett Rosenberg Fellowship in MSU’s College of Natural Science.

“In other words, natural selection promoted the virus’ evolution because the mutations helped them use both their old and new attacks,” Meyer said. “The finding raises questions of whether the five bird flu mutations may also have multiple functions, and could they evolve naturally?”

Meyer, J. R., D. T. Dobias, J. S. Weitz, J. E. Barrick, R. T. Quick, R. E. Lenski. 2012. Repeatability and contingency in the evolution of a key innovation in phage lambda. Science 335: 428-432.

Supplementary material: listen to the Science podcast featuring an interview with Justin Meyer about this work.

See also Carl Zimmer’s article on this paper in the New York Times, and an article in The Scientist magazine!

 

Posted in BEACON in the News | Tagged , , | Leave a comment

BEACON Researchers at Work: Developing interactive evolutionary computation for machine learning games

This week’s BEACON Researchers at Work post is by University of Texas at Austin graduate student Igor Karpov.

Photo of Igor Karpov

Igor with a pair of traditional Komi fur skis

When thinking about parts of my work that are most relevant to BEACON, several topics come to mind simultaneously. To avoid making the hard choice myself, I will briefly describe all of them, and leave the choice of what is interesting to follow up on to the reader.

The unifying theme for the projects described below is that I use of and extend evolutionary computation methods in the context of a popular and complex domain – video and computer games. The domain has several properties that make it an interesting subject of study from the perspective of artificial intelligence. First, the variety of game genres and complexities allows for a gradient of increasingly complex behaviors and adaptation approaches to be developed. Secondly, game engines have developed a good balance of complex environments and behaviors with reasonable amounts of computation and simulation speed. Finally, and perhaps most importantly, the game domain has plenty of human participation. This means both that the domain itself is interesting and challenging enough to hold our attention, and that we can study how our state-of-the-art autonomous agents do when they are interacting with human-level intelligence in its various forms.

Bar graph

The relative ability of bots and human players to pass for human players in the Botprize competition.

3D line graph

An example of the data collected from human games in the Botprize domain.

One of the most complex such domains that I will talk about is the Botprize competition. The goal of this competition is to develop a software player for a state of the art first-person game (Unreal Tournament 2004 in our case) that is behaviorally indistinguishable from a human player. To be more concrete, we have to design a bot that will fool the human players it interacts with into labeling it as a human about as often as another human player is able to do so.

To address this challenge, I have worked with a fellow BEACON researcher and UT Austin graduate student Jacob Schrum (who works on multi-objective evolution of neural network controllers for game domains) and our advisor Risto Miikkulainen, to develop UT2, a game bot that participated in the Botprize competition several times, and placed 2nd in 2010. The overall system is complex and includes a scripted behavior architecture, a module used in combat and evolved by multi-objective constructive evolution of artificial neural networks, and a module that is responsible for human-like movement that is based on playback of human examples (Believable Bot Navigation via Playback of Human Traces). The area is ripe for future work, including imitation learning from human behavior and ways of combining imitation with evolution of autonomous behaviors.

Diagram

A schematic diagram explaining the human-assisted neuroevolution method. Three types of human input (advice, example traces and task shaping) are combined with an evolving population of artificial neural networks to produce desired solutions faster.

The second project that I have worked on together with Vinod Valsalam and Risto Miikkulainen, sets out to study exactly the ways in which human users can harness machine learning methods such as neuroevolution. In this human subject study, we compare manual design of game behavior and unassisted evolution of neural networks against three different types of human-assisted, interactive neuroevolution, namely evolution in the presence of task shaping, evolution with the addition of advice, and evolution with learning from examples (see Human-Assisted Neuroevolution through Shaping, Advice and Examples).

3 line graphs

Relative time to solve the three design tasks manually, by evolving solutions automatically, and with human assistance.

Our results indicate that while the unassisted neuroevolution is a powerful game behavior design tool and outperforms manual design significantly, it can be greatly improved with the correct application of an interactive human assistance method. Further, the type of human assistance that works best depends on the task, leading to a hope of developing hybrid methods that combine the strengths of human input and of machine evolution automatically.

Screen capture of a maze from OpenNEROFinally, I will touch on a substantial open source software development project I am leading. The software is called OpenNERO: game platform for AI research and education. It is a system that includes several different game-like mods that are unified by an AI framework and support neuroevolution, reinforcement learning, search methods, planning, and potentially many others. While a description of the entire system is beyond the scope of this post, I encourage the reader to checkout our website at opennero.googlecode.com, and see some of the educational and research demos we have made available.

Color matrix

A color matrix representation of score differences in the OpenNERO round robin tournament. Rows and columns of the matrix are the red and blue team playing the match respectively. Redder colors mean more decisive victory for the red team and bluer colors mean more decisive victory for the blue team. Teams are ordered according to their average score across all matches played.

One of the most recent ways in which we have used the OpenNERO platform was to run the 2011 OpenNERO Tournament. This tournament, which was run as part of Stanford University’s online Introduction to Artificial Intelligence course, invited students to evolve and/or train behaviors for an RTS-like game, where their teams would compete with other submissions for the right to be called “strongest in the field.” We received 156 submissions and ran a round-robin tournament, resulting in a detailed analysis of behavior diversity and other characteristics. The infrastructure developed for parallel evaluation of games and for analysis and visualization of tournament results gives us confidence that this type of a competition can be run with a much larger number of participants, and can potentially even be used to drive the process of evolution of novel behaviors itself.

For more information about Igor’s work, you can contact him at ikarpov at cs dot utexas dot edu.

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

BEACON Researchers at Work: Studying the evolution of sociality with real and digital hyenas

This week’s BEACON Researchers at Work blog post is by MSU postdoc Aaron Wagner.

The evolution of sociality is one of the most fascinating and productive topics in evolutionary biology. Though it is often very useful to look to social species to understand the current function, costs, benefits, and circumstances of cooperative relationships, current observable social behaviors may not reflect the selective pressures that led to their initial evolution. Instead, the observed benefits of a social strategy may be a consequence of that strategy, not the force that initially favored its evolution. For example, social grouping in carnivores is often explained as a way to increase hunting success via pack hunting. However, in many carnivores, social group size is larger than hunting group size (e.g. lions Panthera leo or spotted hyenas Crocuta crocuta), so any foraging benefits may be an effect, not a cause, of grouping.

Model of the effect of resource dispersion on the evolution of sociality

How resource conditions (bottom) can determine if solitary living (top right) or sociality (top left) evolves.

Simple spatial groups can form through a passive process when the costs of tolerating others drop below the costs of sharing space (such as a territory). The difference between these costs is largely determined by availability of resources: when the resources in an animal’s range exceeds its needs, there is little or no cost to sharing the range, tolerance can develop, and spatial groups can form even in the absence of any benefits. Once simple groups have formed, natural selection can then act to promote the evolution of cooperative strategies and the realization of any associated social benefits. This broad construct (excess resources -> tolerance -> aggregation -> stability -> social benefits) sets the stage for developing and testing predictions about the role of resource availability and distributions in the evolution of sociality. Because simple groups must exist prior to the evolution of more complex social organizations, a fundamental part of my research focuses on uncovering the conditions that permit, promote, or preclude the evolution of simple grouping strategies and the persistence of groups.

Within the carnivores, sociality is extremely rare: 85% of carnivore species are considered solitary. For many good reasons, the vast majority of carnivore behavioral ecology research has focused on the social minority. However, several recent studies of species from the solitary majority have unveiled intriguing variations in grouping strategies and behaviors across populations. In particular, temporary groups sometimes form in these ‘solitary’ animals when resource conditions can support them. Within these groups, cooperation and social behaviors are often limited and primitive and, in the absence of active benefits to grouping, the groups themselves are often unstable. Among these ‘incipiently social’ species is the striped hyena (Hyaena hyaena), which I had the pleasure of studying for many years in Kenya.

Photo of striped hyenas

A mother greets her nephew at her new-born cub’s den.

Before we began working with striped hyenas, they were routinely described as being strictly solitary. However, we discovered that this was not always the case. At our first site, while they almost never interacted, males were willing to share ranges while females were strictly solitary. At the second site where resources were more plentiful, males were strictly solitary but some females shared ranges with other females and often interacted with each other’s cubs at dens. Studies like this, where differences in non- or minimally-cooperative grouping strategies can be compared with differences in resource conditions, provide glimpses of the earliest stages of social evolution and hints about the constraints that were “breached” to permit the evolution of far more complex forms of sociality, like that found in the highly gregarious (and über complex) spotted hyena.

While our work with the striped hyena was enlightening (and an experience I wouldn’t trade for most anything), significant questions remain. For instance: Are permissive conditions sufficient to maintain group stability? Is group stability necessary and sufficient for the evolution of sociality? And what types of modifications in resource conditions explain variations in social strategies, including the conditions that favor immigration (moving to a new group) over philopatry (staying in the same group you were born in) as a means of group formation and maintenance? While it may be possible to address these questions via additional field studies, I have taken a very different approach… following a fairly dizzying left turn into Charles Ofria’s Digital Evolution Lab.

What first brought me to the ‘Devolab’ was an encounter with a description of the digital evolution platform Avida that Charles, his colleagues, and students have developed for and applied toward studying an impressive array of fundamental questions in evolutionary biology. When I first read about Avida, I was instantly convinced that this platform was ideal for addressing questions about the pressures and patterns underlying the evolution of tolerance, group formation, and social cooperation. In a broad sense, Avida seemed perfect for evolving ‘digital hyenas’ or, alternatively, for uncovering the conditions that lead to the evolution of carnivore-like grouping, proto-social, and social behaviors.

While cooperative behaviors have evolved in ‘avidian’ populations in the past, this occurred under conditions in which grouping was a given. That is, organisms were placed into groups, they were not ‘asked’ to form their own groups first. This was also not done in a spatial context whereby groups have physical ranges or territories in the digital world encompassing locally accessible patches of resources. My work seeks to examine exactly that process: starting with a solitary population, what distributions of resources drive the population to evolve ranging behaviors and to either defend that range as a territory or to tolerate one another’s presence?

While it is obvious to us now, having come from working with a large and complex animal that has already evolved to do it, what we did not anticipate was that in order for the organisms to ever evolve such ranging and grouping behaviors, they would also need to evolve the skills to intelligently move and navigate through their environment. Hyenas already do that… it’s something taken for granted in the field and never thought about. Since coming to BEACON, I think about it a lot! Because having intelligent and flexible navigators is so critical for addressing our original goals, much of our efforts have focused on looking at what aspects of the environment drive organisms toward evolving navigation in the first place (compared to not moving at all, or just happily running around like crazed chickens… both of which they

are often quite content to do) and toward evolving use and control of sensors.

The 5 major steps in our approach toward evolving digital hyenas.

As it turns out, starting with a simple, non-moving, and blind ancestor and evolving intelligent navigation in an open ended environment like Avida is far from simple. However, we have succeeded in doing just that. We began with various environments in which the organisms were required to navigate out to a food resource and return to the nest on which they were born. The three biggest challenges that we had to overcome here were to uncover 1) the specific characteristics of the environment that would pressure the avidians to travel far from the nest, 2) the characteristics that would create pressures to evolve away from random movement, and 3) the conditions that would prevent the evolution of fixed ‘blind’ strategies. For the last one, the solution was to put the food resources in motion. For the first two, competition resulting from resource depletion and crowding does the trick: organisms suffer if they all try to feed from the same food resource, because the food runs out. Thus, they are driven to find resources farther from the nest, but the evolution of intelligent sensor use becomes more critical the farther out the organisms travel.

Avidians evolved abilities to detect distant food resources (small greys) moving in fixed orbits, navigate to and feed from them, and return home to reproduce at a central nest (large grey). Organism colors reflect the food resource the organisms are seeking or have fed from. Food resources appear speckled as the organisms deplete them. In this experiment, unlike the food resources, the central nest is not visible from long distances. The organisms here have compensated for this by using the (visible) closest orbiting resource as a landmark from which they search for the nest (note the streams of organisms heading to that lowest orbit resource, but that it is not being depleted). The noisy clouds around the food resources are a partial consequence of crowding… there are fewer cells on the resources than organisms trying to feed from them.

Once the avidians demonstrated an evolved ability to control and use their sensors and to navigate across large distances, we added a new twist to their lives: we allowed avidians to eat other avidians. In other words, we allowed for the evolution of predators from the prey population. With the same sensor capacities as before, avidians almost immediately evolved successful predation strategies in stable predator-prey populations.


Prey (greens) ‘blooms’ occur in response to seasonal shifts in resource (black) abundance and location. Greyed resources are out of season and are below the minimum the prey need to feed.  Evolved from the prey, not introduced, predators (red) have adapted their sensors for use in locating prey and rapidly swarm in response to prey blooms.

Our next step is to tie these successes together with other non-spatial work in which avidians evolved abilities for territory defense as a response to local resource availability and competition. The primary hurdle here will be to evolve territory establishment and fidelity by the predators. In the process, we will ultimately be able to test the suite of hypotheses we originally targeted. Namely, under what resource conditions do predators establish ranges and alter their levels of tolerance toward conspecifics. Undoubtedly, as always, we will be learning as much about the intricacies of evolution from the development process itself as we do from the results of the final experiments…but that’s half the fun of it all!

For more information about Aaron’s work, you can contact him at apwagner at msu dot edu, or visit his website.

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

BEACON Top-Up Recruiting Fellowships at MSU

Call for Nominations
New Graduate Student
BEACON Top-Up Recruiting Fellowships

Sponsored by
The BEACON Center for the Study of Evolution in Action
An NSF Science and Technology Center
 

One goal of BEACON is to initiate and support research and training activities that involve the study of actively evolving systems and evolutionary dynamics, as well as applying these principles to solve tough computational or engineering problems.  Furthermore, BEACON aims to recruit a diverse student population.  To promote these goals, BEACON will be providing BEACON Top-Up Recruiting Fellowships to attract promising new Ph.D. students interested in this area to attend Michigan State University, funded by the University.

Eligibility: Top-Up Recruiting Fellowships can be used to support applicants to Ph.D. programs in all departments at MSU that conduct research in this area, with preference given to applicants who are citizens or permanent residents of the US.  Any applicant nominated for a Top-Up Recruiting Fellowship must be nominated by a BEACON faculty member. In addition, the applicant must receive a 5-year support commitment from the faculty member and/or department, university or external agency (NSF, etc.). BEACON strongly encourages faculty to nominate women, students from underrepresented minorities, and persons with disabilities.

Top-Up Recruiting Fellowship Details: If an applicant is awarded a BEACON Top-Up Recruiting Fellowship, they will receive between $3,000 and $5,000 in additionalfellowship funds for each year they participate in BEACON activities, for up to a maximum of five years. If the applicant receives an NSF or other similar fellowship already providing $30,000 or more in annual support, BEACON will offer a one-time fellowship supplement of $5,000 for the duration of that fellowship.

Requirements: Students receiving this fellowship will be required to take two BEACON-related courses during their first year: one course on either evolutionary biology or computational evolution (whichever is not part of the student’s background) during Fall Semester 2012, and one project course where students work in interdisciplinary groups during Spring Semester 2013. This requirement is to support BEACON’s goal of encouraging students to pursue multi-disciplinary research.  These courses are normally included in the student’s academic program.

Application Process:  To nominate an applicant, please email the student’s application packet to Eric Torng (torng@msu.edu) by February 7, 2012.  Please add the following two items:

  1. A letter of nomination from the prospective advisor.  This letter should describe briefly the research area in which the student is expected to work and how this is connected to BEACON. Please highlight any multidisciplinary aspects of the research.  If the research will involve any of the BEACON partner universities, that should be stated. 
  2. If the candidate is a woman, member of an underrepresented minority, or a person with a disability, note that fact on the application for reporting to the NSF.

Decisions will be made within a week following the announcement of UDF/UEF recipients.

Posted in About BEACON | Tagged , | Leave a comment

BEACON Researchers at Work: Improving Biometric Security with Evolutionary Algorithms

This week’s BEACON Researchers at Work post is by North Carolina A&T State University graduate student Aniesha Alford.

Photo of Aniesha

We all remember the events that occurred on September 11, 2001. I was a sophomore in high school, and I can still vividly recall watching the news along with my classmates as the events unfolded. Since that day, measures are continuously being taken to avoid similar tragedies. One preventive measure is a more secure identification process, specifically via the use of biometric recognition. To date, biometric recognition systems are currently used by a number of commercial and government organizations. However, there is always room for improvement. I perform research with the Center for Advanced Studies in Identity Sciences (CASIS), and my research is in a new field of study that we call Genetic and Evolutionary Biometrics (GEB). GEB is devoted to the discovery, design, and analysis of evolution-based methods for solving traditional problems within the field of biometrics. My research, in particular, focuses on the development of GEB applications to improve the performance of facial and periocular (i.e. the area around the eyes) biometric recognition.

Biometric recognition involves the use of distinct physical, chemical, and/or behavioral characteristics for automatic recognition of an individual. Examples of such biometric characteristics (also known as modalities) include the face, fingerprint, voice, and signatures. These recognition systems typically work by first using a sensor (such as a camera) to acquire a biometric sample. The newly acquired sample is then passed to a feature extractor which transforms the acquired sample into a set of unique features referred to as a feature template. Often, feature selection techniques are then applied to reduce the dimensionality of the resulting feature templates. Next, the reduced template is compared to those previously enrolled (stored) in a database. The similarity between the recently acquired and enrolled templates are then measured and used to make a decision (accept/reject an individual).

Flowchart of a typical biometric systemIn the biometrics community, feature selection techniques have typically focused on retaining the most salient individual features (i.e. the most variant individual dimensions, the most consistent individual features, or the most discriminative individual features). However, my research proposes the use of GECs to: (a) evolve subsets of the most salient combinations of features and/or (b) weight features based on their discriminatory ability in an effort to increase accuracy while decreasing the overall number of features needed for recognition.

Three techniques have been developed and applied for facial and periocular recognition: Genetic & Evolutionary Feature Selection (GEFeS), Weighting (GEFeW), and Weighting/Selection (GEFeWS). GEFeS reduces the number of features used by evolving a feature mask (FM) that discards features that do not aid in increasing the recognition accuracy. On the contrary, GEFeW evolves a weight for each feature within a feature template based on its relevance. Our final technique, GEFeWS, is a hybrid of GEFeS and GEFeW. GEFeWS evolves a FM that discards those features that are not relevant and weights those features which are.

To test the effectiveness of these techniques, images were selected from the Face Recognition Grand Challenge (FRGC) database. Two feature extraction techniques were then applied to the facial and periocular images: the Eigenface method and the Local Binary Patterns (LBP) method. The Eigenface method, which is based on Principle Component Analysis, is a statistical dimensionality reduction technique that is used to extract only those dimensions that are necessary to efficiently distinguish images of individuals. The LBP method is a texture analysis technique which works by first segmenting an image into a grid of evenly sized regions (referred to as patches) and then analyzing the intensity changes of the pixels within each patch. GEFeS, GEFeW, and GEFeWS were then used to evolve FMs for the face-only, periocular-only, and face + periocular feature templates. The performances of these techniques were compared to performance of the feature templates without the use of GECs.

Our results showed that by fusing the periocular biometric with the face, we could achieve higher recognition accuracies than using the two biometric modalities independently. In addition, the LBP feature templates outperformed the Eigenface templates. Our results also showed that our GECs were able to achieve higher recognition rates than the baseline methods (i.e. the feature templates without the use of GECs), while using significantly fewer features. Of the three techniques, GEFeWS performed best, using less than 50% of the extracted features to achieve higher accuracies than GEFeS and GEFeW alone.

In conclusion, I am very excited about our research. It is great to be one of the pioneers in this new field of study, but it is even greater to think that one day our research could be implemented to make biometric security processes more accurate, faster, and more efficient. In addition, the potential that similar techniques may have in other areas of study are astounding. By presenting my research at conferences, I have been approached by several individuals interested in applying similar techniques to their research (i.e. tomato classification). I look forward to seeing how the skills I have gained through this research will come into play in the future. The possibilities seem endless and I believe that BEACON has prepared me for the challenge!

For more information about Aniesha’s research, you can contact her at aalford at ncat dot edu.

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