Bench Press

Computer-in-a-petri-dish?

So much is made about man vs machine in science fiction, that maybe we’ve neglected to pay attention to the entity which may trump us both: bacteria. A team of US Researchers have recently published an article in the Journal of Biological Engineering that suggests an innovative use of synthetic biology to perform complex computations.

Consider a classical computer science problem: the Hamiltonian Path. Imagine that you’re a tourist, and you have a map of all the cities you wish to visit along with all the roads which connect those cities. Finding a Hamiltonian Path, in this case, would mean traveling to each city you want to visit without having to go through any city more than once. While this may seem like simple map work, computer scientists have so far been unable to find a way of efficiently finding a Hamiltonian Path that does not go through an exhaustive list of paths.

However, a team of scientists from across four academic institutions (Missouri Western State University, Davidson College, North Carolina Central University, and Johnson C. Smith University) have cleverly engineered a solution using Escherichia coli bacteria to solve a basic form of the Hamiltonian Path with only three cities.

The cities were represented by a combination of genes causing the bacteria to glow red or green, and the possible routes between the cities were explored by the random shuffling of DNA. Bacteria producing the correct answer glowed both colours, turning them yellow.

The magic behind the bacterial solution is that, through sheer brute force made possible by bacterial exponential multiplication, the bacteria can explore a wide range of possible solutions to the Hamiltonian Path Problem in parallel! 1000 bacteria = 1000 test runs! So, if the Hamiltonian Path Problem is harder than you expect, then simply let the bacteria divide. If they divide three more times, you’ll have increased the “computational” power available to you by a factor of 8!

But what makes the Hamiltonian Path Problem so interesting? If you’re a computer science buff, you’d know that the Hamiltonian Path is classified as NP complete, something which describes the most difficult search problems out there. More formally, an NP complete problem is a search problem that has an answer that can be checked/verified in a quick and efficient manner, but, as far as we know, does not have a quick and efficient way to solve. Given this very precise and esoteric definition, you would think the number of NP complete problems would be very limited. In actuality, NP complete problems show up everywhere. These problems range from esoteric ones like the Knight’s tour problem, the Travelling salesman problem, to challenging scheduling and traffic routing questions in telecommunications networks and multicore processors, and even to games like Sudoku and Battleship! (A list of some of the more well-known NP complete problems is listed on this Wikipedia page)

What makes this particular result even more interesting is the fact that NP complete problems are reducible to each and every other NP complete problem. In other words, a method that can quickly and efficiently solve one NP complete problem can be used to solve every other NP complete problem quickly and efficiently as well. In a sense, all NP complete problems are inherently the same problem. Thus, creating a bacterial solution to solving one NP complete problem provides a potential path to solve every other NP complete problem, proving that synthetic biology can do a whole lot more than just simple biological circuits, they may even provide an interesting tool to solve some of the most challenging computational problems.

So perhaps the judgment day the Terminator series envisioned won’t originate from Cyberdyne, but from a synthetic biology lab experimenting with some “smart” bacteria. I’ll be keeping my eyes open.

(Image Credit)

Who said giant subatomic particles and giant microbes had a monopoly on plush cuteness? I Heart Guts shows you that plush organs can be just as cute:

That would be a heart (on the left), lungs (on the top), kidney (in the middle), and liver saying hello from what looks like a location in Japan.

And there are more adorable creations! They include: intestines, spleen, stomach, bladder, brain, pancreas, gallbladder, uterus, and even a special faux leather “black heart”!

What does this have to do with technology and science? Well, I found these on the Internet after all… okay its a stretch. But, after all, how can you not *lung* these guys (yes, they also sell organ-inspired T-shirts)?

(Images all from I Heart Guts website)

As technology continues to advance the ubiquitous nature of certain devices prompts innovative people to come up with amazing new uses for everyday items. A perfect example of this is the cell phone. We’ve already shown you smartphones that can take and record ultrasound images as well as a nifty Android application that makes stargazing easy for the amateur astronomer in all of us. Now a team led by Dr. Daniel Fletcher at UC Berkeley in collaboration with researchers at UCSF have turned the smartphone into an incredibly effective microscopy device.

Light microscopy is a vital tool for the diagnosis and screening of various diseases. Unfortunately in many regions of the world access is limited due to availability or lack of portability. Dr. Fletcher’s group looked to solve this problem by taking off the shelf components and building a solution that would be cheap and effective. Fletcher’s group built a mobile-phone mounted light microscope, dubbed the CellScope, capable of providing images detailed enough to help diagnose diseases like malaria and tuberculosis. Using a mobile phone as the platform for the microscope also allows images to be saved and transmitted to clinical experts for further analysis.

