PathLinker

Reconstructs signaling pathways from protein interaction networks
<h1>PathLinker</h1> <br> <h2>Description</h2> <p>Implements the PathLinker algorithm for reconstructing signalling pathways from protein interaction networks.</p> <br> <h2>Overview</h2> <p>PathLinker is a method for reconstructing signalling pathways from protein interaction and regulatory networks. Consider a protein-protein interaction network represented as a directed graph. The network may contain physical, signalling, and regulatory interactions between pairs of proteins. Given a query composed of a set of receptors and a set of transcription factors in this network that represent the "sources" and "targets" of some specific signalling pathway (e.g., the Wnt pathway), PathLinker attempts to compute a high quality reconstruction of this pathway. Specifically, PathLinker computes a sub-network that connects the receptors in the query to the transcription factors in the query. More generally, PathLinker will be useful for connecting any set of sources to any set of targets in an interaction network.</p> <p>The primary algorithmic component of PathLinker is computing the <em>k</em>-shortest simple paths in the network from any source to any target. PathLinker accomplishes this task through a novel integration of Yen's algorithm with the A* heuristic, which allows very efficient computation for very large <em>k</em> values, e.g., 10,000, on networks with hundreds of thousands of edges. PathLinker outputs the sub-network composed of the <em>k</em> shortest paths.</p> <p>PathLinker supports several different options for weighting the edges in the network. If the edges in the input graph do not have weights, PathLinker computes the <em>k</em> lowest cost paths, where the cost of a path is the number of edges in it. If the input graph has edge weights, they can be treated additively or as probabilities. If the edge weights are additive, PathLinker defines the cost of a path as the sum of the edge weights and computes the <em>k</em> paths of lowest cost. In the case of probabilities, PathLinker treats the edge weights as multiplicative and computes the <em>k</em> highest cost paths, where the cost of a path is the product of the edge weights.</p> <p>See the publications referenced below for a formal description of the method, comprehensive evaluations and comparisons to other approaches, and experimental validation of results.</p> <br> <h2>How to use PathLinker</h2> <h3>Running the plugin</h3> <p>To run the plugin, fill in the inputs (as described below) and press the submit button. Note that PathLinker runs on the currently selected network.</p> <h3>Inputs</h3> <p><b>Sources/Targets:</b> PathLinker takes in the names of the sources and targets separated by spaces. If there are sources or targets named that do not exist in the network, PathLinker will warn the user. There are two options here:</p> <ul> <li><em>Allow sources and targets in paths</em>: Normally, PathLinker removes incoming edges to sources and outgoing edges from targets before computing paths. If the user selects this option, PathLinker will not remove these edges. Therefore, source and target nodes can appear as intermediate nodes in paths computed by PathLinker.</li> <br> <li><em>Targets are identical to sources</em>: If the user selects this option, PathLinker will copy the sources to the targets field. This option allows the user to compute a subnetwork that connects a single set of nodes. If the user selects this option, then PathLinker will automatically allow sources and targets to appear in paths, i.e., the previous option is also selected. Note that since PathLinker computes loopless paths, if the user inputs only a single node and selects this option, PathLinker will not compute any paths at all. </li> </ul> <p><b>Algorithm:</b> There are two parameters here: <ul> <li><em>k</em>: PathLinker takes in the number of paths the user wants. If an invalid value is input for <em>k</em> (e.g., a negative number or a non-integer), PathLinker will compute the default <em>k</em> = 200 paths.</li> <br> <li> <em>Edge penalty</em>: PathLinker takes in an edge penalty when using the additive or multiplicative options. For the additive option, PathLinker will penalize each path by a factor of (number of edges in the path)*(edge penalty), and for the multiplicative option by a factor of (number of edges in the path)^(edge penalty). The larger the value of edge penalty, the less likely it is that longer paths will appear in the results.</li> </ul> </p> <p> <b>Edge weights:</b> There are three options for the edge weights to be used in the algorithm: <ul> <li><em>Unweighted</em>: PathLinker will compute the <em>k</em> lowest cost paths, where the cost is the number of edges in the path</li> <br> <li><em>Weighted, edge weights are additive</em>: PathLinker will compute the <em>k</em> lowest cost paths, where the cost is the sum of the edge weights</li> <br> <li><em>Weighted, edge weights are probabilities</em>: PathLinker will compute the <em>k</em> highest cost paths, where the cost is the product of the edge weights</li> </ul> </p> <h3>Output</h3> <p>PathLinker pops up a table containing the <em>k</em> paths that displays the rank of each path, its score, and the nodes in the path itself. Additionally, if the user wants, PathLinker generates a sub-network consisting of only the nodes and edges that were involved in the <em>k</em> paths.</p> <br> <h2> How to Cite PathLinker</h2> <p>We will be very glad to hear from you if you use PathLinker in your work. If you publish a paper that uses PathLinker, please cite:</p> <ol> <li><a href="http://www.nature.com/articles/npjsba20162">Pathways on Demand: Automated Reconstruction of Human Signaling Networks</a>. Anna Ritz, Christopher L. Poirel, Allison N. Tegge, Nicholas Sharp, Allison Powell, Kelsey Simmons, Shiv D. Kale, and T. M. Murali, Systems Biology and Applications, a Nature partner journal, 2, Article number 16002, 2016.</li> <li> <a href="http://www.ncbi.nlm.nih.gov/pubmed/23641868">Top-down network analysis to drive bottom-up modeling of physiological processes</a>. Christopher L. Poirel, Richard R. Rodrigues, Katherine C. Chen, John J. Tyson, and T. M. Murali, Journal of Computational Biology, 20(5), 409-418, 2013.</li> </ol> <br> <h2>Contact Information</h2> <p>If you have any problems using PathLinker or any suggestions for improvement, please contact us by email at jeffl@vt.edu or murali@cs.vt.edu</p>

