Algorithms for matching partially labelled sequence graphs

Area of Science:

• Bioinformatics
• Computational Biology
• Evolutionary Biology

Background:

• Predicting protein-protein interactions is crucial for understanding biological processes.
• Matching interacting protein sequences, especially paralogs within species, is challenging in eukaryotes.
• Genome co-location, useful in bacteria, is insufficient for eukaryotic paralog pairing.

Purpose of the Study:

• To develop and test computational methods for pairing interacting protein paralogs in eukaryotes.
• To address the difficulty of matching paralogs when unique identifiers are absent.
• To improve the prediction of protein interactions using evolutionary relationships.

Main Methods:

• Developed graph-based methods using evolutionary distances between paralogs and unique proteins (singletons).
• Tested two variants: a topology-based method using phylogenetic trees and a distance-based method.
• Utilized sequence data to infer evolutionary relationships for paralog pairing.

Main Results:

• Both developed methods successfully paired interacting protein paralogs.
• The topology-based method showed slightly better performance than the distance-based method.
• The methods demonstrated effectiveness across a set of test proteins.

Conclusions:

• The developed methods offer a promising approach for eukaryotic protein interaction prediction.
• Future refinements may incorporate additional data like known interactions and genomic context.
• These methods aim to enable the use of vast eukaryotic genomic data for interaction studies.