Links for Additional Information

Erik Demaine, Ph.D.

Department of Electrical Engineering and Computer Science
Associate Professor of Computer Science and Engineering
Dept. of Electrical Engineering and Computer Science

Room 32-G680
617-253-6871 (phone)


B.Sc. Computer Science, Dalhousie University, 1995
M.Math., Computer Science, University of Waterloo, 1996
Ph.D., Computer Science, University of Waterloo, 2001
Assistant Prof., Dept. of Electrical Engineering and Computer Science, 2001
Member, MIT Computer Science and Artificial Intelligence Laboratory, 2001

Research Summary

Professor Demaine does his research in the Computer Science and Artificial Intelligence Laboratory, where he is a member of the Theory of Computation group. Professor Demaine`s research centers around algorithms, data structures, and geometry.

Folding and unfolding is an exciting area of geometry. It is attractive in the way that problems and even results can be easily understood, with little knowledge of mathematics or computer science, yet the solutions are difficult and involve many sophisticated techniques. The general sort of problem considered is how a particular object (e.g., linkage, piece of paper, polyhedron, or protein) can be reconfigured or folded according to a few constraints, which depend on the object being folded and the problem of interest. In particular, we are interested in efficient algorithms for characterizing foldability, and finding efficient folding processes, or in proving that such algorithms are impossible.

Protein folding
With our current knowledge, we can predict the primary sequence of amino acids in a protein from the DNA sequence of a gene. However, the key to protein function lies in the secondary and tertiary interactions between those amino acids that occur as a result of a process called protein folding. Protein folding takes a linear sequence of amino acids and creates a three-dimensional molecule with a defined structure. Within this defined structure lies the functional attributes of the protein. Therefore, if we can understand the process of attaining the folded state, we can predict the structure as well as the function of proteins from genomic sequence.

One direction we are exploring is the mechanics of proteins: ignoring the energy dynamics of the folding process, how can proteins reconfigure from one conformation to another? Here we model the protein as a mechanical linkage, either a chain representing the protein backbone or a tree representing all amino acids. Linkage reconfiguration has been studied extensively in geometry, but few positive results about reachability are known in 3D. Our work exploits the special properties of proteins, e.g., that they are initially produced by ribosome, to understand why proteins can reconfigure without obstruction.

We are also looking at a variation on the standard protein folding problem: designing synthetic proteins that fold stably into a particular configuration. So far we have shown the existence of such stable foldings, i.e., proteins with unique minimum-energy states, in a mathematical model of protein folding called the H-P model. This model takes into account the hydrophobic and hydrophilic nature of protein segments and computationally determines the folded state.

Selected Publications

  • Demaine, E.D., Langerman S., and O`Rourke, J. (2006) "Geometric restrictions on producible polygonal protein chains," Algorithmica, 44(2), 167-181.
  • Aichholzer, O., Bremner, D., Demaine, E.D., Meijer, H., Sacristan, V., and Soss, M. (2003) "Long proteins with unique optimal foldings in the H-P model," Computational Geometry: Theory and Applications 25(1-2), 139-159.
  • Bar-Joseph, Z., Demaine, E., Gifford, D.K., Hamel, A.M., Jaakkola, T.S., and Srebro, N. (2003) "K-ary clustering with optimal leaf ordering for gene expression data," Bioinformatics 19(9), 1070-1078.
  • Aloupis, G., Demaine, E.D., Dujmovi, V., Erickson, J., Langerman, S., Meijer, H., O`Rourke, J., Overmars, M., Soss, M., Streinu, I., and Toussaint, G. (2002) ``Flat-state connectivity of linkages under dihedral motions,`` in Proceedings of the 13th Annual International Sympsosium on Algorithms and Computation, 369-380.
  • Aloupis, G., Demaine, E.D., Meijer, H., O`Rourke, J., Streinu, I., and Toussaint, G. (2002) ``Flat-state connectivity of chains with fixed acute angles,`` in Proceedings of the 14th Canadian Conference on Computational Geometry, 27-30.

Last Updated: January 20, 2011