In recent years, computational challenges have become more and more important to infer biologically relevant information from the vast amount of experimental data available to systems biologists. Building on work originally done by Marc Mezard and Riccardo Zecchina in the context of random instances of satisfiability, we are developing various computationally efficient algorithms for problems in systems biology.
Specifically, we try to frame the biological question under consideration in terms of more standard problems in computer science, like clustering, Steiner trees, flow problems, etc., and then use approximation algorithms motivated by statistical physics to solve these problems. Currently, our most successful approach involves variants of belief- and survey propagation algorithms, but in the course of adapting our problem to this setting, we often need to derive alternative representations of the original computer science problem which might be useful when applying other algorithms as well.
The biological systems we have considered so far include pathways in yeast, various forms of cancer including glioblastoma, and learning problems in neural networks.
Microsoft Research Team Members
Christian Borgs is deputy managing director of Microsoft Research 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. Borgs’ research areas include properties of self-engineered networks, phase transitions in theoretical computer science, and algorithmic game theory. Read more...
Jennifer Tour Chayes is managing director of the newly opened 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. 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 almost 100 scientific papers and the co-inventor of more than 20 patents. Read more...
Jasmin Fisher studied Biology as an undergraduate, obtained her M.Sc. in Biophysics and Physiology, and her Ph.D. in Neuroimmunology at the Weizmann Institute of Science in the department of Neurobiology. She was then drawn to the new emerging field of Computational Biology, and did her post-doctoral work on the application of formal verification methods in biology. Jasmin is currently a Researcher at the Microsoft Research Cambridge lab in England, and an affiliated lecturer in the University of Cambridge. Jasmin is one of the founders of the field of Executable Biology and a leader in the area of formal methods in biology. Over the past decade, Jasmin has been pioneering the study on usage of program analysis techniques for the analysis of biological models. Her research focuses on the construction and analysis of executable models that mimic aspects of biological phenomena in order to better understand complex biological systems. She is mainly interested in processes of cell fate determination and signalling networks operating during normal development and cancer. Read more...
Anthony Gitter received his PhD in Computer Science from Carnegie Mellon University under the supervision of Ziv Bar-Joseph. His research is in computational biology with an emphasis on the networks problems that arise in systems biology. Anthony is especially interested in the mechanisms that underlie human disease and the hidden layers of biological phenomena. Read more...
Ernest Fraenkel, MIT
Ernest Fraenkel studied Chemistry and Physics as an undergraduate at Harvard College and obtained his Ph.D. in Structural Biology at MIT in the department of Biology. After doing post-doctoral work in the same field at Harvard, he turned his attention to the emerging field of Systems Biology. His research now focuses on using high-throughput techniques and computational methods to uncover the molecular pathways that are altered in disease and to identify new therapeutic strategies. Read more...
Riccardo Zecchina, Politecnico di Torino, Italy
Riccardo 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). Read more...
Sharing information to reconstruct patient-specific pathways in heterogeneous diseases (A. Gitter, A. Braunstein, A. Pagnani, C. Baldassi, C. Borgs, J. Chayes, R. Zecchina, and E. Fraenkel) Pacific Symposium on Biocomputing 19 (2014) 39 – 50.
Simultaneous reconstruction of multiple signaling pathways via the prize-collecting Steiner forest problem (N. Tuncbag, A. Braunstein, A. Pagnani, S.S. Huang, J. Chayes, C. Borgs, R. Zecchina, and E. Fraenkel) Journal of Computational Biology 20 (2013) 124 – 136.
Finding undetected protein associations in cell signaling by belief propagation (with M. Bailly-Bechet, C. Borgs, A. Braunstein, J. Chayes, A. Dagkessamanskaia, J. Francois, and R. Zecchina). Proceedings of the National Academy of Sciences (PNAS) 108 (2011) 882 – 887.
Statistical mechanics of Steiner trees (M. Bayati, C. Borgs, A. Braunstein, A. Ramezanpour, and R. Zecchina) Physical Review Letters 101, 037208 (2008), reprinted in Virtual Journal of Biological Physics Research 16, August 1 (2008).