The CellScope was put through it’s paces by Dr. Fletcher’s team as they tested it in various applications. As seen in the figure below sickle shaped red blood cells are clearly visible within the image of a blood smear sample allowing the diagnosis of malaria.

In addition to taking diagnostically clear images of blood smears, Dr. Fletcher’s group tested the CellScope with fluorescent filters to see if the CellScope could be utilized in an increasingly popular tuberculosis screening and monitoring assay.

As seen above the fluorescent staining of tuberculosis bacilli in spittum is remarkably clear for a microscope attachment on a mobile phone. In the C panel of the above figure, Dr. Fletcher’s group also attempted to harness the computational power of the mobile phone by developing software to automatically count and process the fluorescent image.

The CellScope’s effectiveness, portability, and low cost make it an incredible tool for health care providers throughout the world. More details available at PLoS ONE.

(PLoS ONE: Mobile Phone Based Clinical Microscopy for Global Health Applications)

We’ve mentioned before the power of Cloud Computing as a means of expanding the computational power in the hands of researchers and scientists (by “outsourcing” it to someone with excess computing capacity like Amazon or Google), such as those at CERN studying high-energy particle physics. So, it was very heartwarming to see a Chemical & Engineering News cover story on the use of new cloud computing systems by large biotech/pharmaceutical companies like Genentech, Pfizer, and Eli Lilly.

Lilly has demonstrated the viability of cloud computing in pharmaceutical R&D, according to Dave Powers, the firm’s associate information consultant for discovery IT. "We were recently able to launch a 64-machine cluster computer working on bioinformatics sequence information, complete the work, and shut it down in 20 minutes," he says, describing a project the firm executed using Amazon’s Elastic Compute Cloud (EC2) service. "It cost $6.40. To do that internally—to go from nothing to getting a 64-machine cluster installed and qualified—is a 12-week process."

What was most interesting about the article was the assessment of the cost/benefit analysis that the companies each went through before adopting the technology, something which is important to understand both for researchers/companies interested in adopting cloud computing techniques as well as for technologists/developers striving for broad adoption of their own special technologies. This particular case is especially enlightening as it flips the conventional wisdom – who said that all pharma IT systems and managers are slow to embrace change?

There are 4 key factors that seemed to play a role in “tipping” the large bio/pharma companies: (1) cost, (2) maturity, (3) third parties, and (4) the ability to achieve sizable benefits on a number of scales.

1. Cost: This is usually the “easy” part of new technologies. After all, if a technology is being considered as an alternative to conventional approaches, it usually has major cost or efficiency advantages. In this case, Cloud promoters/IT experts were able to make the case that the cost of buying, setting up, qualifying, and supporting IT infrastructure needed to support all internal demand for computing resources was much greater than the cost of outsourcing some computing needs to Cloud Computing providers. This cost, of course, is measured not only in terms of IT dollars spent,  but also in terms of the time needed to set up, qualify, and develop the necessary IT infrastructure as well as the potential dollars a company might lose by being less nimble.
2. Maturity: One of the major obstacles that new technologies face is that nobody trusts them. After all, why trust a new player with an unproven product for your ultra-important needs (especially when your job is on the line if your needs aren’t fulfilled), when your current setup is working “good enough”? In the case of Cloud Computing, however, the availability of well-known vendors (Microsoft, Google, Amazon, Rackspace, etc) who have had years of experience developing their own systems and product offering has been instrumental in wearing down the traditional resistance that new technologies tend to face. Amazon, especially, has built a well-known cloud platform (their Elastic Compute Cloud more commonly referred to as EC2), with:
   • Easy-to-use web interface
   • Range of offerings that are attractive to many customers (e.g. targeted offerings which distinguish the needs of web application providers versus high-performance scientific computing clusters)
   • Support for standard enterprise software to minimize the amount of re-work that CIOs/IT people will need to do
   • Professional SLA (service-level agreement) which legally obligates Amazon to provide a certain level of service
   • Simple billing system
