Paper Info
Title
iCFN: an efficient exact algorithm for multistate protein design.
Abstract
Motivation: Multistate protein design addresses real-world challenges, such as multi-specificity design and backbone flexibility, by considering both positive and negative protein states with an ensemble of substates for each. It also presents an enormous challenge to exact algorithms that guarantee the optimal solutions and enable a direct test of mechanistic hypotheses behind models. However, efficient exact algorithms are lacking for multistate protein design. Results: We have developed an efficient exact algorithm called interconnected cost function networks (iCFN) for multistate protein design. Its generic formulation allows for a wide array of applications such as stability, affinity and specificity designs while addressing concerns such as global flexibility of protein backbones. iCFN treats each substate design as a weighted constraint satisfaction problem (WCSP) modeled through a CFN; and it solves the coupled WCSPs using novel bounds and a depth-first branch-and-bound search over a tree structure of sequences, substates, and conformations. When iCFN is applied to specificity design of a T-cell receptor, a problem of unprecedented size to exact methods, it drastically reduces search space and running time to make the problem tractable. Moreover, iCFN generates experimentally-agreeing receptor designs with improved accuracy compared with state-of-the-art methods, highlights the importance of modeling backbone flexibility in protein design, and reveals molecular mechanisms underlying binding specificity.
Year
DOI
Venue
2018
10.1093/bioinformatics/bty564
BIOINFORMATICS
Field
DocType
Volume
Data mining,Exact algorithm,Computer science,Protein design,Theoretical computer science
Journal
34
Issue
ISSN
Citations 
17
1367-4803
0
PageRank 
References 
Authors
0.34
21
2
Name
Order
Citations
PageRank
Mostafa Karimi1172.72
Yang Shen224.10