1.2.4

Works with Cytoscape 3.2

Release Notes

Version 1.2.4 adds the following features: <ul> <li>Allows user to press Apps > PathLinker > Open to make PathLinker the selected tab in the CytoScape panel</li> <li>Fixes bug with persistent allow sources in paths setting</li> </ul>

1.2.1

Works with Cytoscape 3.2

Release Notes

Version 1.2.1 adds the following features: <ul> <li>Hierarchical layout only applied with k less than or equal to 200, due to slow rendering for large networks.</li> </ul>

1.2

Works with Cytoscape 3.2

Release Notes

Version 1.2 adds the following features: <ul> <li>Subnetwork is now automatically displayed as a hierarchical layout.</li> <li>Plugin now quits if there are no valid sources/targets.</li> <li>If the edge penalty is left blank, the plugin will assume the default value.</li> <br> </ul>

1.1

Works with Cytoscape 3.2

Release Notes

Version 1.1 adds the following features: <ul> <li>Adds support for graphs with multiple directed edges connecting the same pair of nodes. Now, multiple edges are replaced with a single edge whose weight is the average of the multiple edges.</li> <br> <li>Adds option for the user to specify an edge penalty for both additive and multiplicative options. For the multiplicative option this parameter will penalize each path by a factor of (number of edges in path)^(edge penalty) and for the additive option by a factor of (number of edges in path)*(edge penalty). <br> Note: to obtain the same results as v1.0 of the PathLinker plugin, please use a value for the argument equal to the total weight of edges in the network.</li> <br> <li>Fixes a bug with empty node/edge table entries being left behind after PathLinker is run.</li> </ul>

1.0

Works with Cytoscape 3.2

Release Notes

First version of PathLinker plugin.

CYTOSCAPE 3

Version 1.2.4

License Click here

Released 13 Oct 2016

Works with Cytoscape 3.2

Download Stats Click here