3. Third party: The existence of third party players on a particular type of technology provide two things to companies interested in adopting a new type of technology. First, it is proof of a concept’s maturity. If a technology really is great, then there will be companies that aim to provide services or add-on products for users of that technology. Second, it simplifies the job of using the technology, as there will be companies who specialize in providing support and useful add-ons. In the case of Cloud Computing, there are a number of providers who specialize in helping companies deploy Cloud computing software or manage their use of computing resources. Companies like Eucalyptus and CycleComputing can provide support (for a fee) for companies interested in setting up their own cloud, and open source projects like Hadoop and research papers on how to use Amazon’s EC2 to do proteomics research not only validate Cloud Computing but provide free advice on how to set up research “clouds”!
4. Benefits achievable on multiple scales: Too often, new technologies promise grand benefits which can only be realized on very specific scales. Small pilots and full-scale transformations are not how companies make decisions and do not reflect the reality of how technology is used. Technology that only delivers significant benefits in small pilots or only work if all old technology is replaced by a new one will be very challenging to adopt. The beauty of the Cloud efforts detailed in the article is that they cover a wide range of scales. Benefits are easily realized regardless of if you outsource your entire IT infrastructure, or if you choose to only use the Cloud some of the time, or selectively avoid using the Cloud when regulatory concerns dictate it.

This is not to say that the adoption of cloud computing in these cases went perfectly smoothly. Amazon does experience service outages and there are still issues to be sorted out regarding SLAs and regulatory concerns, but their adoption by companies in an industry known for conservative IT practices is something that can and should be learned from.

(Image credit)

The heartbeat of the news.

Ever since June 25, 2009, Michael Jackson’s death has been the talk of the nation, his face plastered over web articles, newspapers, and television stations. His death broke the record for the number of users on Yahoo news at any one point in time, topping even President Barack Obama’s inauguration, and even Google believed its servers were under attack due to the sudden spike in web searches for the moon-walking legend. However, have you ever wondered why the news of the King of Pop’s untimely death has stayed in the media for so long, while other news topics, such as the death of another cultural icon, Farrah Fawcett, quickly died out?

Jon Kleinberg, Jure Leskovec, and Lars Backstroma, from the computer science department at Cornell, sought to answer these types of questions by tracking the life-cycle of news articles for a three month period during 2008. Their research included 20,000 mainstream media sites and over 90 million articles. Using a complex algorithm which could identify certain phrases in different news articles such that the computer could mark them as being of the same subject (a task that has proven to be very difficult time and time again), the team tracked the movement of news using across blogs and news sites across the Internet. Armed with an extensive pool of data to sift through and analyze, the three researchers discovered an astounding pattern that was shared throughout most news topics.

They found a consistent rhythm as stories rose into prominence and then fell off over just a few days, with a “heartbeat” pattern of handoffs between blogs and mainstream media. In mainstream media, they found, a story rises to prominence slowly then dies quickly; in the blogosphere, stories rise in popularity very quickly but then stay around longer, as discussion goes back and forth. Eventually though, almost every story is pushed aside by something newer.

Before research like this was done, many editors and journalists perceived something they described to be a “news cycle.” However, with no quantifiable data, there was no way to be confident whether this was just their perceptions or an actual phenomenon. With the information collected by these Cornell researchers, they believe the latter to be the case and have started to create mathematical models which would accurately describe the life-cycle of news.

The slow rise of a new story in the mainstream, the researchers suggest, results from imitation – as more sites carried a story, other sites were more likely to pick it up. But the life of a story is limited, as new stories quickly push out the old. A mathematical model based on the interaction of imitation and recency predicted the pattern fairly well, the researchers said, while predictions based on either imitation or recency alone couldn’t come close.

This type of news excites me because it shows how technology and the Internet have produced a tangible result (in this case, a physical model to the life cycle of a news article) to a question that would have been unsolvable 20 years ago. Truly the capabilities of technology to solve even the most abstract problems are limitless.

(Image Credit)

One of the ways in which scientists can reach out to the public with new social media techniques is through online video, and this is a lesson that the University of Nottingham has learned well. This past week, I found three informative sites that scientists at the University of Nottingham have contributed to:

• Sixty Symbols – a site dedicated to helping the layperson understand those crazy symbols that they see in physicist’s and astronomer’s equations and work



• Periodic Table of Videos – a site which has an informational video for nearly every element in the periodic table
• Test-Tube – an award-winning site which tries to document the daily life of a scientist, including the triumphs, failures, and the monotony/drama that occurs in between

The interesting thing, at least to me, is that the videos succeed not only in conveying interesting concepts in, hopefully, an easy-to-understand format, but that they do what textbooks and slides and figures and online encyclopedia’s can never do: they humanize the science and the scientists behind them. And, if that happens effectively, then social media may be the most powerful scientific tool ever.

