Dr. Dobb's Journal - August 2008 - (Page 17)

DDJ: I looked at your paper “Inferring Tree Models for Oncogenesis from Comparative Genome Hybridization Data” . CP: You’re fishing up papers I’m very proud of and nobody else knows about! Thank you. That paper was undertaken due to the excellent work at the National Institutes of Health [NIH] of my former Stanford student Alejandro Schdffer. Today with relatively low-tech techniques you can get a glimpse of what regions of the genome are overactive or underactive in cancer cells compared to healthy cells. You get a bunch of regions in the genome where obviously something fishy happens. Cancer is the result of this. When you get lots of such cells, various stages of cancer development, it’s like there were many species of cancer cells. Our thought was, “Why not use the techniques biologists use in the field of phylogenetics and construct the tree of life?” In phylogenetics, you get the either the genome or the phenotype, the external characteristics of the species you find, and from this you infer what went on. Who was the common ancestor? So we thought about using the same technique to understand how cancer grows and develops. We conjectured that something goes wrong and that’s the root of the tree. Because of that, a bunch of other things go wrong, and so on. Looking at the data, you can infer quite reasonably what happened. A lot of other clever clinicians from NIH gave a paper, which led to this. We found tree models for the progress of cancer. There are molecular events that predispose the cell. Either a suppressor is busted or a promoter is overactive. The amazing thing was how hard it was to find data in these days of overabundant data. We could only find data for a few kinds of cancers. People have used the technique after us, and I’m sure that there are much more elaborate, sophisticated lab techniques. DDJ: Have there been concrete research results? CP: One of our predictions is that ovarian cancer is really three different diseases that have very close clinical symptoms. I believe there is some support for that now. Our tree model had a root, and the next three nodes were way down, suggesting it was not really one tree. If you look at ovarian cancer, the tree that, according to our model, describes the progression of the diseases is really a forest of three trees. DDJ: What got you started in math? CP: Back home in Greece, my father was a math teacher. Mathematics always fascinated me, but I don’t believe I ever spoke about math with my father. His influence was tacit. We never spoke about it because we were both so passionate about the subject, not until I was in college and just before his death, when it was obvious that I had become a better mathematician than him, so the tension was not there anymore. DDJ: He must have been a wise man, because one thing a father can do is instill in his child a hatred of a subject. Obviously, you speak at least two languages, probably more. CP: I mumble many languages. I speak Greek and English and have working knowledge of German, French, Spanish, Italian, some Turkish. DDJ: Are you a musician? CP: Yes, how did you guess? I am a failed musician! I’m very interested in music but I’m not very good at it. DDJ: I’ve observed that many computer scientists are also linguists, musicians, and play chess. CP: So you were wrong about the chess part. DDJ: No chess? CP: Actually, all my life I’ve been next to incredible chess players. The two top players in Greece when I was growing up, one was my cousin, the other was my schoolmate. DDJ: So you narrowly missed becoming a chess player! CP: More like, I was so discouraged by my encounters with those two. But I think you are close. I’m very passionate about backgammon. I’m a serious backgammon player. Frankly, I think backgammon is a much more interesting game, much harder to learn. DDJ: Because you have to assess such fine probabilities? CP: It’s something much simpler than that. In chess, when you play like an idiot, you always lose, so you learn. In backgammon, you can play 10 games, not play well, and win. So you think you are great but you have made a great number of mistakes. Tragically, life is closer to backgammon, because you can play a perfect game and lose! DDJ: So can chess be solved without exhaustive search, by some model? CP: My most famous book, perhaps, is Computational Complexity. Complexity Theory is a mathematical field that tries to find the intrinsic difficulty of problems. “This problem looks difficult, is it because it is really difficult or because I’m stupid?” That’s the question. Computational Complexity is a very difficult field, because it’s nearly impossible to prove what everyone knows from experience. You have to be very, very lucky. The P versus NP problem, whether you can telescope exhaustive search, is always the key, because there are instances where we know how to bypass exhaustive search. Compare chess with Nim. There are many games where, by creative thinking, you can see that they don’t have intrinsic difficulty. They can be solved front-to-back. You can look at a position and make a calculation and say it’s a win. People have proved that chess is part of the family of games that seem to have intrinsic difficulty, that seem to embody computation, require exhaustive search. There can be games on a large board that have very suggestive symmetries, but still, they have subtle mathematical properties. DDJ: What are you working on now? CP: I’m always looking at lots of problems in various areas. But in the last 10 years, the larger part of my work is on this new area, trying to understand the Internet and the Web, trying to understand the underpinnings. In computer science, we don’t have great mysteries. We want to solve problems, but it’s not like we have mysterious objects we don’t understand. It’s not like Physics, which has the Universe, or Economics, which has the Markets, Neuroscience has the Brain, and Biology the Cell. For us, the computer and its software are huge, complex, powerful, and fascinating, but we constructed them. Intrinsically, there’s very little mystery. In many ways, the Internet and the Web, we did not create them. They arrived, appeared, emerged. All these other artifacts, software, processers, and so forth, there was a designer, a team, an entity that intentionally built them. The Web emerged from an interaction of millions of entities on the basis of deliberately simple protocols. Thus the Internet and the Web are our mysterious objects. Computer scientists are looking at them the way other scientists are looking at their mysterious objects. We have to look at them using the scientific method: observations, measurement, experiments, verifiable theories, applied mathematics. August 2008 l www.ddj.com l Dr. Dobb’s Journal 17 http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - August 2008

Dr. Dobb's Journal - August 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Developer’s Notebook A Conversation with Christos Papadimitriou OpenGL and Mobile Devices: Round 2 Ellipse Specification Using Vectors Embed Custom GUIs in WPF Building RIAs on J2EE Foundations Disentangling Concepts in Object-Oriented Systems The Agile Edge Effective Concurrency Swaine’s Flames

Dr. Dobb's Journal - August 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.