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

Trade-off in GreedyPlus performance between orthologous vertices aligned and edges aligned.Using BLAST score between proteins as the only similarity feature, we ran GreedyPlus with the edge alignment weight set at values ranging from 0% to 100% of the protein BLAST score weight, and plotted its performance. If the plots were tightly correlated, it would indicate that successfully aligning networks topologically would be equivalent to aligning vertex pairs successfully. However, we observe a distinct trade-off between aligning edges and aligning orthologous vertices.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f9: Trade-off in GreedyPlus performance between orthologous vertices aligned and edges aligned.Using BLAST score between proteins as the only similarity feature, we ran GreedyPlus with the edge alignment weight set at values ranging from 0% to 100% of the protein BLAST score weight, and plotted its performance. If the plots were tightly correlated, it would indicate that successfully aligning networks topologically would be equivalent to aligning vertex pairs successfully. However, we observe a distinct trade-off between aligning edges and aligning orthologous vertices.

Mentions: Though we lack sufficient IIN data to make a general statement, we observed a trade-off between the alignment of biologically verified vertex pairs and the alignment of edges with a number of algorithms, including our own. Notably, an increase in the number of edges aligned did not necessarily lead to an increase in the number of vertices properly aligned. Some brief experiments with the Edge Alignment Weight parameter showed that, with GreedyPlus, attempting to maximize the number of aligned edges results in a distinct decrease in the number of properly aligned vertices (see Fig. 9).


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

Law B, Bader GD - Sci Rep (2015)

Trade-off in GreedyPlus performance between orthologous vertices aligned and edges aligned.Using BLAST score between proteins as the only similarity feature, we ran GreedyPlus with the edge alignment weight set at values ranging from 0% to 100% of the protein BLAST score weight, and plotted its performance. If the plots were tightly correlated, it would indicate that successfully aligning networks topologically would be equivalent to aligning vertex pairs successfully. However, we observe a distinct trade-off between aligning edges and aligning orthologous vertices.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f9: Trade-off in GreedyPlus performance between orthologous vertices aligned and edges aligned.Using BLAST score between proteins as the only similarity feature, we ran GreedyPlus with the edge alignment weight set at values ranging from 0% to 100% of the protein BLAST score weight, and plotted its performance. If the plots were tightly correlated, it would indicate that successfully aligning networks topologically would be equivalent to aligning vertex pairs successfully. However, we observe a distinct trade-off between aligning edges and aligning orthologous vertices.
Mentions: Though we lack sufficient IIN data to make a general statement, we observed a trade-off between the alignment of biologically verified vertex pairs and the alignment of edges with a number of algorithms, including our own. Notably, an increase in the number of edges aligned did not necessarily lead to an increase in the number of vertices properly aligned. Some brief experiments with the Edge Alignment Weight parameter showed that, with GreedyPlus, attempting to maximize the number of aligned edges results in a distinct decrease in the number of properly aligned vertices (see Fig. 9).

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