The DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.
Integrative network alignment reveals large regions of global network similarity in yeast and human
Open accessAbstract
Motivation: High-throughput methods for detecting molecular interactions have produced large sets of biological network data with much more yet to come. Analogous to sequence alignment, efficient and reliable network alignment methods are expected to improve our understanding of biological systems. Unlike sequence alignment, network alignment is computationally intractable. Hence, devising efficient network alignment heuristics is currently a foremost challenge in computational biology. Results: We introduce a novel network alignment algorithm, called Matching-based Integrative GRAph ALigner (MI-GRAAL), which can integrate any number and type of similarity measures between network nodes (e.g. proteins), including, but not limited to, any topological network similarity measure, sequence similarity, functional similarity and structural similarity. Hence, we resolve the ties in similarity measures and find a combination of similarity measures yielding the largest contiguous (i.e. connected) and biologically sound alignments. MI-GRAAL exposes the largest functional, connected regions of protein–protein interaction (PPI) network similarity to date: surprisingly, it reveals that 77.7% of proteins in the baker's yeast high-confidence PPI network participate in such a subnetwork that is fully contained in the human high-confidence PPI network. This is the first demonstration that species as diverse as yeast and human contain so large, continuous regions of global network similarity. We apply MI-GRAAL's alignments to predict functions of un-annotated proteins in yeast, human and bacteria validating our predictions in the literature. Furthermore, using network alignment scores for PPI networks of different herpes viruses, we reconstruct their phylogenetic relationship. This is the first time that phylogeny is exactly reconstructed from purely topological alignments of PPI networks. Availability: Supplementary files and MI-GRAAL executables: http://bio-nets.doc.ic.ac.uk/MI-GRAAL/. Contact: natasha@imperial.ac.uk Supplementary information: Supplementary data are available at Bioinformatics online.
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
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
PHYLIP-Phylogeny inference package (Version 3.2)
Felsenstein, J. (1989) · Cladistics · Cited by 17,682
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
(2010) · Introduction to Combinatorics · doi:10.1201/b12336-12 · Cited by 5,632
Fields, J. (2001) · Cited by 4,044
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
PHYLIP ( PHYLogeny Inference Package)
Cummings, M. P. (2004) · Dictionary of Bioinformatics and Computational Biology · doi:10.1002/9780471650126.dob0534.pub2 · Cited by 3,127
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
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
Superfamilies of Evolved and Designed Networks
Milo, R., Itzkovitz, S., Kashtan, N., Levitt, R., Shen-Orr, S., Ayzenshtat, I., Sheffer, M., & Alon, U. (2004) · Science · doi:10.1126/science.1089167 · Cited by 1,412
(2023) · WORLD SCIENTIFIC eBooks · doi:10.1142/9789811273117_0001 · Cited by 885
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
Topics in herpesvirus genomics and evolution
McGeoch, D. J., Rixon, F. J., & Davison, A. J. (2006) · Virus Research · doi:10.1016/j.virusres.2006.01.002 · Cited by 544
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
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
Self-citationGræ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
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
A proteome-wide protein interaction map for Campylobacter jejuni
Parrish, J. R., Yu, J., Liu, G., Hines, J. A., Chan, J. E., Mangiola, B. A., Zhang, H., Pacifico, S., Fotouhi, F., DiRita, V. J., et al. (2007) · Genome Biology · doi:10.1186/gb-2007-8-7-r130 · Cited by 237
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
A new graph-based method for pairwise global network alignment
Klau, G. W. (2009) · BMC Bioinformatics · doi:10.1186/1471-2105-10-s1-s59 · Cited by 230
Optimal Network Alignment with Graphlet Degree Vectors
Milenković, T., Ng, W. L., Hayes, W., & PržUlj, N. (2010) · Cancer Informatics · doi:10.4137/cin.s4744 · Cited by 193
Self-citationEvolutionarily Conserved Herpesviral Protein Interaction Networks
Fossum, E., Friedel, C. C., Rajagopala, S. V., Titz, B., Baiker, A., Schmidt, T., Kraus, T., Stellberger, T., Rutenberg, C., Suthram, S., et al. (2009) · PLoS Pathogens · doi:10.1371/journal.ppat.1000570 · Cited by 177
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
A Large-scale Protein–protein Interaction Analysis in Synechocystis sp. PCC6803
Sato, S., Shimoda, Y., Muraki, A., Kohara, M., Nakamura, Y., & Tabata, S. (2007) · DNA Research · doi:10.1093/dnares/dsm021 · Cited by 169
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
Integrating Reptilian Herpesviruses into the Family Herpesviridae
McGeoch, D. J., & Gatherer, D. (2004) · Journal of Virology · doi:10.1128/jvi.79.2.725-731.2005 · Cited by 138
Automatic 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
The Modular Organization of Protein Interactions in Escherichia coli
Peregrín-Alvarez, J. M., Xiong, X., Su, C., & Parkinson, J. (2009) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000523 · Cited by 93
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
Shimoda, Y., Shinpo, S., Kohara, M., Nakamura, Y., Tabata, S., & Sato, S. (2008) · DNA Research · doi:10.1093/dnares/dsm028 · Cited by 79
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 56
LOCAL OPTIMIZATION FOR GLOBAL ALIGNMENT OF PROTEIN INTERACTION NETWORKS
Chindelevitch, L., Liao, C.-S., & Berger, B. (2009) · WORLD SCIENTIFIC eBooks · doi:10.1142/9789814295291_0015 · Cited by 41
Cited by
Structure and dynamics of molecular networks: A novel paradigm of drug discovery
Csermely, P., Korcsmáros, T., Kiss, H. J. M., London, G., & Nussinov, R. (2013) · Pharmacology & Therapeutics · doi:10.1016/j.pharmthera.2013.01.016 · Cited by 892
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
Metadata
- Authors
- Kuchaiev, O., & Pržulj, N.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2011-03-16
- Volume
- 27
- Issue
- 10
- Pages
- 1390-1396
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2137648512
- Cited by
- 256
- References
- 40
- FWCI
- 9.29
- Type
- journal article
- Language
- en
- Open access
- bronze
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.