The graph algorithms below have been used (or have the potential to be used) for the pathway reconstruction task. This task is typically formulated as follows: given a protein-protein interaction (PPI) network (represented as a graph, which may be weighted and/or directed) and a set of proteins of interest, return a subnetwork of the PPI graph that contains the proteins of interest.
References:
- Yosef et al. Toward accurate reconstruction of functional protein networks. Molecular Systems Biology. 2009. doi:10.1038/msb.2009.3
- Yosef et al. ANAT: a tool for constructing and analyzing functional protein networks. Science Signaling. 2011. doi:10.1126/scisignal.2001935
- Almozlino et al. ANAT 2.0: reconstructing functional protein subnetworks. BMC Bioinformatics. 2017. doi:10.1186/s12859-017-1932-1
References:
- Cerami et al. Automated network analysis identifies core pathways in glioblastoma. PLoS One. 2010. doi:10.1371/journal.pone.0008918
- Liu et al. netboxr: Automated discovery of biological process modules by network analysis in R. PLoS One. 2020. doi:10.1371/journal.pone.0234669
References:
- Yeger-Lotem et al. Bridging high-throughput genetic and transcriptional data reveals cellular responses to alpha-synuclein toxicity. Nature Genetics. 2009. doi:10.1038/ng.337
- Lan et al. ResponseNet: revealing signaling and regulatory networks linking genetic and transcriptomic screening data. Nucleic Acids Research. 2011. doi:10.1093/nar/gkr359
- Basha et al., ResponseNet2.0: revealing signaling and regulatory pathways connecting your proteins and genes–now with human data. Nucleic Acids Research. 2013. doi:10.1093/nar/gkt532
- Basha et al. ResponseNet v.3: revealing signaling and regulatory pathways connecting your proteins and genes across human tissues. Nucleic Acids Research. 2019. doi:10.1093/nar/gkz421
References:
- Huang and Fraenkel. Integrating proteomic, transcriptional, and interactome data reveals hidden components of signaling and regulatory networks. Science Signaling. 2009. doi:10.1126/scisignal.2000350
- Tuncbag et al. Simultaneous reconstruction of multiple signaling pathways via the prize-collecting steiner forest problem. Journal of Computational Biology. 2013. doi:10.1089/cmb.2012.0092
- Gitter et al. Sharing information to reconstruct patient-specific pathways in heterogeneous diseases. Pacific Symposium on Biocomputing. 2014. doi:10.1142/9789814583220_0005
- Tuncbag et al., Network-Based Interpretation of Diverse High-Throughput Datasets through the Omics Integrator Software Package. PLoS Computational Biology. 2016. doi:10.1371/journal.pcbi.1004879
PathLinker takes as input (1) a weighted, directed PPI network, (2) two sets of nodes: a source set (representing receptors of a pathway of interest) and a target set (representing transcriptional regulators of a pathway of interest), and (3) an integer k. PathLinker efficiently computes the k-shortest paths from any source to any target and returns the subnetwork of the top k paths as the pathway reconstruction. Later work expanded PathLinker by incorporating protein localization information to re-score tied paths, dubbed Localized PathLinker (LocPL).
References:
- Ritz et al. Pathways on demand: automated reconstruction of human signaling networks. NPJ Systems Biology and Applications. 2016. doi:10.1038/npjsba.2016.2
- Youssef, Law, and Ritz. Integrating protein localization with automated signaling pathway reconstruction. BMC Bioinformatics. 2019. doi:10.1186/s12859-019-3077-x
References:
- Rubel and Ritz. Augmenting Signaling Pathway Reconstructions. Proceedings of the 11th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics (ACM-BCB '20). 2020. doi:10.1145/3388440.3412411
References:
- Magnano and Gitter. Automating parameter selection to avoid implausible biological pathway models. NPJ Systems Biology and Applications. 2021. doi:10.1038/s41540-020-00167-1