CAREER: Exact and Approximate Algorithms for 3D Structure Modeling of Protein-Protein Interactions

Toyota Technological Institute At Chicago, Chicago IL

Investigators

Abstract

Protein-protein interactions (PPIs) play fundamental roles in all biological processes including the maintenance of cellular integrity, metabolism, transcription/translation, and cell-cell communication. High-throughput experimental approaches have been developed to systematically identify PPIs. However, these methods cannot produce atomic 3D models of PPIs, which hinder studying PPI molecular mechanisms at atomic level and understanding cellular processes at molecular level. Atomic structures of PPIs are also important for rational drug design. High-resolution methods for PPI 3D structure determination such as X-ray or NMR are time-consuming and sometimes technically challenging, so computational method is urgently needed for PPI structure modeling. Intellectual Merit: This proposal studies exact/approximate algorithms for 3D structure modeling of PPIs, with the ultimate goal to enrich large-scale PPI networks with high-resolution 3D structure models. The proposal will study 1) simultaneous threading of all sequences of a target PPI to a complex template; 2) protein complex side-chain packing with a very large rotamer library and more realistic energy functions; and 3) simultaneous interface threading and side-chain packing to align distantly-related protein complexes. This proposal will apply several elegant and powerful techniques such as graph minor theory, probabilistic graphical models, dual relaxation and decomposition, which are not well-known in the field, to understanding the mathematical structure of the problem with more realistic and challenging settings and designing efficient algorithms. The expected outcome includes theoretical analysis of protein interfaces and complexes by graph theory, efficient algorithms for PPI structure modeling and publicly available software and servers. The resulting software can be used to verify experimental PPIs and even predict novel PPIs missed by experimental approaches. The software will benefit a broad range of biological and biomedical applications, such as gene functional annotation, better understanding of disease processes, design of novel diagnostics and drugs, personalized medicine and even bio-energy development. The resulting algorithms and software will be communicated to the broader community and also be further developed and disseminated to industry by two companies. Broader Impact: This work is expected to enrich and disseminate knowledge on systems biology and structure bioinformatics, machine learning, graph theory and optimization and further enrich the pedagogical literature. Contributions from this work to computer science are: understanding of protein graphs using graph minor theory and graph transformations and solving several computationally challenging problems by combining techniques from graph theory and continuous optimization. This research work will train minority students from two HBCU schools, future K-12 science teachers and students attending the first online bioinformatics program in Illinois. Students will receive training at the intersection of biology and computer science. The proposed course materials and book chapters will be freely available to the public.