Scalable global alignment for multiple biological networks

Yu-Keng Shih, Srinivasan ParthasarathyBMC Bioinformatics 2012 · DOI

TL;DR

This paper introduces a novel, scalable algorithm for aligning multiple biological networks (specifically protein-protein interaction networks). Their method significantly outperforms existing state-of-the-art approaches in both the quality of functional ortholog identification and computational efficiency, offering a substantial speedup.

What Problem Does This Paper Address?

Understanding how biological functions are conserved across different species is crucial for deciphering evolutionary processes and identifying disease mechanisms. Protein-protein interaction (PPI) networks are a powerful way to represent these biological systems. However, aligning these networks across multiple species to find conserved functional modules (groups of proteins that perform similar functions) is a computationally challenging task. Existing "global alignment" methods aim to map most proteins across networks, but they struggle with scalability, especially when dealing with many large networks. This paper tackles the problem of efficiently and accurately performing global alignment for multiple PPI networks simultaneously.

Methods

The authors propose a four-stage algorithm:

  1. Preprocessing: They first enhance the sequence similarity matrix by incorporating a measure of shared neighbors. This step aims to prioritize aligning proteins that not only have similar sequences but also interact with similar partners, hinting at conserved functional roles.
  2. Clustering: Proteins are clustered based on their (preprocessed) similarity. They opt for hierarchical clustering, finding it more suitable for generating globular clusters that balance scalability and the ability to capture diverse protein groups.
  3. Seed Generation: Clusters are used to generate initial "seed" match-sets. These seeds are pairs of proteins with high similarity, forming the starting point for alignment.
  4. Seed Expansion and Merging: This is the core of their novel approach.
  5. Seed Expansion (Algorithm 2): Seeds are expanded by iteratively adding neighboring proteins that maintain high similarity. This is managed using a priority queue to always select the most promising pair, aiming to conserve edges and thus network topology.
  6. Merging Match-sets (Algorithm 3): A sophisticated merging criterion is introduced to combine existing match-sets. This criterion balances the size of the merged set, the similarity of proteins within it, and the "expand ratio" (how many new species are brought into the match-set). This allows for the formation of match-sets that span multiple networks.
  7. Aligning Remaining Proteins (Stage 4): Any proteins not yet aligned are then considered, prioritizing those with the highest similarity, and the merging criterion is applied again.

The key novelty lies in the independent yet sequential consideration of sequence similarity (via clustering and seed generation) and network topology (via seed expansion and merging), combined with a robust merging strategy that allows for multi-network alignments.

Datasets

The authors evaluated their algorithm on three real biological datasets:

  • DOMAIN: A subset of an older DIP dataset, requiring proteins to have at least one domain. Similarity is calculated using domain information and Pfam p-values.
  • DIP (Database of Interacting Proteins): A standard PPI database. Similarity is measured using normalized BLAST bit scores.
  • BioGRID (Biological General Repository for Interaction Datasets): Another comprehensive PPI database. Similarity is also measured using normalized BLAST bit scores.

They extracted proteins with FASTA sequences from these datasets to compute similarity scores.

Key Insights and Ideas

  • Balancing Sequence Similarity and Network Topology: The paper highlights the inherent trade-off between aligning similar sequences and preserving network structure. Their approach tackles this by first focusing on sequence similarity (clustering) and then progressively incorporating topology (seed expansion and merging).
  • The Power of "Seed" Expansion: Starting with highly similar protein pairs (seeds) and expanding outwards using a priority queue is an efficient way to discover conserved interactions and build comprehensive alignments.
  • Multi-Network Merging is Crucial: Simply aligning pairs of networks is insufficient. Their merging criterion, which considers multiple factors, is key to forming biologically meaningful match-sets that span across several species.
  • Preprocessing Enhances Alignment: Incorporating neighbor similarity into the initial similarity matrix before clustering significantly improves the quality of the resulting alignments.
  • Scalability is Paramount: Existing methods struggle with the sheer volume of biological data. This paper's focus on a scalable algorithm is a critical advancement.

Key Results

  • Significant Speedup: The proposed method is 50x to 500x faster than the state-of-the-art IsoRankN algorithm on the tested datasets. This is attributed to IsoRankN's iterative matrix updates versus their approach of performing preprocessing and clustering only once.
  • Improved Alignment Quality:
    • Coverage: Their method achieves higher coverage (more proteins aligned) compared to IsoRankN.
  • Functional Relevance: They demonstrate this through lower p-values for enriched GO terms, indicating more biologically meaningful functional orthologs.
  • Comprehensive Alignments: Qualitative analysis shows their method finds more functionally consistent and comprehensive alignments.
  • Trade-off Analysis: Figure 3 illustrates the trade-off between average similarity score and conserved edge rate for different clustering methods and parameters, showing that their agglomerative method generally yields better conserved edge rates for a given similarity score.
  • Preprocessing Benefit: The number of strictly conserved edges increased significantly with their preprocessing step.

Limitations and Future Work

  • Weighted PPI Networks: The current work does not explicitly consider weighted PPI networks, where edges have confidence scores. The authors suggest investigating GNA with weighted interactions as a future direction.
  • Future Work: They propose exploring graph clustering algorithms as an alternative starting point and integrating similarity scores with interaction confidence.

Summary updated

BibTeX
@article{shih2012scalable,
  author = {Yu-Keng Shih and Srinivasan Parthasarathy},
  title = {{Scalable global alignment for multiple biological networks}},
  journal = {BMC Bioinformatics},
  year = {2012},
  doi = {10.1186/1471-2105-13-s3-s11},
}
Figure