Algorithms that Can Handle the "Omics"
Imagine two Neanderthal proto-scientists, standing before an enormous pile of rocks—big rocks, small rocks, smooth rocks, rocks with jagged edges.
“Well,” remarks one of Stone Age researchers, “this is a lot of data here.”
“Yes,” replies his colleague, “if only we had some way to make sense of it all, I bet we could achieve a breakthrough in rock utilization.”
Today, biological researchers are confronting a similar dilemma: a wealth of data, but an inadequate analytical toolkit. Increasingly, biologists are using genomic methods, such as expression profiling, next-generation sequencing, and RNAi screens, together with proteomic and metabolomic technologies, to discover the molecular basis of changes in living systems. Collectively, these methods are often referred to as “omics.”
Unfortunately, these advances in experimental technologies have, in many cases, outpaced the development of the bioinformatics tools that are needed to analyze the data. In other words, optimal analysis of large quantities of experimental data often requires the solution of hard problems that are intractable by conventional computational tools. Happily, collaborative efforts between the Massachusetts Institute of Technology and Microsoft Research have resulted in new algorithms that often do quite well in analyzing these types of problems.
Our methods, which extend ideas from statistical physics of disordered systems to problems in computer science, have provided novel distributive algorithmic schemes for solving large-scale optimization and inference tasks. Among the features of our new algorithms are computational efficiency, parallelizability, and flexibility to include heterogeneous prior knowledge and to integrate diverse data sources. The spectrum of applications ranges from constraint satisfaction and stochastic optimization problems over networks, to graphical games and statistical inference problems.
Our collaboration aims at bringing these new algorithmic techniques to bear on significant problems in biological research. Preliminary results have already led to the discovery of new functional genes and to the prediction of protein contacts from sequence data.
Our current focus is on cancer genomics. In collaboration with the Memorial Sloan-Kettering Cancer Center, we are working on the integration of different types of molecular data to reveal complex response pathways of relevance in cancer development. We hope that this work leads not only to advances in general algorithmic techniques for biological research, but also to the development of drug targets for specific cancers.
Primary Researchers
Jennifer Tour Chayes is managing director of the Microsoft Research New England lab in Cambridge, Massachusetts. Before this, she was research area manager for Mathematics, Theoretical Computer Science, and Cryptography at Microsoft Research, Redmond. Chayes joined Microsoft Research in 1997, when she co-founded the Theory group. Prior to that, she was professor of Mathematics at the University of California, Los Angeles, and a post-doctoral Fellow in Physics and Mathematics at Harvard and Cornell. She obtained her Ph.D. in Mathematical Physics from Princeton University. Her research areas include phase transitions in discrete mathematics and computer science, structural and dynamical properties of self-engineered networks, and algorithmic game theory. She is the co-author of more than 100 scientific papers and the co-inventor of more than 25 patents. Chayes is a Fellow of the American Association for the Advancement of Science, the Association for Computing Machinery and the Fields Institute, and a National Associate of the National Academies. She is a member of many boards and committees, and is currently chair of the ACM Turing Award Committee.
Christian Borgs is deputy managing director of the Microsoft Research New England is deputy managing director of the Microsoft Research New England lab in Cambridge, Massachusetts. He is also an affiliate professor of Mathematics at the University of Washington. Before becoming deputy managing director of the New England lab, he was a principal researcher and co-manager of the Theory group at Microsoft Research. Prior to that, Borgs was a chaired professor of Physics at Leipzig University. Borgs obtained his Ph.D. from the University of Munich, was a post-doctoral Fellow at ETH Zürich, and an assistant professor of Physics at the Free University of Berlin. Borgs’ research areas include properties of self-engineered networks, phase transitions in theoretical computer science, and algorithmic game theory. He is the author of more than 100 scientific papers and the co-inventor of more than 25 patents. Borgs is the recipient of the 1993 Karl Scheel Prize of the German Physical Society.
Riccardo Zecchina is professor of Theoretical Physics at the Politecnico di Torino in Italy. His interests are in topics at the interface between statistical physics and computer science. His current research activity is focused on combinatorial and stochastic optimization, probabilistic and message-passing algorithms, and interdisciplinary applications of statistical physics (in computational biology, graphical games, and statistical inference).
