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

蛋白质-蛋白质相互作用（PPIs）在所有生物过程中发挥着重要作用，包括维持细胞完整性、代谢、转录/翻译和细胞-细胞通讯。已经开发出高通量实验方法来系统地识别ppi。然而，这些方法不能产生PPI的原子三维模型，这阻碍了在原子水平上研究PPI的分子机制和在分子水平上理解PPI的细胞过程。质子泵抑制剂的原子结构对合理的药物设计也很重要。高分辨率的PPI三维结构测定方法，如x射线或核磁共振，耗时长，有时技术上具有挑战性，因此迫切需要计算方法来进行PPI结构建模。智力优势：本提案研究PPI三维结构建模的精确/近似算法，最终目标是用高分辨率的三维结构模型丰富大规模PPI网络。该提案将研究1)将目标PPI的所有序列同时线程化到一个复杂的模板；2)蛋白质复合物侧链包装，具有非常大的旋转体库和更真实的能量函数；3)同时进行界面穿线和侧链包装，以排列远缘相关的蛋白质复合物。本提案将运用图小理论、概率图模型、对偶松弛和分解等在该领域尚不知名的一些优雅而强大的技术，以更现实和具有挑战性的设置来理解问题的数学结构，并设计有效的算法。预期的结果包括通过图论对蛋白质界面和复合物进行理论分析，高效的PPI结构建模算法以及公开可用的软件和服务器。由此产生的软件可用于验证实验PPIs，甚至预测实验方法错过的新PPIs。该软件将有利于广泛的生物和生物医学应用，如基因功能注释，更好地了解疾病过程，设计新的诊断和药物，个性化医疗甚至生物能源开发。由此产生的算法和软件将传播给更广泛的社区，并由两家公司进一步发展和传播给工业界。更广泛的影响：这项工作有望丰富和传播系统生物学和结构生物信息学、机器学习、图论和优化方面的知识，并进一步丰富教学文献。这项工作对计算机科学的贡献是：使用图小理论和图变换来理解蛋白质图，并通过结合图论和连续优化技术来解决几个计算上具有挑战性的问题。这项研究工作将培训来自两所HBCU学校的少数民族学生，未来的K-12科学教师和参加伊利诺伊州第一个在线生物信息学课程的学生。学生将接受生物学和计算机科学交叉领域的培训。拟议的课程材料和书籍章节将免费提供给公众。

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.