Optimizing Global Network Alignment With a Genetic Algorithm: Leveraging Pre-Trained Embeddings for Protein Sequences and Gene Ontology Terms

Abstract

Multiple objectives have emerged in tuning protein-protein interaction (PPI) networks, such as identifying cross-species network similarities and predicting protein complexes and functions. Despite the proliferation of tuning methodologies, challenges remain in balancing accuracy and efficiency. In this paper, we introduce GA2Vec, a novel approach for globally aligning multiple PPI networks using genetic algorithms in a many-to-many fashion. GA2Vec leverages vector embeddings of protein sequences from ProtBERT, ESM-2, and ProtT5-XL-UniRef50 to reconstruct weighted PPI networks, incorporating functional similarity through Gene Ontology (GO) term embeddings derived from the Anc2vec method. We employ four community detection algorithms to generate candidate clusters from the weighted graph, serving as initial solutions for the genetic algorithm. The genetic algorithm optimizes network alignment by refining these clusters using a fitness function based on similarity scores from pre-trained embeddings and GO terms, achieving a robust global network alignment. We demonstrate the effectiveness of our method through experiments on eukaryotic, prokaryotic, SARS-CoV, and virus-host biological networks. It achieves robust alignment between SARS-CoV-2 and SARS-CoV-1 PPI networks, balancing $F1$, cluster interaction quality ($CIQ$), internal cluster quality ($ICQ$), consistent clusters, and $sensitivity$, with scores reflecting its adaptability to diverse biological contexts.