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 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...
Jennifer Listgarten took a long and winding road to find her current area of interest in computational biology. She started off with a Physics degree, followed by a Master’s in Computer Vision before completing a Ph.D. in Machine Learning at the University of Toronto with advisors Sam Roweis and Radford Neal. Within computational biology, Jennifer is interested in methods development, especially using insights from machine learning along with more standard applied statistics. She also has an interest in application of these methods to discover new biological/medical insights. Jennifer has worked in a broad set of domain areas including gene expression studies, LC-MS proteomics, immunoinformatics, statistical genetics, and epigenetics. She is currently also starting to explore topics related to cancer and wearables.
James Zou received his Ph.D. from Harvard University in 2014. He was recently a Simons fellow at U.C. Berkeley and a research associate at the Broad Institute. He is interested in developing machine learning algorithms to gain insights into both human evolution and human diseases. He is also interested in design-optimization for synthetic biology and in algorithms inspired by natural and social phenomena.
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...
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).