The DOI matches its Crossref record; 52 of the 52 references it cites were found in a registry or an index.
Pairwise Alignment of Protein Interaction Networks
Abstract
With an ever-increasing amount of available data on protein-protein interaction (PPI) networks and research revealing that these networks evolve at a modular level, discovery of conserved patterns in these networks becomes an important problem. Although available data on protein-protein interactions is currently limited, recently developed algorithms have been shown to convey novel biological insights through employment of elegant mathematical models. The main challenge in aligning PPI networks is to define a graph theoretical measure of similarity between graph structures that captures underlying biological phenomena accurately. In this respect, modeling of conservation and divergence of interactions, as well as the interpretation of resulting alignments, are important design parameters. In this paper, we develop a framework for comprehensive alignment of PPI networks, which is inspired by duplication/divergence models that focus on understanding the evolution of protein interactions. We propose a mathematical model that extends the concepts of match, mismatch, and gap in sequence alignment to that of match, mismatch, and duplication in network alignment and evaluates similarity between graph structures through a scoring function that accounts for evolutionary events. By relying on evolutionary models, the proposed framework facilitates interpretation of resulting alignments in terms of not only conservation but also divergence of modularity in PPI networks. Furthermore, as in the case of sequence alignment, our model allows flexibility in adjusting parameters to quantify underlying evolutionary relationships. Based on the proposed model, we formulate PPI network alignment as an optimization problem and present fast algorithms to solve this problem. Detailed experimental results from an implementation of the proposed framework show that our algorithm is able to discover conserved interaction patterns very effectively, in terms of both accuracies and computational cost.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Gapped BLAST and PSI-BLAST: a new generation of protein database search programs
Altschul, S. (1997) · Nucleic Acids Research · doi:10.1093/nar/25.17.3389 · Cited by 73,302
Thompson, J. D., Higgins, D. G., & Gibson, T. J. (1994) · Nucleic Acids Research · doi:10.1093/nar/22.22.4673 · Cited by 64,617
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
Identification of common molecular subsequences
Smith, T. F., & Waterman, M. S. (1981) · Journal of Molecular Biology · doi:10.1016/0022-2836(81)90087-5 · Cited by 9,940
Massagué, J. (1998) · Annual Review of Biochemistry · doi:10.1146/annurev.biochem.67.1.753 · Cited by 7,556
An automated method for finding molecular complexes in large protein interaction networks
Bader, G. D., & Hogue, C. W. (2003) · BMC Bioinformatics · doi:10.1186/1471-2105-4-2 · Cited by 6,072
An Efficient Heuristic Procedure for Partitioning Graphs
Kernighan, B. W., & Lin, S. (1970) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1970.tb01770.x · Cited by 5,305
Functional organization of the yeast proteome by systematic analysis of protein complexes
Gavin, A.-C., Bösche, M., Krause, R., Grandi, P., Marzioch, M., Bauer, A., Schultz, J., Rick, J. M., Michon, A.-M., Cruciat, C.-M., et al. (2002) · Nature · doi:10.1038/415141a · Cited by 4,759
The COG database: a tool for genome-scale analysis of protein functions and evolution
Tatusov, R. L. (2000) · Nucleic Acids Research · doi:10.1093/nar/28.1.33 · Cited by 4,520
From molecular to modular cell biology.
Hartwell, L. H., Hopfield, J. J., Leibler, S., & Murray, A. W. (1999) · Nature · doi:10.1038/35011540 · Cited by 3,632
Systematic identification of protein complexes in Saccharomyces cerevisiae by mass spectrometry
Ho, Y., Gruhler, A., Heilbut, A., Bader, G. D., Moore, L., Adams, S.-L., Millar, A., Taylor, P., Bennett, K., Boutilier, K., et al. (2002) · Nature · doi:10.1038/415180a · Cited by 3,601
A comprehensive two-hybrid analysis to explore the yeast protein interactome
Ito, T., Chiba, T., Ozawa, R., Yoshida, M., Hattori, M., & Sakaki, Y. (2001) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.061034498 · Cited by 3,566
Structure of 20S proteasome from yeast at 2.4Å resolution
Groll, M., Ditzel, L., Löwe, J., Stock, D., Bochtler, M., Bartunik, H. D., & Huber, R. (1997) · Nature · doi:10.1038/386463a0 · Cited by 2,257
Xenarios, I. (2002) · Nucleic Acids Research · doi:10.1093/nar/30.1.303 · Cited by 1,741
BIND--The Biomolecular Interaction Network Database
Bader, G. D. (2001) · Nucleic Acids Research · doi:10.1093/nar/29.1.242 · Cited by 1,560
A Bayesian Networks Approach for Predicting Protein-Protein Interactions from Genomic Data
Jansen, R., Yu, H., Greenbaum, D., Kluger, Y., Krogan, N. J., Chung, S., Emili, A., Snyder, M., Greenblatt, J. F., & Gerstein, M. (2003) · Science · doi:10.1126/science.1087361 · Cited by 1,254
Automatic clustering of orthologs and in-paralogs from pairwise species comparisons
Remm, M., Storm, C. E. V., & Sonnhammer, E. L. L. (2001) · Journal of Molecular Biology · doi:10.1006/jmbi.2000.5197 · Cited by 1,174
DIP: the Database of Interacting Proteins
Xenarios, I. (2000) · Nucleic Acids Research · doi:10.1093/nar/28.1.289 · Cited by 1,123
Evolutionary Rate in the Protein Interaction Network
Fraser, H. B., Hirsh, A. E., Steinmetz, L. M., Scharfe, C., & Feldman, M. W. (2002) · Science · doi:10.1126/science.1068696 · Cited by 869
Conserved patterns of protein interaction in multiple species
Sharan, R., Suthram, S., Kelley, R. M., Kuhn, T., McCuine, S., Uetz, P., Sittler, T., Karp, R. M., & Ideker, T. (2005) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0409522102 · Cited by 796
Feige, U., Peleg, D., & Kortsarz, G. (2001) · Algorithmica · doi:10.1007/s004530010050 · Cited by 592
Yeger-Lotem, E., Sattath, S., Kashtan, N., Itzkovitz, S., Milo, R., Pinter, R. Y., Alon, U., & Margalit, H. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0306752101 · Cited by 536
Conserved pathways within bacteria and yeast as revealed by global protein network alignment
Kelley, B. P., Sharan, R., Karp, R. M., Sittler, T., Root, D. E., Stockwell, B. R., & Ideker, T. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1534710100 · Cited by 529
The Yeast Protein Interaction Network Evolves Rapidly and Contains Few Redundant Duplicate Genes
Wagner, A. (2001) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a003913 · Cited by 521
Spectra of random graphs with given expected degrees
Chung, F., Lu, L., & Vu, V. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0937490100 · Cited by 492
Modeling of Protein Interaction Networks
Vázquez, A., Flammini, A., Maritan, A., & Vespignani, A. (2003) · Complexus · doi:10.1159/000067642 · Cited by 472
Evolutionary conservation of motif constituents in the yeast protein interaction network
Wuchty, S., Oltvai, Z. N., & Barabási, A.-L. (2003) · Nature Genetics · doi:10.1038/ng1242 · Cited by 440
Evolving protein interaction networks through gene duplication
Pastor-Satorras, R., Smith, E., & Solé, R. V. (2003) · Journal of Theoretical Biology · doi:10.1016/s0022-5193(03)00028-6 · Cited by 429
PathBLAST: a tool for alignment of protein interaction networks
Kelley, B. P., Yuan, B., Lewitter, F., Sharan, R., Stockwell, B. R., & Ideker, T. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh411 · Cited by 420
Mining coherent dense subgraphs across massive biological networks for functional discovery
Hu, H., Yan, X., Huang, Y., Han, J., & Zhou, X. J. (2005) · Bioinformatics · doi:10.1093/bioinformatics/bti1049 · Cited by 333
Duplication Models for Biological Networks
Chung, F., Lu, L., Dewey, T. G., & Galas, D. J. (2003) · Journal of Computational Biology · doi:10.1089/106652703322539024 · Cited by 322
How the global structure of protein interaction networks evolves
Wagner, A. (2003) · Proceedings of the Royal Society of London. Series B: Biological Sciences · doi:10.1098/rspb.2002.2269 · Cited by 266
Pathway alignment: application to the comparative analysis of glycolytic enzymes
Dandekar, T., Schuster, S., Snel, ., Huynen, M. A., & Peer Bork, B. (1999) · Biochemical Journal · doi:10.1042/0264-6021:3430115 · Cited by 256
Subunit interaction maps for the regulatory particle of the 26S proteasome and the COP9 signalosome
Fu, H. (2001) · The EMBO Journal · doi:10.1093/emboj/20.24.7096 · Cited by 247
Preferential Attachment in the Protein Network Evolution
Eisenberg, E., & Levanon, E. Y. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.138701 · Cited by 224
Alignment of metabolic pathways
Pinter, R. Y., Rokhlenko, O., Yeger-Lotem, E., & Ziv-Ukelson, M. (2005) · Bioinformatics · doi:10.1093/bioinformatics/bti554 · Cited by 214
Berg, J., Lässig, M., & Wagner, A. (2004) · BMC Evolutionary Biology · doi:10.1186/1471-2148-4-51 · Cited by 198
Functional modules by relating protein interaction networks and gene expression
Tornow, S. (2003) · Nucleic Acids Research · doi:10.1093/nar/gkg838 · Cited by 195
Sharan, R., Ideker, T., Kelley, B., Shamir, R., & Karp, R. M. (2005) · Journal of Computational Biology · doi:10.1089/cmb.2005.12.835 · Cited by 194
Predicting Protein Complex Membership Using Probabilistic Network Reliability
Asthana, S., King, O. D., Gibbons, F. D., & Roth, F. P. (2004) · Genome Research · doi:10.1101/gr.2203804 · Cited by 190
Approximation algorithms for maximum dispersion
Hassin, R., Rubinstein, S., & Tamir, A. (1997) · Operations Research Letters · doi:10.1016/s0167-6377(97)00034-5 · Cited by 186
An efficient algorithm for detecting frequent subgraphs in biological networks
Koyutürk, M., Grama, A. Y., & Szpankowski, W. (2004) · Bioinformatics · doi:10.1093/bioinformatics/bth919 · Cited by 182
Self-citationGenetic Analysis of Calmodulin and Its Targets in Saccharomyces cerevisiae
Cyert, M. S. (2001) · Annual Review of Genetics · doi:10.1146/annurev.genet.35.102401.091302 · Cited by 174
Evolution and Topology in the Yeast Protein Interaction NetworkPreprint
Wuchty, S. (2004) · Genome Research · doi:10.1101/gr.2300204 · Cited by 138
What do we learn from high-throughput protein interaction data?
Titz, B., Schlesner, M., & Uetz, P. (2004) · Expert Review of Proteomics · doi:10.1586/14789450.1.1.111 · Cited by 107
Evolution of the yeast protein interaction network
Qin, H. H., Lu, H. H., Wu, W. B., & Li, W. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2235584100 · Cited by 74
Local modeling of global interactome networks
Scholtens, D. M., Vidal, M., & Gentleman, R. C. (2005) · Computer applications in the biosciences · doi:10.1093/bioinformatics/bti567 · Cited by 73
Pairwise Local Alignment of Protein Interaction Networks Guided by Models of Evolution
Koyutürk, M., Grama, A. Y., & Szpankowski, W. (2005) · Lecture notes in computer science · doi:10.1007/11415770_4 · Cited by 73
Self-citationFunctional Evolution of the Yeast Protein Interaction Network
Kunin, V., Pereira-Leal Jose, B., & Ouzounis, C. (2004) · Molecular Biology and Evolution · doi:10.1093/molbev/msh085 · Cited by 68
Greedily building protein networks with confidence
Bader, J. S. (2003) · Bioinformatics · doi:10.1093/bioinformatics/btg358 · Cited by 64
A statistical framework for combining and interpreting proteomic datasets
Gilchrist, M. A., Kubatko, L. S., & Wagner, A. (2004) · Bioinformatics · doi:10.1093/bioinformatics/btg469 · Cited by 62
A high-throughput assay for Tn5 Tnp-induced DNA cleavage
Ason, B. L. (2004) · Nucleic Acids Research · doi:10.1093/nar/gnh080 · Cited by 34
Cited by
Protein-to-protein interactions: Technologies, databases, and algorithms
Cannataro, M., Guzzi, P. H., & Veltri, P. (2010) · ACM Computing Surveys · doi:10.1145/1824795.1824796 · Cited by 620
Integrative approaches for finding modular structure in biological networks
Mitra, K., Carvunis, A.-R., Ramesh, S. K., & Ideker, T. (2013) · Nature Reviews Genetics · doi:10.1038/nrg3552 · Cited by 535
Topological network alignment uncovers biological function and phylogeny
Kuchaiev, O., Milenković, T., Memišević, V., Hayes, W., & Pržulj, N. (2010) · Journal of The Royal Society Interface · doi:10.1098/rsif.2010.0063 · Cited by 355
Computational solutions for omics data
Berger, B., Peng, J., & Singh, M. (2013) · Nature Reviews Genetics · doi:10.1038/nrg3433 · Cited by 346
A Guide to Conquer the Biological Network Era Using Graph Theory
Koutrouli, M., Karatzas, E., Paez-Espino, D., & Pavlopoulos, G. A. (2020) · Frontiers in Bioengineering and Biotechnology · doi:10.3389/fbioe.2020.00034 · Cited by 264
Metadata
- Authors
- Koyutürk, M., Kim, Y., Topkara, U., Subramaniam, S., Szpankowski, W., & Grama, A.
- Venue
- Journal of Computational Biology
- Publisher
- SAGE Publications
- Published
- 2006-03
- Volume
- 13
- Issue
- 2
- Pages
- 182-199
- ISSN
- 1066-5277 (ISSN-L)
- 1557-8666
- OpenAlex
- W1984209790
- Cited by
- 268
- References
- 52
- FWCI
- 6.02
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.