In 2003 an unknown virus suddenly emerged in Guangdong China and proceeded to spread rapidly around the world. The SARS coronavirus disseminated around the world via the global air transportation network with stunning efficiency, highlighting one of the unintended consequences of the globe’s vast airline system. After the SARS outbreak, a group at St. Michael’s Hospital in Toronto, took it upon themselves to study the SARS outbreak in detail. The end goal to develop effective strategies to deal with future epidemics. Their project dubbed Bio.Diaspora took a multidisciplinary approach in analyzing air traffic patterns and the distribution of infectious diseases. Their self proclaimed mission:

Understand global patterns of human travel via commercial airlines as a way to predict how emerging infectious diseases are most likely to spread around the world – and consequently apply this knowledge to help the world’s cities and countries better prepare for and respond to global infectious disease threats of tomorrow.

The Bio.Diaspora team believed that not only more applied research into the impacts of global population mobility on public health and security is necessary, but access to quality data on global air transportation and traffic patterns is needed as well. They sought to fulfill this need by:

[D]eveloping a data warehouse for the sole purpose of conducting methodological and applied research on commercial air travel and emerging infectious disease threats. This report embodies rigorous analysis of these data from multiple scientific perspectives – medicine, infectious diseases, public health, health policy, biostatistics, geographic sciences, network analysis, computer sciences, and mathematical modeling.

Their thorough analysis accounted for numerous factors and yielded a report just prior to the emergence of the H1N1 influenza (Swine Flu) pandemic. One of the really interesting parts of the Bio.Diaspora report was the numerous simulations done on potential H5N1 avian influenza transmission from emergence in numerous potential cities around the world.

Click through for interactive version.

The above graphic illustrates the likelihood of importation of H5N1 avian influenza into various areas of the world with an epidemic beginning in São Paulo, Brazil. This caught my eye as it seemingly foreshadowed the H1N1 epidemic. After the emergence of H1N1, the Bio.Diaspora team went back to study the air traffic patterns of the initial stages of the spread (March and April 2009) from Mexico. Running simulations like those from the Bio.Diaspora project’s report they were able to produce predictions based on the flight itineraries (data shown below) that correlated highly with the observed transmission pattern. Their complete analysis is published in the New England Journal of Medicine.

Destination Cities and Corresponding Volumes of International Passengers Arriving from Mexico between March 1 and April 30, 2008.

The Bio.Diaspora project team’s work on both the SARS epidemic and now the H1N1 pandemic illustrate that there’s still much to learn about managing public health crises on a global scale thanks to the highly interconnected nature of today’s cities. It’s a much smaller world now and new tools and ideas will be necessary to deal with future emerging diseases.

(Bio.Diaspora)(Spread of a Novel Influenza A (H1N1) Virus via Global Airline Transportation)

If you read our last post on the N-body problem and want to try your hand at playing around with simulations of this enduring problem, then this article from Wired Science may be music to your N=2 ears. A group of developers from virtual world developer Genkii and astrophysicists from the Meta Institute of Computational Astrophysics have put together a simulation tool using the open source OpenSim (an implementation of Linden Lab’s popular SecondLife virtual world engine) to run N-body problem simulations and aim to publish their results in the Journal of Virtual Worlds Research.

As to why the developers chose to use OpenSim (from their ArXiV pre-print):

“From the point of view of an astrophysicist dealing with gravitational N-body simulations, virtual worlds such as OpenSim are N-body simulators, with two extra features: a surprisingly elaborate graphics module, and a bug in the equations of motion. As to the latter: whereas objects should attract each other via Newton’s inverse-square law of gravity, objects in OpenSim fall straight down. However, that “bug” is easily fixed. We have done so, and we discuss our first results in this paper.”

The most interesting aspect of this work is not only that it was possible, but that, should virtual world administrators choose to allow it, these tools can be bundled into almost any virtual world running off an OpenSim compatible setup!

We have modified the standard physics engine of OpenSim using a plugin. Server administrators can select to replace the standard physics engine with our plugin at server-initialization time, region by region … Though [the example above] shows only one avatar in view on a remote “desert island,” a similar simulation could, in principle, take place anywhere on an OpenSim grid, and any user present could collaborate to construct the initial conditions, discuss the outcome with other avatars, save data from the simulation, etc.

Now, the current simulation has a limit: it can only simulate up to 50 bodies – but I’d like to think of this as just one powerful example of how virtual world technology might be used in the future to power new types of simulations and empower scientists to collaborate over them.

(Image credit: ArXiV pre-print of publication)