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 simple example of GreedyPlus in action.First, GreedyPlus finds the highest scoring pair of vertices (in yellow), in this case the pair (A, 1), and aligns them. Then the similarity matrix is updated, with the scores of all pairs of all neighbours of just-aligned vertices (in green) incremented by the Edge Alignment Weight (in this case, 1). Using the updated similarity matrix, GreedyPlus iterates until all vertices are aligned. In this example, the third vertex alignment [C, 3] is made as a result of the Edge Alignment Weight increasing its similarity score; otherwise, the pairing [E, 3] would have been made instead.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f10: A simple example of GreedyPlus in action.First, GreedyPlus finds the highest scoring pair of vertices (in yellow), in this case the pair (A, 1), and aligns them. Then the similarity matrix is updated, with the scores of all pairs of all neighbours of just-aligned vertices (in green) incremented by the Edge Alignment Weight (in this case, 1). Using the updated similarity matrix, GreedyPlus iterates until all vertices are aligned. In this example, the third vertex alignment [C, 3] is made as a result of the Edge Alignment Weight increasing its similarity score; otherwise, the pairing [E, 3] would have been made instead.

Mentions: The GreedyPlus algorithm is essentially a greedy algorithm that iteratively aligns pairs of vertices in descending order of similarity, defined by a given similarity score. However, when aligning two vertices, GreedyPlus also considers the number of edges that would be aligned if the vertices were aligned, strengthening the respective vertex pair similarity score with more edges aligned (see Fig. 10 and Fig. 11). Thus, GreedyPlus will prefer to align vertex pairs that also align edge pairs over those that do not if the difference in similarity is small, but will align highly similar vertices irrespective of network topology. The preference of the algorithm in aligning edges or maximizing vertex similarity can be controlled using a defined parameter, named the edge alignment weight (EAW), providing flexibility and enabling investigation of the relative importance of aligning vertices versus edges.


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

Law B, Bader GD - Sci Rep (2015)

A simple example of GreedyPlus in action.First, GreedyPlus finds the highest scoring pair of vertices (in yellow), in this case the pair (A, 1), and aligns them. Then the similarity matrix is updated, with the scores of all pairs of all neighbours of just-aligned vertices (in green) incremented by the Edge Alignment Weight (in this case, 1). Using the updated similarity matrix, GreedyPlus iterates until all vertices are aligned. In this example, the third vertex alignment [C, 3] is made as a result of the Edge Alignment Weight increasing its similarity score; otherwise, the pairing [E, 3] would have been made instead.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f10: A simple example of GreedyPlus in action.First, GreedyPlus finds the highest scoring pair of vertices (in yellow), in this case the pair (A, 1), and aligns them. Then the similarity matrix is updated, with the scores of all pairs of all neighbours of just-aligned vertices (in green) incremented by the Edge Alignment Weight (in this case, 1). Using the updated similarity matrix, GreedyPlus iterates until all vertices are aligned. In this example, the third vertex alignment [C, 3] is made as a result of the Edge Alignment Weight increasing its similarity score; otherwise, the pairing [E, 3] would have been made instead.
Mentions: The GreedyPlus algorithm is essentially a greedy algorithm that iteratively aligns pairs of vertices in descending order of similarity, defined by a given similarity score. However, when aligning two vertices, GreedyPlus also considers the number of edges that would be aligned if the vertices were aligned, strengthening the respective vertex pair similarity score with more edges aligned (see Fig. 10 and Fig. 11). Thus, GreedyPlus will prefer to align vertex pairs that also align edge pairs over those that do not if the difference in similarity is small, but will align highly similar vertices irrespective of network topology. The preference of the algorithm in aligning edges or maximizing vertex similarity can be controlled using a defined parameter, named the edge alignment weight (EAW), providing flexibility and enabling investigation of the relative importance of aligning vertices versus edges.

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