Binhai Zhu, Ph.D.: On the Chain Pair Simplification Problem

Friday, October 7 at 12:30 p.m. in IT 252


Motivated by computing and visualizing the structural resemblance between a pair of protein backbones in 3D, the Chain Pair Simplification (CPS) problem was proposed in 2008. In the problem, given two polygonal chains A and B, one needs to simplify them simultaneously into A’ and B’ such that A and A’, B and B’, and A’ and B’ are close (using the non-traditional discrete Frechet distance measure). In this talk, I will illustrate the development of this research problem, including an O(n^5) time solution and some empirical results using real datasets from the Protein Data Bank. In addition, I will introduce some variations of the problem and pose some open problems..

About Binhai Zhu

Dr. Binhai Zhu obtained his PhD at McGill University in 1994. After two years of post-doc at Los Alamos National Laboratory, he has been teaching in HK, Canada and US since 1996. He is currently a professor in computer science at Montana State University, Bozeman, MT, USA.  His main research interests are in algorithms, especially in geometric algorithms and bioinformatics. He has published over 180 papers in these areas. More information about his research can be found on his web page.