The DOI matches its Crossref record; 75 of the 75 references it cites were found in a registry or an index.
Topological network alignment uncovers biological function and phylogeny
Open accessAbstract
Sequence comparison and alignment has had an enormous impact on our understanding of evolution, biology and disease. Comparison and alignment of biological networks will probably have a similar impact. Existing network alignments use information external to the networks, such as sequence, because no good algorithm for purely topological alignment has yet been devised. In this paper, we present a novel algorithm based solely on network topology, that can be used to align any two networks. We apply it to biological networks to produce by far the most complete topological alignments of biological networks to date. We demonstrate that both species phylogeny and detailed biological function of individual proteins can be extracted from our alignments. Topology-based alignments have the potential to provide a completely new, independent source of phylogenetic information. Our alignment of the protein–protein interaction networks of two very different species—yeast and human—indicate that even distant species share a surprising amount of network topology, suggesting broad similarities in internal cellular wiring across all life on Earth.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Basic local alignment search tool
Altschul, S. F., Gish, W., Miller, W., Myers, E. W., & Lipman, D. J. (1990) · Journal of Molecular Biology · doi:10.1006/jmbi.1990.9999 · Cited by 98,669
Gene Ontology: tool for the unification of biology
Ashburner, M., Ball, C. A., Blake, J. A., Botstein, D., Butler, H., Cherry, J. M., Davis, A. P., Dolinski, K., Dwight, S. S., Eppig, J. T., et al. (2000) · Nature Genetics · doi:10.1038/75556 · Cited by 43,206
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060
KEGG: Kyoto Encyclopedia of Genes and Genomes
Kanehisa, M. (2000) · Nucleic Acids Research · doi:10.1093/nar/28.1.27 · Cited by 37,077
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
KEGG: Kyoto Encyclopedia of Genes and Genomes
Ogata, H., Goto, S., Sato, K., Fujibuchi, W., Bono, H., & Kanehisa, M. (1999) · Nucleic Acids Research · doi:10.1093/nar/27.1.29 · Cited by 31,232
Ohno, S. (1970) · doi:10.1007/978-3-642-86659-3 · Cited by 7,833
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385
Lethality and centrality in protein networks
Jeong, H., Mason, S. P., Barabási, A.-L., & Oltvai, Z. N. (2001) · Nature · doi:10.1038/35075138 · Cited by 5,287
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
A comprehensive analysis of protein–protein interactions in Saccharomyces cerevisiae
Uetz, P., Giot, L., Cagney, G., Mansfield, T. A., Judson, R. S., Knight, J. R., Lockshon, D., Narayan, V., Srinivasan, M., Pochart, P., et al. (2000) · Nature · doi:10.1038/35001009 · Cited by 4,706
BioGRID: a general repository for interaction datasets
Stark, C. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkj109 · Cited by 3,960
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
Global landscape of protein complexes in the yeast Saccharomyces cerevisiae
Krogan, N. J., Cagney, G., Yu, H., Zhong, G., Guo, X., Ignatchenko, A., Li, J., Pu, S., Datta, N., Tikuisis, A. P., et al. (2006) · Nature · doi:10.1038/nature04670 · Cited by 2,952
Towards a proteome-scale map of the human protein–protein interaction network
Rual, J.-F., Venkatesan, K., Hao, T., Hirozane-Kishikawa, T., Dricot, A., Li, N., Berriz, G. F., Gibbons, F. D., Dreze, M., Ayivi-Guedehoussou, N., et al. (2005) · Nature · doi:10.1038/nature04209 · Cited by 2,933
A generic protein purification method for protein complex characterization and proteome exploration
Rigaut, G., Shevchenko, A., Rutz, B., Wilm, M., Mann, M., & Séraphin, B. (1999) · Nature Biotechnology · doi:10.1038/13732 · Cited by 2,707
Proteome survey reveals modularity of the yeast cell machinery
Gavin, A.-C., Aloy, P., Grandi, P., Krause, R., Boesche, M., Marzioch, M., Rau, C., Jensen, L. J., Bastuck, S., Dümpelfeld, B., et al. (2006) · Nature · doi:10.1038/nature04532 · Cited by 2,575
A Human Protein-Protein Interaction Network: A Resource for Annotating the Proteome
Stelzl, U., Worm, U., Lalowski, M., Haenig, C., Brembeck, F. H., Goehler, H., Stroedicke, M., Zenkner, M., Schoenherr, A., Koeppen, S., et al. (2005) · Cell · doi:10.1016/j.cell.2005.08.029 · Cited by 2,387
Twilight zone of protein sequence alignments
Rost, B. (1999) · Protein Engineering, Design and Selection · doi:10.1093/protein/12.2.85 · Cited by 1,833
Detecting rich-club ordering in complex networks
Colizza, V., Flammini, A., Serrano, M. A., & Vespignani, A. (2006) · Nature Physics · doi:10.1038/nphys209 · Cited by 1,001
An empirical framework for binary interactome mapping
Venkatesan, K., Rual, J.-F., Vazquez, A., Stelzl, U., Lemmens, I., Hirozane-Kishikawa, T., Hao, T., Zenkner, M., Xin, X., Goh, K.-I., et al. (2009) · Nature Methods · doi:10.1038/nmeth.1280 · Cited by 904
Markov chain Monte Carlo estimation of exponential random graph models
Snijders, T. A. B. (2002) · Journal of Social Structure · Cited by 869
Similar Amino Acid Sequences: Chance or Common Ancestry?
Doolittle, R. F. (1981) · Science · doi:10.1126/science.7280687 · Cited by 843
Biological network comparison using graphlet degree distribution
Pržulj, N. (2007) · Bioinformatics · doi:10.1093/bioinformatics/btl301 · Cited by 837
Self-citationIto, T., Tashiro, K., Muta, S., Ozawa, R., Chiba, T., Nishizawa, M., Yamamoto, K., Kuhara, S., & Sakaki, Y. (2000) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.97.3.1143 · Cited by 814
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
Toward a Comprehensive Atlas of the Physical Interactome of Saccharomyces cerevisiae
Collins, S. R., Kemmeren, P., Zhao, X.-C., Greenblatt, J. F., Spencer, F., Holstege, F. C. P., Weissman, J. S., & Krogan, N. J. (2007) · Molecular & Cellular Proteomics · doi:10.1074/mcp.m600381-mcp200 · Cited by 795
Modeling interactome: scale-free or geometric?
Pržulj, N., Corneil, D. G., & Jurisica, I. (2004) · Bioinformatics · doi:10.1093/bioinformatics/bth436 · Cited by 706
Self-citationHuman protein reference database as a discovery resource for proteomics
Peri, S. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh070 · Cited by 608
The genome of Cryptosporidium hominis
Xu, P., Widmer, G., Wang, Y., Ozaki, L. S., Alves, J. M., Serrano, M. G., Puiu, D., Manque, P., Akiyoshi, D., Mackey, A. J., et al. (2004) · Nature · doi:10.1038/nature02977 · Cited by 563
Subnets of scale-free networks are not scale-free: Sampling properties of networks
Stumpf, M. P. H., Wiuf, C., & May, R. M. (2005) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0501179102 · Cited by 561
Modeling cellular machinery through biological network comparison
Sharan, R., & Ideker, T. (2006) · Nature Biotechnology · doi:10.1038/nbt1196 · Cited by 559
Prediction of protein function from protein sequence and structure
Whisstock, J. C., & Lesk, A. M. (2003) · Quarterly Reviews of Biophysics · doi:10.1017/s0033583503003901 · Cited by 460
Webb, E. C. (1992) · Academic Press eBooks · Cited by 444
Classes of complex networks defined by role-to-role connectivity profiles
Guimerà, R., Sales-Pardo, M., & Amaral, L. A. N. (2007) · Nature Physics · doi:10.1038/nphys489 · Cited by 425
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
IsoRankN: spectral methods for global alignment of multiple protein networks
Liao, C.-S., Lu, K., Baym, M., Singh, R., & Berger, B. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp203 · Cited by 396
Functional Specificity among Ribosomal Proteins Regulates Gene Expression
Komili, S., Farny, N. G., Roth, F. P., & Silver, P. A. (2007) · Cell · doi:10.1016/j.cell.2007.08.037 · Cited by 390
A new sequence distance measure for phylogenetic tree construction
Otu, H. H., & Sayood, K. (2003) · Bioinformatics · doi:10.1093/bioinformatics/btg295 · Cited by 348
Effect of sampling on topology predictions of protein-protein interaction networks
Han, J.-D. J., Dupuy, D., Bertin, N., Cusick, M. E., & Vidal, M. (2005) · Nature Biotechnology · doi:10.1038/nbt1116 · Cited by 344
Græmlin: General and robust alignment of multiple large interaction networks
Flannick, J., Novak, A., Srinivasan, B. S., McAdams, H. H., & Batzoglou, S. (2006) · Genome Research · doi:10.1101/gr.5235706 · Cited by 320
Predicting protein function from sequence and structural data
Watson, J. D., Laskowski, R. A., & Thornton, J. M. (2005) · Current Opinion in Structural Biology · doi:10.1016/j.sbi.2005.04.003 · Cited by 315
Evidence from Beta-Tubulin Phylogeny that Microsporidia Evolved from Within the Fungi
Keeling, P. J., Luker, M. A., & Palmer, J. D. (2000) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a026235 · Cited by 302
Empirically controlled mapping of the Caenorhabditis elegans protein-protein interactome network
Simonis, N., Rual, J.-F., Carvunis, A.-R., Tasan, M., Lemmens, I., Hirozane-Kishikawa, T., Hao, T., Sahalie, J. M., Venkatesan, K., Gebreab, F., et al. (2009) · Nature Methods · doi:10.1038/nmeth.1279 · Cited by 302
Uncovering Biological Network Function via Graphlet Degree SignaturesPreprint
Milenković, T., & Pržulj, N. (2008) · Europe PMC (PubMed Central) · doi:10.48550/arxiv.0802.0556 · Cited by 295
Self-citationPairwise Global Alignment of Protein Interaction Networks by Matching Neighborhood Topology
Singh, R., Xu, J., & Berger, B. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-71681-5_2 · Cited by 286
Uncovering Biological Network Function via Graphlet Degree Signatures
Milenković, T., & Pržulj, N. (2008) · Cancer Informatics · doi:10.4137/cin.s680 · Cited by 278
Self-citationPairwise Alignment of Protein Interaction Networks
Koyutürk, M., Kim, Y., Topkara, U., Subramaniam, S., Szpankowski, W., & Grama, A. (2006) · Journal of Computational Biology · doi:10.1089/cmb.2006.13.182 · Cited by 268
Complex Spliceosomal Organization Ancestral to Extant Eukaryotes
Collins, L., & Penny, D. (2005) · Molecular Biology and Evolution · doi:10.1093/molbev/msi091 · Cited by 240
Web Services at the European Bioinformatics Institute
Labarga, A., Valentin, F., Anderson, M., & Lopez, R. (2007) · Nucleic Acids Research · doi:10.1093/nar/gkm291 · Cited by 237
Local graph alignment and motif search in biological networks
Berg, J., & Lässig, M. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0305199101 · Cited by 218
An integrated approach to inferring gene–disease associations in humans
Radivojac, P., Peng, K., Clark, W. T., Peters, B. J., Mohan, A., Boyle, S. M., & Mooney, S. D. (2008) · Proteins: Structure, Function, and Bioinformatics · doi:10.1002/prot.21989 · Cited by 175
Global alignment of protein–protein interaction networks by graph matching methods
Zaslavskiy, M., Bach, F., & Vert, J.-P. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp196 · Cited by 163
Deriving phylogenetic trees from the similarity analysis of metabolic pathways
Heymans, M., & Singh, A. K. (2003) · Bioinformatics · doi:10.1093/bioinformatics/btg1018 · Cited by 154
Fitting a geometric graph to a protein–protein interaction network
Higham, D. J., Rašajski, M., & Pržulj, N. (2008) · Bioinformatics · doi:10.1093/bioinformatics/btn079 · Cited by 153
Self-citationCross-species analysis of biological networks by Bayesian alignment
Berg, J., & Lässig, M. (2006) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0602294103 · Cited by 146
Efficient estimation of graphlet frequency distributions in protein–protein interaction networks
Pržulj, N., Corneil, D. G., & Jurišica, I. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl030 · Cited by 134
Self-citationThe Plasmodium protein network diverges from those of other eukaryotes
Suthram, S., Sittler, T., & Ideker, T. (2005) · Nature · doi:10.1038/nature04135 · Cited by 134
Sequence‐similar, structure‐dissimilar protein pairs in the PDB
Kosloff, M., & Kolodny, R. (2008) · Proteins: Structure, Function, and Bioinformatics · doi:10.1002/prot.21770 · Cited by 124
GraphCrunch: A tool for large network analyses
Milenković, T., Lai, J., & Pržulj, N. (2008) · BMC Bioinformatics · doi:10.1186/1471-2105-9-70 · Cited by 118
Self-citationAutomatic Parameter Learning for Multiple Local Network Alignment
Flannick, J. A., Novak, A. F., Do, C. B., Srinivasan, B. S., & Batzoglou, S. (2009) · Journal of Computational Biology · doi:10.1089/cmb.2009.0099 · Cited by 95
Phylogenetic Analysis of Metabolic Pathways
Forst, C. V., & Schulten, K. J. (2001) · Journal of Molecular Evolution · doi:10.1007/s002390010178 · Cited by 90
Automatic Parameter Learning for Multiple Network Alignment
Flannick, J. A., Novak, A. F., Do, C. B., Srinivasan, B. S., & Batzoglou, S. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-78839-3_19 · Cited by 87
Modelling protein–protein interaction networks via a stickiness index
Pržulj, N., & Higham, D. J. (2006) · Journal of The Royal Society Interface · doi:10.1098/rsif.2006.0147 · Cited by 85
Self-citationThe effects of incomplete protein interaction data on structural and evolutionary inferences
de Silva, E., Thorne, T., Ingram, P. J., Agrafioti, I., Swire, J. S., Wiuf, C., & Stumpf, M. P. H. (2006) · BMC Biology · doi:10.1186/1741-7007-4-39 · Cited by 68
GLOBAL ALIGNMENT OF MULTIPLE PROTEIN INTERACTION NETWORKS
Singh, R., Xu, J., & Berger, B. (2007) · Pacific Symposium on Biocomputing (PSB) · doi:10.1142/9789812776136_0030 · Cited by 67
Agrafioti, I., Swire, J. S., Abbott, J., Huntley, D. M., Butcher, S., & Stumpf, M. P. H. (2005) · BMC Evolutionary Biology · doi:10.1186/1471-2148-5-23 · Cited by 66
Optimized Null Model for Protein Structure Networks
Milenković, T., Filippis, I., Lappé, M., & Pržulj, N. (2009) · PLoS ONE · doi:10.1371/journal.pone.0005967 · Cited by 50
Self-citationLaurents, D. V., Subbiah, S., & Levitt, M. (1994) · Protein Science · doi:10.1002/pro.5560031105 · Cited by 40
Complementarity of network and sequence information in homologous proteins
Memišević, V., Milenković, T., & Pržulj, N. (2010) · Berichte aus der medizinischen Informatik und Bioinformatik/Journal of integrative bioinformatics · doi:10.1515/jib-2010-135 · Cited by 39
Self-citationStructure of brain functional networks
Kuchaiev, O., Wang, P. T., Nenadic, Z., & Przulj, N. (2009) · Annual International Conference of the IEEE Engineering in Medicine and Biology Society · doi:10.1109/iembs.2009.5333938 · Cited by 37
Self-citationA high-throughput assay for Tn5 Tnp-induced DNA cleavage
Ason, B. L. (2004) · Nucleic Acids Research · doi:10.1093/nar/gnh080 · Cited by 34
Generating confidence intervals on biological networks
Thorne, T., & Stumpf, M. P. H. (2007) · BMC Bioinformatics · doi:10.1186/1471-2105-8-467 · Cited by 27
LEARNING THE STRUCTURE OF PROTEIN-PROTEIN INTERACTION NETWORKS
Kuchaiev, O., & Pržulj, N. (2008) · Pacific Symposium on Biocomputing (PSB) · doi:10.1142/9789812836939_0005 · Cited by 17
Self-citation
Cited by
Comparing methods for comparing networks
Tantardini, M., Ieva, F., Tajoli, L., & Piccardi, C. (2019) · Scientific Reports · doi:10.1038/s41598-019-53708-y · Cited by 264
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
Integrative network alignment reveals large regions of global network similarity in yeast and human
Kuchaiev, O., & Pržulj, N. (2011) · Bioinformatics · doi:10.1093/bioinformatics/btr127 · Cited by 256
Self-citationGaiteri, C., Chen, M., Szymanski, B., Kuzmin, K., Xie, J., Lee, C., Blanche, T., Chaibub Neto, E., Huang, S.-C., Grabowski, T., et al. (2015) · Scientific Reports · doi:10.1038/srep16361 · Cited by 76
Systems biology perspectives on minimal and simpler cells
Xavier, J. C., Patil, K. R., & Rocha, I. (2014) · Microbiology and Molecular Biology Reviews · doi:10.1128/mmbr.00050-13 · Cited by 58
Metadata
- Authors
- Kuchaiev, O., Milenković, T., Memišević, V., Hayes, W., & Pržulj, N.
- Venue
- Journal of The Royal Society Interface
- Publisher
- The Royal Society
- Published
- 2010-03-24
- Volume
- 7
- Issue
- 50
- Pages
- 1341-1354
- ISSN
- 1742-5662 (ISSN-L)
- 1742-5689
- OpenAlex
- W2130237248
- Cited by
- 355
- References
- 75
- FWCI
- 9.33
- Type
- journal article
- Language
- en
- Open access
- green
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.