Research About Me Links Teaching

I recently graduated from the University of North Carolina at Chapel Hill with a PhD from the department of Computer Science. I studied under Jack Snoeyink. While there, I earned a certificate from UNC's Bioinformatics and Computational Biology program and was part of the the inter-institutional BioGeometry research group.

I find structural biology absolutely fascinating. I delight in finding and solving computational problems that emerge from structural biology. My first publication resulted from collaboration with Professors David and Jane Richardson at Duke. The biological problem they were interested in was the placement of hydrogen atoms into crystal structures (J. M. Word, S. C. Lovell, J. S. Richardson, and D. C. Richardson (1999) "Asparagine and Glutamine: Using Hydrogen Atom Contacts in the Choice of Side-chain Amide Orientation." JMB 285, 1735-47). They had previously used a brute force approach to find the minimum energy placement of hydrogen atoms into a given structure. Our improvement came in replacing the brute force approach with a dynamic programming algorithm. With this better algorithm, we observed a speedup of seven orders of magnitude.

The general problem the Richardsons encountered emerges elsewhere within computational structural biology. It is called the "side chain placement problem" within protein design. My second publication expands upon the results of the first publication, and connects the side chain placement problem with a class of NP-Complete problems for which certain problem instances yield polynomial time solutions. This class of problems can be described with graphs. Each problem instance maps to a graph instance. A graph theoretic property called treewidth, bounds the complexity of problem instances. If the treewidth is bound by a constant, then the problem instance will have a polynomial time solution. (I find Hans Bodlaender's work on treewidth very helpful).

I began collaborating with Brian Kuhlman when exploring dynamic programming in the sidechain placement problem. It has been an incredibly fruitful collaboration. I'm very lucky to have had the opporunity to work with him. Brian wrote the design module of the Rosetta mollecular modelling program.

Publications

Andrew Leaver-Fay, Yuanxin Liu, and Jack Snoeyink. Faster placement of hydrogen atoms in protein structures by dynamic programming in the Workshop on Algorithm Engineering and Experiments, 2004 (ALENEX 2004). [PDF]

Andrew Leaver-Fay, Brian Kuhlman, and Jack Snoeyink. An Adaptive Dynamic Programming Algorithm for The Side Chain Placement Problem in the Pacific Symposium on Biocomputing, 2005 (PSB 2005). [PDF]

Andrew Leaver-Fay, Brian Kuhlman, and Jack Snoeyink. Rotamer-Pair Energy Calculations Using a Trie Data Structure appearing in 5th Workshop on Algorithms in Bioinformatics (WABI 2005). Published by Springer. [PDF].
Copyright, Springer-Verlag

Andrew Leaver-Fay, Glenn Butterfoss, Jack Snoeyink, and Brian Kuhlman. Maintaining solvent accessible surface area under rotamer substitution for protein design Journal of Computational Chemistry, 2007, Feb 6. [Download]

Andrew Leaver-Fay, Yuanxin Liu, Jack Snoeyink, and Xueyi Wang. Faster placement of hydrogen atoms in protein structures by dynamic programming The Journal of Experimental Algorithms, 2007. Volume 12. [Available Soon]


Email: plato at cs dot unc dot edu