Subsets of adjacent nodes (SOAN): a fast method for computing suboptimal paths in protein dynamic networks

ABSTRACT

Suboptimal path analysis in a protein structural or dynamical network becomes increasingly popular for identifying critical residues involved in allosteric communication and regulation. Several software packages have been developed for calculating suboptimal paths, including NetworkView, WISP, and CNAPATH (Bio3D). Although these packages work well for biological systems of moderate sizes, they either dramatically slow down or are subjected to accuracy issues when applied to large systems such as supramolecular complexes. In this work, we develop a new method called SOAN, which implements a modified version of Yen’s algorithm for finding loopless k-shortest paths. Instead of searching the entire protein network, SOAN builds up a subgraph for path calculations based on an initial evaluation of the optimal path and its neighbouring nodes. We test our method on four systems of increasing size and compare it to the NetworkView, WISP and CNAPATH methods. The result shows that SOAN is approximately five times faster than NetworkView and orders of magnitude faster than CNAPATH and WISP. In terms of accuracy, SOAN is comparable to CNAPATH and WISP and superior to NetworkView. We also discuss the influence of SOAN input parameters on performance and suggest optimal values.

GRAPHICAL ABSTRACT

KEYWORDS:

• Molecular dynamics
• allosteric communication and regulation
• dynamic network analysis
• suboptimal paths
• graph theory

Acknowledment

Computational resources were provided in part by an allocation from the National Science Foundation XSEDE program CHE110042. An award of computer time was provided by the INCITE program. This research also used resources of the Oak Ridge Leadership Computing Facility, which is a DOE Office of Science User Facility supported under Contract DE-AC05-00OR22725.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data Availability

This code is freely available at https://github.com/tdodd3/SOAN.

Additional information

Funding

This work was supported by National Science Foundation grant MCB-2027902 and National Institute of General Medical Sciences grant R35GM139382 to I.I. T.D. was supported by a Molecular Basis of Disease fellowship from Georgia State University. X.Q.Y. and D.H. are supported by National Science Foundation grant MCB-2018144