Subsets of adjacent nodes (SOAN): a fast method for computing suboptimal paths in protein dynamic networks
Subsets of adjacent nodes (SOAN): a fast method for computing suboptimal paths in protein dynamic networks
复制标题
DOI：
10.1080/00268976.2021.1893847
复制
发表时间：
2021-03
影响因子：
1.7
通讯作者：
T. Dodd;Xin-Qiu Yao;D. Hamelberg;I. Ivanov
中科院分区：
文献类型：
--
作者：
T. Dodd;Xin-Qiu Yao;D. Hamelberg;I. Ivanov
摘要蛋白质结构或动力学网络中的次优路径分析越来越多地用于识别与变构通讯和调控有关的关键残基。已经开发了几个用于计算次优路径的软件包，包括NetworkView、WISP和CNAPATH(Bio3D)。虽然这些包在中等大小的生物系统中工作良好，但当应用于超分子复合体等大型系统时，它们要么显著减慢，要么受到精度问题的影响。在这项工作中，我们开发了一种称为SOAN的新方法，它实现了Yen算法的修改版本，用于寻找无环k-最短路径。SOAN不是搜索整个蛋白质网络，而是基于对最优路径及其邻近节点的初始评估，建立用于路径计算的子图。我们在四个规模不断增大的系统上测试了我们的方法，并将其与NetworkView、WIP和CNAPATH方法进行了比较。结果表明，SOAN的速度大约是NetworkView的5倍，比CNAPATH和WIP快几个数量级。在准确性方面，SOAN可与CNAPATH和WISP相媲美，优于NetworkView。我们还讨论了SOAN输入参数对性能的影响，并提出了最佳值。图形摘要
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