A Global Network Alignment Method Using Discrete Particle Swarm Optimization.

Area of Science:

• Computational Biology
• Bioinformatics
• Systems Biology

Background:

• Molecular interaction data is growing exponentially, necessitating network-level comparative analysis.
• Global network alignment is crucial for identifying conserved subnetworks and understanding evolutionary relationships across species.
• Network alignment is an NP-hard problem, similar to subgraph isomorphism.

Purpose of the Study:

• To introduce a novel heuristic algorithm, Particle-Swarm-Optimization based Network Aligner (PSONA), for global network alignment.
• To optimize a weighted global alignment model that considers both protein sequence similarity and interaction conservation.
• To enhance the accuracy and functional coherence of network alignment results.

Main Methods:

• PSONA utilizes a heuristic approach based on Particle Swarm Optimization (PSO).
• It redefines particle statuses and updating rules in a discrete form using permutation.
• A seed-and-extend strategy, incorporating high sequence similarity seeding and greedy local search extension, guides the alignment process.

Main Results:

• PSONA demonstrates superior performance compared to several state-of-the-art methods on ten network pairs across five species.
• The algorithm effectively maps proteins with high functional coherence.
• PSONA can refine existing network aligners, acting as a booster for improved results.

Conclusions:

• PSONA offers an effective solution for the NP-hard problem of global network alignment.
• The method enhances functional coherence in cross-species protein mapping.
• PSONA shows potential as a valuable tool for comparative network biology and evolutionary studies.