Monday, February 21, 2011

Computer Science Problem? Biology has the Answer!

The last time I had a class on computers was in 7th Grade, and I wasn't very good at it. To be very honest, complicated computer-related things often confuse me (I did surprisingly well in my Geographic Information Systems- GIS- class. I'm definitely learning!).

A couple of weeks ago, in the Research Scholars Journal Club, we were discussing a paper about a computing problem known as 'Maximal Independent Set' or MIS. I was discussing it with a friend of mine a little while ago, who happens to be a software engineer, and we were discussing how this problem is almost like a game of chess (yes, I use lots of analogies to make sense of things I do not understand initially). Chess is all about looking ahead, and making your moves based on what you think the opponent might do, and then planning your next move accordingly and so on. Experts can sometimes look ahead upto several moves, but there's only so much you can predict. This computing problem is similar in the sense that there are a few 'leader nodes' and several 'non-leader nodes' in a local network, and they must interconnect in a way (almost like a spiderweb) such that no two leaders are connected and each non-leader is connected to at least one leader. The complication arises from the fact that there's so many leaders and non-leaders, that you can only tell who your neighbors are upto a certain degree, and without full confidence- if this were a game of chess, you would have to look ahead lots of moves, and even then you may or may not win. Thus, this computing problem is far more complicated than it sounds.

As it turns out, fruit flies have found a way to solve this problem that has baffled computer scientists for a long, long time. During neurological development in fruit flies, a number of bristles can be observed. Through a randomized selection process, some cells are chosen to be 'Sensory Organ Precursors' or SOPs (the 'leaders'), while others are not ('non-leaders'). The SOPs express a large amount of 'Delta' protein, and the surrounding cells had a protein called 'Notch' protein. The Delta protein, essentially, sends signals to its surrounding cells, which, with the help of Notch protein, can understand that there are SOPs in their vicinity. This message prevents them from becoming SOPs themselves, and so no two neighboring cells as SOPs.

That's a very good description of what I've been trying to say in last 2 paragraphs. It's taken directly from the paper.

So once again, biology saves the day, giving computer scientists another reason to rejoice!


Link to paper: http://www.sciencemag.org/content/331/6014/183.full

No comments:

Post a Comment