The DOI matches its Crossref record; 69 of the 69 references it cites were found in a registry or an index.
Græmlin: General and robust alignment of multiple large interaction networks
Open accessAbstract
The recent proliferation of protein interaction networks has motivated research into network alignment: the cross-species comparison of conserved functional modules. Previous studies have laid the foundations for such comparisons and demonstrated their power on a select set of sparse interaction networks. Recently, however, new computational techniques have produced hundreds of predicted interaction networks with interconnection densities that push existing alignment algorithms to their limits. To find conserved functional modules in these new networks, we have developed Græmlin, the first algorithm capable of scalable multiple network alignment. Græmlin's explicit model of functional evolution allows both the generalization of existing alignment scoring schemes and the location of conserved network topologies other than protein complexes and metabolic pathways. To assess Græmlin's performance, we have developed the first quantitative benchmarks for network alignment, which allow comparisons of algorithms in terms of their ability to recapitulate the KEGG database of conserved functional modules. We find that Græmlin achieves substantial scalability gains over previous methods while improving sensitivity.
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
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
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
KEGG: Kyoto Encyclopedia of Genes and Genomes
Kanehisa, M. (2000) · Nucleic Acids Research · doi:10.1093/nar/28.1.27 · Cited by 37,077
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
(2012) · Encyclopedia of the Sciences of Learning · doi:10.1007/978-1-4419-1428-6_5195 · Cited by 19,370
Cluster analysis and display of genome-wide expression patterns
Eisen, M. B., Spellman, P. T., Brown, P. O., & Botstein, D. (1998) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.95.25.14863 · Cited by 16,184
MUSCLE: a multiple sequence alignment method with reduced time and space complexity
Edgar, R. C. (2004) · BMC Bioinformatics · doi:10.1186/1471-2105-5-113 · Cited by 8,970
Network biology: understanding the cell's functional organization
Barabási, A.-L., & Oltvai, Z. N. (2004) · Nature Reviews Genetics · doi:10.1038/nrg1272 · Cited by 7,903
Network motifs: simple building blocks of complex networks.
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002) · Science · doi:10.1126/science.298.5594.824 · Cited by 7,368
Initial sequencing and comparative analysis of the mouse genome
Mouse Genome Sequencing Consortium (2002) · Nature · doi:10.1038/nature01262 · Cited by 7,187
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
Evolutionarily conserved elements in vertebrate, insect, worm, and yeast genomes
Siepel, A., Bejerano, G., Pedersen, J. S., Hinrichs, A. S., Hou, M., Rosenbloom, K., Clawson, H., Spieth, J., Hillier, L. W., Richards, S., et al. (2005) · Genome Research · doi:10.1101/gr.3715005 · Cited by 3,971 · cited 1×
“These diverse application areas were united by perhaps the most important premise of modern biology: the principle that evolutionary conservation implies functional relevance (Bejerano et al. 2004; Cooper et al. 2005; Siepel et al. 2005).”
BackgroundFrom 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
A Genomic Perspective on Protein Families
Tatusov, R. L., Koonin, E. V., & Lipman, D. J. (1997) · Science · doi:10.1126/science.278.5338.631 · Cited by 3,590
Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids
Durbin, R., Eddy, S. R., Krogh, A., & Mitchison, G. (1998) · Cambridge University Press eBooks · doi:10.1017/cbo9780511790492 · Cited by 3,246
International Chicken Genome Sequencing Consortium (2004) · Nature · doi:10.1038/nature03154 · Cited by 2,750
A Gene-Coexpression Network for Global Discovery of Conserved Genetic Modules
Stuart, J. M., Segal, E., Koller, D., & Kim, S. K. (2003) · Science · doi:10.1126/science.1087447 · Cited by 2,256
Boyle, E. I., Weng, S., Gollub, J., Jin, H., Botstein, D., Cherry, J. M., & Sherlock, G. (2004) · Bioinformatics · doi:10.1093/bioinformatics/bth456 · Cited by 2,067
Progressive sequence alignment as a prerequisitetto correct phylogenetic trees
Feng, D.-F., & Doolittle, R. F. (1987) · Journal of Molecular Evolution · doi:10.1007/bf02603120 · Cited by 1,883
Natural engineering principles of electron tunnelling in biological oxidation–reduction
Page, C. C., Moser, C. C., Chen, X., & Dutton, P. L. (1999) · Nature · doi:10.1038/46972 · Cited by 1,872
A Protein Interaction Map of Drosophila melanogaster
Giot, L., Bader, J. S., Brouwer, C., Chaudhuri, A., Kuang, B., Li, Y., Hao, Y. L., Ooi, C. E., Godwin, B., Vitols, E., et al. (2003) · Science · doi:10.1126/science.1090289 · Cited by 1,863
Xenarios, I. (2002) · Nucleic Acids Research · doi:10.1093/nar/30.1.303 · Cited by 1,741
Ultraconserved Elements in the Human Genome
Bejerano, G., Pheasant, M., Makunin, I., Stephen, S., Kent, W. J., Mattick, J. S., & Haussler, D. (2004) · Science · doi:10.1126/science.1098119 · Cited by 1,732
A Map of the Interactome Network of the Metazoan C. elegans
Li, S., Armstrong, C. M., Bertin, N., Ge, H., Milstein, S., Boxem, M., Vidalain, P.-O., Han, J.-D. J., Chesneau, A., Hao, T., et al. (2004) · Science · doi:10.1126/science.1091403 · Cited by 1,628
Assigning protein functions by comparative genome analysis: Protein phylogenetic profiles
Pellegrini, M., Marcotte, E. M., Thompson, M. J., Eisenberg, D., & Yeates, T. O. (1999) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.96.8.4285 · Cited by 1,585
Aligning Multiple Genomic Sequences With the Threaded Blockset Aligner
Blanchette, M., Kent, W. J., Riemer, C., Elnitski, L., Smit, A. F. A., Roskin, K. M., Baertsch, R., Rosenbloom, K., Clawson, H., Green, E. D., et al. (2004) · Genome Research · doi:10.1101/gr.1933104 · Cited by 1,452
THIRTY YEARS OF GRAPH MATCHING IN PATTERN RECOGNITION
CONTE, D., FOGGIA, P., SANSONE, C., & VENTO, M. (2004) · International Journal of Pattern Recognition and Artificial Intelligence · doi:10.1142/s0218001404003228 · Cited by 1,370
Distribution and intensity of constraint in mammalian genomic sequence
Cooper, G. M., Stone, E. A., Asimenos, G., Green, E. D., Batzoglou, S., & Sidow, A. (2005) · Genome Research · doi:10.1101/gr.3577405 · Cited by 1,359
Self-citationShukla, S., Mishra, B., Avashthi, H., & Chandra, M. (2022) · Bioinformatics · doi:10.1016/b978-0-323-89775-4.00003-1 · Cited by 1,244
CDD: a Conserved Domain Database for protein classification
Marchler-Bauer, A. (2004) · Nucleic Acids Research · doi:10.1093/nar/gki069 · Cited by 1,156
LAGAN and Multi-LAGAN: Efficient tools for large-scale multiple alignment of genomic DNA
Brudno, M., Do, C. B., Cooper, G. M., Kim, M. F., Davydov, E., Program, N. C. S., Green, E. D., Sidow, A., & Batzoglou, S. (2003) · Genome Research · doi:10.1101/gr.926603 · Cited by 1,115
Self-citationSCOP database in 2004: refinements integrate structure and sequence family data
Andreeva, A. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh039 · Cited by 909
Toward a functional analysis of the yeast genome through exhaustive two-hybrid screens
Fromont-Racine, M., Rain, J.-C., & Legrain, P. (1997) · Nature Genetics · doi:10.1038/ng0797-277 · Cited by 908
PatternHunter: faster and more sensitive homology search
Ma, B., Tromp, J., & Li, M. (2002) · Bioinformatics · doi:10.1093/bioinformatics/18.3.440 · Cited by 829
Why highly expressed proteins evolve slowly
Drummond, D. A., Bloom, J. D., Adami, C., Wilke, C. O., & Arnold, F. H. (2005) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0504070102 · Cited by 815
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
WormBase: a multi-species resource for nematode biology and genomics
Harris, T. W. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh066 · Cited by 715
A Probabilistic Functional Network of Yeast Genes
Lee, I., Date, S. V., Adai, A. T., & Marcotte, E. M. (2004) · Science · doi:10.1126/science.1099511 · Cited by 690
Dubnau, D. (1999) · Annual Review of Microbiology · doi:10.1146/annurev.micro.53.1.217 · Cited by 600
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 FlyBase database of the Drosophila genome projects and community literature
(2003) · Nucleic Acids Research · doi:10.1093/nar/gkg094 · Cited by 490
Matthews, L. R., Vaglio, P., Reboul, J., Ge, H., Davis, B. P., Garrels, J., Vincent, S., & Vidal, M. (2001) · Genome Research · doi:10.1101/gr.205301 · Cited by 482
Integrating genomic homology into gene structure prediction
Korf, I., Flicek, P., Duan, D., & Brent, M. R. (2001) · Bioinformatics · doi:10.1093/bioinformatics/17.suppl_1.s140 · Cited by 466
Performance evaluation of amino acid substitution matrices
Henikoff, S., & Henikoff, J. G. (1993) · Proteins: Structure, Function, and Bioinformatics · doi:10.1002/prot.340170108 · Cited by 445
Human and Mouse Gene Structure: Comparative Analysis and Application to Exon Prediction
Batzoglou, S., Pachter, L., Mesirov, J. P., Berger, B., & Lander, E. S. (2000) · Genome Research · doi:10.1101/gr.10.7.950 · Cited by 378
Self-citationChristie, K. R. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh033 · Cited by 289
MAVID: Constrained Ancestral Alignment of Multiple Sequences
Bray, N., & Pachter, L. (2004) · Genome Research · doi:10.1101/gr.1960404 · Cited by 284
Human and mouse oligonucleotide-based array CGH
van den IJssel, P. (2005) · Nucleic Acids Research · doi:10.1093/nar/gni191 · Cited by 274
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
Ogata, H. (2000) · Nucleic Acids Research · doi:10.1093/nar/28.20.4021 · Cited by 221
SCORING PAIRWISE GENOMIC SEQUENCE ALIGNMENTS
CHIAROMONTE, F., YAP, V. B., & MILLER, W. (2001) · Biocomputing 2002 · doi:10.1142/9789812799623_0012 · Cited by 214
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
Assessing the limits of genomic data integration for predicting protein networks
Lu, L. J., Xia, Y., Paccanaro, A., Yu, H., & Gerstein, M. (2005) · Genome Research · doi:10.1101/gr.3610305 · Cited by 206
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
Weights for data related by a tree
Altschul, S. F., Carroll, R. J., & Lipman, D. J. (1989) · Journal of Molecular Biology · doi:10.1016/0022-2836(89)90234-9 · Cited by 177
SLAM: Cross-Species Gene Finding and Alignment with a Generalized Pair Hidden Markov Model
Alexandersson, M., Cawley, S., & Pachter, L. (2003) · Genome Research · doi:10.1101/gr.424203 · Cited by 174
The evolution of genetic regulatory systems in bacteria
McAdams, H. H., Srinivasan, B., & Arkin, A. P. (2004) · Nature Reviews Genetics · doi:10.1038/nrg1292 · Cited by 161
Self-citationBloom, J. D., & Adami, C. (2003) · BMC Evolutionary Biology · doi:10.1186/1471-2148-3-21 · Cited by 137
Characterization of Evolutionary Rates and Constraints in Three Mammalian Genomes
Cooper, G. M., Brudno, M., Stone, E. A., Dubchak, I., Batzoglou, S., & Sidow, A. (2004) · Genome Research · doi:10.1101/gr.2034704 · Cited by 134
Self-citationThe many faces of sequence alignment
Batzoglou, S. (2005) · Briefings in Bioinformatics · doi:10.1093/bib/6.1.6 · Cited by 131
Self-citationA simple physical model for scaling in protein-protein interaction networks
Deeds, E. J., Ashenberg, O., & Shakhnovich, E. I. (2005) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0509715102 · Cited by 123
Gollop, N., & March, P. E. (1991) · Journal of Bacteriology · doi:10.1128/jb.173.7.2265-2270.1991 · Cited by 97
Phylogenetic Analysis of Metabolic Pathways
Forst, C. V., & Schulten, K. J. (2001) · Journal of Molecular Evolution · doi:10.1007/s002390010178 · Cited by 90
Designing Multiple Simultaneous Seeds for DNA Similarity Search
Sun, Y., & Buhler, J. D. (2005) · Journal of Computational Biology · doi:10.1089/cmb.2005.12.847 · Cited by 87
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
The conserved exon method for gene finding.
Bafna, V., & Huson, D. H. (2000) · PubMed · Cited by 72
Hara, H., Yasuda, S., HORIUCHI, K., & Park, J. T. (1997) · Journal of Bacteriology · doi:10.1128/jb.179.18.5802-5811.1997 · Cited by 67
Cited by
Network‐based prediction of protein function
Sharan, R., Ulitsky, I., & Shamir, R. (2007) · Molecular Systems Biology · doi:10.1038/msb4100129 · Cited by 1,074
A Survey of Statistical Network Models
Goldenberg, A., Zheng, A. X., Fienberg, S. E., & Airoldi, E. M. (2010) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000005 · Cited by 819
Singh, R., Xu, J., & Berger, B. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0806627105 · Cited by 652
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
Metadata
- Authors
- Flannick, J., Novak, A., Srinivasan, B. S., McAdams, H. H., & Batzoglou, S.
- Venue
- Genome Research
- Publisher
- Cold Spring Harbor Laboratory
- Published
- 2006-08-09
- Volume
- 16
- Issue
- 9
- Pages
- 1169-1181
- ISSN
- 1088-9051 (ISSN-L)
- OpenAlex
- W2171081680
- Cited by
- 320
- References
- 69
- Type
- posted content
- Language
- en
- Open access
- hybrid
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.