Going the Distance for Protein Function Prediction
A protein ‘friends’ another protein on a particular organism’s Genomic Facebook, otherwise known as its protein protein interaction network (PPI). What can we say about these two proteins? Do we know that they perform similar functions in the cell? Can a drug targeting one effect the other?
Recent advances in technology have given us increasing amounts of low-resolution, high-throughput data on these ‘friendships’ between proteins. These experimentally validated interactions allow for the natural construction of an interaction graph similar to the friendship graph of Facebook.
Many current techniques to label proteins with regard to function are based on guilt by association. It is assumed that an unknown protein that interacts with a labeled or known protein is more likely to share a common function. Such a view correlates local distance in the network to pairwise similarity of protein function.
We maintain however that any method that relies on shortest path distance as a measure of functional dissimilarity in a PPI network will have inherent limitations. Two different equal length short paths do not simply equal degrees of similarity. We introduce diffusion state distance (DSD), a new metric based on a graph diffusion property similar to Google’s PageRank, designed to capture finer-grained distinctions in proximity for transfer of functional annotation in PPI networks. We show that replacing the shortest- path metric by DSD improves the performance of classical function prediction methods across the board.
Benjamin Hescott is an Assistant Professor in the Department of Computer Science at Tufts University’s School of Engineering.
His research interests include computational complexity, approximation algorithms, and computational biology. He graduated from Boston University with a Ph.D. in computer science in 2008. He is the faculty supervisor for the student ACM chapter and serves as liaison to the New England Undergraduate Computer Science Symposium. He is member of the leadership team for ELA (Empowering Leadership Alliance) whose main purpose is encouraging, preparing, and retaining underrepresented minorities in computer science. He is the recipient of the 2011 IEEE Computer Society Computer Science and Engineering Undergraduate Teaching Award, the 2011 Lerman-Neubauer Prize for Outstanding Teaching and Advising, the 2012 Henry and Madeline Fischer Award (Engineering Teacher of the year award) and the 2012 Lillian and Joseph Leibner Award for Excellence in Teaching and Advising of Students.