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 zoom-in of the “optimal” GreedyPlus alignment of worm and yeast SH3-mediated IINs, consisting of the two yeast BZZ1 vertices and all their neighbours.Domain interfaces are represented by triangular vertices, ligand interfaces by circular vertices. Yellow vertices are aligned and orthologous; green vertices and edges are aligned, red are unaligned from worm, blue are unaligned from yeast. Vertex size indicates score. The two EAW contributors to EPHX-1,1010,1087 - BZZ1,568,633 are outlined in purple; the EAW contributor to SDPN-1,420,502 - BZZ1,478,572 is outlined in orange.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f5: A zoom-in of the “optimal” GreedyPlus alignment of worm and yeast SH3-mediated IINs, consisting of the two yeast BZZ1 vertices and all their neighbours.Domain interfaces are represented by triangular vertices, ligand interfaces by circular vertices. Yellow vertices are aligned and orthologous; green vertices and edges are aligned, red are unaligned from worm, blue are unaligned from yeast. Vertex size indicates score. The two EAW contributors to EPHX-1,1010,1087 - BZZ1,568,633 are outlined in purple; the EAW contributor to SDPN-1,420,502 - BZZ1,478,572 is outlined in orange.

Mentions: As a snapshot of how GreedyPlus works in practice, we zoom in on the yeast protein BZZ1 (see Fig. 5), which has two domain vertices in our dataset. BZZ1 is a recruiter protein involved in regulating actin polymerization33, and is an ortholog of the worm protein SDPN-1; Gene Ontology identifies both genes as involved in endocytosis34. In this alignment, performed by GreedyPlus using its tuned similarity weights, one of the BZZ1 domains is aligned to SDPN-1’s single SH3 domain. However, because GreedyPlus cannot perform one-to-many alignments, BZZ1’s other SH3 domain is aligned to EPHX-1, which is not an identified ortholog. Neither SDPN-1 nor EPHX-1 are among BZZ1’s top BLAST scores, ranking 9th and 11th among our dataset; however, the other similarity features and the Edge Alignment Weight drive up their priority in alignment.


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

Law B, Bader GD - Sci Rep (2015)

A zoom-in of the “optimal” GreedyPlus alignment of worm and yeast SH3-mediated IINs, consisting of the two yeast BZZ1 vertices and all their neighbours.Domain interfaces are represented by triangular vertices, ligand interfaces by circular vertices. Yellow vertices are aligned and orthologous; green vertices and edges are aligned, red are unaligned from worm, blue are unaligned from yeast. Vertex size indicates score. The two EAW contributors to EPHX-1,1010,1087 - BZZ1,568,633 are outlined in purple; the EAW contributor to SDPN-1,420,502 - BZZ1,478,572 is outlined in orange.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f5: A zoom-in of the “optimal” GreedyPlus alignment of worm and yeast SH3-mediated IINs, consisting of the two yeast BZZ1 vertices and all their neighbours.Domain interfaces are represented by triangular vertices, ligand interfaces by circular vertices. Yellow vertices are aligned and orthologous; green vertices and edges are aligned, red are unaligned from worm, blue are unaligned from yeast. Vertex size indicates score. The two EAW contributors to EPHX-1,1010,1087 - BZZ1,568,633 are outlined in purple; the EAW contributor to SDPN-1,420,502 - BZZ1,478,572 is outlined in orange.
Mentions: As a snapshot of how GreedyPlus works in practice, we zoom in on the yeast protein BZZ1 (see Fig. 5), which has two domain vertices in our dataset. BZZ1 is a recruiter protein involved in regulating actin polymerization33, and is an ortholog of the worm protein SDPN-1; Gene Ontology identifies both genes as involved in endocytosis34. In this alignment, performed by GreedyPlus using its tuned similarity weights, one of the BZZ1 domains is aligned to SDPN-1’s single SH3 domain. However, because GreedyPlus cannot perform one-to-many alignments, BZZ1’s other SH3 domain is aligned to EPHX-1, which is not an identified ortholog. Neither SDPN-1 nor EPHX-1 are among BZZ1’s top BLAST scores, ranking 9th and 11th among our dataset; however, the other similarity features and the Edge Alignment Weight drive up their priority in alignment.

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