Subsets of adjacent nodes (SOAN): a fast method for computing suboptimal paths in protein dynamic networks. (18th October 2021)

• Record Type: Journal Article
• Authors: Dodd, Thomas; Yao, Xin-Qiu; Hamelberg, Donald; Ivanov, Ivaylo
• Is Part Of: Molecular physics. Volume 119:Number 19/20(2021)
• Publication Date: 2021-10-18
• Subjects: Molecular dynamics -- allosteric communication and regulation -- dynamic network analysis -- suboptimal paths -- graph theory; Molecules -- Periodicals; Chemistry, Physical and theoretical -- Periodicals; Molécules -- Périodiques; Chimie physique et théorique -- Périodiques; 539.6.05
• DOI: 10.1080/00268976.2021.1893847
• Languages: English
• ISSNs: 0026-8976

Abstract

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: UF0001