Limits...
GreedyPlus: An Algorithm for the Alignment of Interface Interaction Networks.

Law B, Bader GD - Sci Rep (2015)

Bottom Line: The increasing ease and accuracy of protein-protein interaction detection has resulted in the ability to map the interactomes of multiple species.We now have an opportunity to compare species to better understand how interactomes evolve.GreedyPlus is fast and simple, allowing for easy customization of behaviour, yet still capable of generating biologically meaningful network alignments.

View Article: PubMed Central - PubMed

Affiliation: 1] Department of Computer Science, University of Toronto, Toronto, ON, Canada [2] The Donnelly Centre, University of Toronto, Toronto, ON, Canada.

ABSTRACT
The increasing ease and accuracy of protein-protein interaction detection has resulted in the ability to map the interactomes of multiple species. We now have an opportunity to compare species to better understand how interactomes evolve. As DNA and protein sequence alignment algorithms were required for comparative genomics, network alignment algorithms are required for comparative interactomics. A number of network alignment methods have been developed for protein-protein interaction networks, where proteins are represented as vertices linked by edges if they interact. Recently, protein interactions have been mapped at the level of amino acid positions, which can be represented as an interface-interaction network (IIN), where vertices represent binding sites, such as protein domains and short sequence motifs. However, current algorithms are not designed to align these networks and generally fail to do so in practice. We present a greedy algorithm, GreedyPlus, for IIN alignment, combining data from diverse sources, including network, protein and binding site properties, to identify putative orthologous relationships between interfaces in available worm and yeast data. GreedyPlus is fast and simple, allowing for easy customization of behaviour, yet still capable of generating biologically meaningful network alignments.

No MeSH data available.


Related in: MedlinePlus

A density plot of graphlet similarity scores between orthologous vertices (in pink) and random vertex pairs (in blue).Orthologous vertex pairs do not demonstrate a characteristic graphlet similarity score; as such, graphlet similarity has reduced power in correctly aligning vertices. Note that many random vertex pairs have high graphlet similarity in the IINs under study; this is due to the prevalence of leaf vertices, which tend to exhibit similar graphlet degree vectors.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4499810&req=5

f4: A density plot of graphlet similarity scores between orthologous vertices (in pink) and random vertex pairs (in blue).Orthologous vertex pairs do not demonstrate a characteristic graphlet similarity score; as such, graphlet similarity has reduced power in correctly aligning vertices. Note that many random vertex pairs have high graphlet similarity in the IINs under study; this is due to the prevalence of leaf vertices, which tend to exhibit similar graphlet degree vectors.

Mentions: The GRAAL and H-GRAAL algorithms rely on a single vertex similarity feature, known as the graphlet degree signature16. Thus our second comparison uses only graphlet degree vertex similarity across all compared algorithms (Table 2), including C-GRAAL as it was also tested with just graphlet degree signature. This vertex similarity measure results in poor vertex alignment performance across all algorithms. For example, the GRAAL algorithm identifies no orthologous vertex pairs, though it does have a similar execution time as GreedyPlus. The generation of the graphlet degree signature for a given vertex involves counting the number of 2-, 3-, 4-, and 5-vertex graphlets in which the vertex participates. However, of the 29 graphlets of such size, 20 of them contain odd cycles not present in bipartite networks. This reduces the number of graphlet orbits, and the length of the graphlet degree signature vector, from 72 to 20. Due to this loss of resolution, the GRAAL algorithm loses power in discriminating between vertex pairings (see Fig. 4). Furthermore, the exaggerated spoke-hub network of IINs in comparison to PPINs, for which the GRAAL algorithm was designed, results in the GRAAL algorithm preferring to align non-orthologous vertices to orthologous ones.


GreedyPlus: An Algorithm for the Alignment of Interface Interaction Networks.

Law B, Bader GD - Sci Rep (2015)

A density plot of graphlet similarity scores between orthologous vertices (in pink) and random vertex pairs (in blue).Orthologous vertex pairs do not demonstrate a characteristic graphlet similarity score; as such, graphlet similarity has reduced power in correctly aligning vertices. Note that many random vertex pairs have high graphlet similarity in the IINs under study; this is due to the prevalence of leaf vertices, which tend to exhibit similar graphlet degree vectors.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4499810&req=5

f4: A density plot of graphlet similarity scores between orthologous vertices (in pink) and random vertex pairs (in blue).Orthologous vertex pairs do not demonstrate a characteristic graphlet similarity score; as such, graphlet similarity has reduced power in correctly aligning vertices. Note that many random vertex pairs have high graphlet similarity in the IINs under study; this is due to the prevalence of leaf vertices, which tend to exhibit similar graphlet degree vectors.
Mentions: The GRAAL and H-GRAAL algorithms rely on a single vertex similarity feature, known as the graphlet degree signature16. Thus our second comparison uses only graphlet degree vertex similarity across all compared algorithms (Table 2), including C-GRAAL as it was also tested with just graphlet degree signature. This vertex similarity measure results in poor vertex alignment performance across all algorithms. For example, the GRAAL algorithm identifies no orthologous vertex pairs, though it does have a similar execution time as GreedyPlus. The generation of the graphlet degree signature for a given vertex involves counting the number of 2-, 3-, 4-, and 5-vertex graphlets in which the vertex participates. However, of the 29 graphlets of such size, 20 of them contain odd cycles not present in bipartite networks. This reduces the number of graphlet orbits, and the length of the graphlet degree signature vector, from 72 to 20. Due to this loss of resolution, the GRAAL algorithm loses power in discriminating between vertex pairings (see Fig. 4). Furthermore, the exaggerated spoke-hub network of IINs in comparison to PPINs, for which the GRAAL algorithm was designed, results in the GRAAL algorithm preferring to align non-orthologous vertices to orthologous ones.

Bottom Line: The increasing ease and accuracy of protein-protein interaction detection has resulted in the ability to map the interactomes of multiple species.We now have an opportunity to compare species to better understand how interactomes evolve.GreedyPlus is fast and simple, allowing for easy customization of behaviour, yet still capable of generating biologically meaningful network alignments.

View Article: PubMed Central - PubMed

Affiliation: 1] Department of Computer Science, University of Toronto, Toronto, ON, Canada [2] The Donnelly Centre, University of Toronto, Toronto, ON, Canada.

ABSTRACT
The increasing ease and accuracy of protein-protein interaction detection has resulted in the ability to map the interactomes of multiple species. We now have an opportunity to compare species to better understand how interactomes evolve. As DNA and protein sequence alignment algorithms were required for comparative genomics, network alignment algorithms are required for comparative interactomics. A number of network alignment methods have been developed for protein-protein interaction networks, where proteins are represented as vertices linked by edges if they interact. Recently, protein interactions have been mapped at the level of amino acid positions, which can be represented as an interface-interaction network (IIN), where vertices represent binding sites, such as protein domains and short sequence motifs. However, current algorithms are not designed to align these networks and generally fail to do so in practice. We present a greedy algorithm, GreedyPlus, for IIN alignment, combining data from diverse sources, including network, protein and binding site properties, to identify putative orthologous relationships between interfaces in available worm and yeast data. GreedyPlus is fast and simple, allowing for easy customization of behaviour, yet still capable of generating biologically meaningful network alignments.

No MeSH data available.


Related in: MedlinePlus