Limits...
Detecting conserved protein complexes using a dividing-and-matching algorithm and unequally lenient criteria for network comparison.

Peng W, Wang J, Wu F, Yi P - Algorithms Mol Biol (2015)

Bottom Line: The increase of protein-protein interaction (PPI) data of different species makes it possible to identify common subnetworks (conserved protein complexes) across species via local alignment of their PPI networks, which benefits us to study biological evolution.Comparisons are made between other six existing methods and UEDAMAlign.The experimental results show that UEDAMAlign outperforms other existing methods in recovering conserved protein complexes that both match well with known protein complexes and have similar functions.

View Article: PubMed Central - PubMed

Affiliation: The School of Information Science and Engineering, Central South University, Changsha, Hunan People's Republic of China ; The Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming, 650093 Yunnan People's Republic of China.

ABSTRACT
The increase of protein-protein interaction (PPI) data of different species makes it possible to identify common subnetworks (conserved protein complexes) across species via local alignment of their PPI networks, which benefits us to study biological evolution. Local alignment algorithms compare PPI network of different species at both protein sequence and network structure levels. For computational and biological reasons, it is hard to find common subnetworks with strict similar topology from two input PPI networks. Consequently some methods introduce less strict criteria for topological similarity. However those methods fail to consider the differences of the two input networks and adopt equally lenient criteria on them. In this work, a new dividing-and-matching-based method, namely UEDAMAlign is proposed to detect conserved protein complexes. This method firstly uses known protein complexes or computational methods to divide one of the two input PPI networks into subnetworks and then maps the proteins in these subnetworks to the other PPI network to get their homologous proteins. After that, UEDAMAlign conducts unequally lenient criteria on the two input networks to find common connected components from the proteins in the subnetworks and their homologous proteins in the other network. We carry out network alignments between S. cerevisiae and D. melanogaster, H. sapiens and D. melanogaster, respectively. Comparisons are made between other six existing methods and UEDAMAlign. The experimental results show that UEDAMAlign outperforms other existing methods in recovering conserved protein complexes that both match well with known protein complexes and have similar functions.

No MeSH data available.


Eight cases (a–h) of connectivity in conserved protein complexes from two different PPI networks when UEDAMAlign adopts the same lenient criteria as AlignNemo does to extend a pair of homologous proteins. The nodes with different color come from different PPI networks. The full lines connecting two different color nodes represent their known homologous mappings. The dot lines represent artificial homologous mappings by a unbalanced Bi-random walk algorithm. The full lines connecting the same color nodes represent their interactions.
© Copyright Policy - OpenAccess
Related In: Results  -  Collection

License 1 - License 2
getmorefigures.php?uid=PMC4487215&req=5

Fig1: Eight cases (a–h) of connectivity in conserved protein complexes from two different PPI networks when UEDAMAlign adopts the same lenient criteria as AlignNemo does to extend a pair of homologous proteins. The nodes with different color come from different PPI networks. The full lines connecting two different color nodes represent their known homologous mappings. The dot lines represent artificial homologous mappings by a unbalanced Bi-random walk algorithm. The full lines connecting the same color nodes represent their interactions.

Mentions: The basic idea of UEDAMAlign is first dividing PPI networks into small subnetworks and then mapping proteins of subnetworks to the other PPI network. Many computational methods, such as Coach [36], MCL [37, 38], CMC [39], CFinder [40] and so on, have been proposed to detect protein complexes form a single PPI network and achieve good performance. Moreover, biological experiments have been implemented on several species and the data of known protein complexes is available. Consequently those known protein complexes or those predicted by computational methods can be conveniently used as partition of a PPI network. The main challenge of UEDAMAlign lies in mapping proteins in subnetworks of a PPI network to the other one in order to find common connected components. In the course of finding common connected components, UEDAMAlign adopts unequally lenient criteria to extend a pair of homologous proteins. The span distance of a protein pair in a single network is unequal with respect to the difference of input PPI networks, which is determined by inputting parameters l and r. For example, when taking the same lenient criteria as AlignNemo and DAMAlign do, UEDAMAlign absorbs a pair of homologous proteins into its predicted conserved protein complexes if at least one of protein in the homologous protein pair connects to the proteins in the predicted conserved protein complexes through a path of length not larger than 2. In this case, parameters l and r are set to 2. When parameters l and r are set to 2 and 3 respectively, UEDAMAlign locally extends a pair of homologous proteins if there exists a path of length not larger than 2 to connect the node in the homologous protein pair in PPI network one or a path of length not larger than 3 to connect the node in the homologous protein pair in PPI network two. Figure 1 shows eight cases of connectivity in conserved protein complexes from two different PPI networks when l and r are set to 2. Figure 2 shows eleven cases of connectivity in conserved protein complexes from two different PPI networks when l and r are set to 2 and 3 respectively. The nodes with different color come from different PPI networks. The full lines connecting two different color nodes represent their known homologous mappings. The dot lines represent artificial homologous mappings detected by unbalanced Bi-random walk algorithm. The full lines connecting the same color nodes represent their interactions.Figure 1


Detecting conserved protein complexes using a dividing-and-matching algorithm and unequally lenient criteria for network comparison.

Peng W, Wang J, Wu F, Yi P - Algorithms Mol Biol (2015)

Eight cases (a–h) of connectivity in conserved protein complexes from two different PPI networks when UEDAMAlign adopts the same lenient criteria as AlignNemo does to extend a pair of homologous proteins. The nodes with different color come from different PPI networks. The full lines connecting two different color nodes represent their known homologous mappings. The dot lines represent artificial homologous mappings by a unbalanced Bi-random walk algorithm. The full lines connecting the same color nodes represent their interactions.
© Copyright Policy - OpenAccess
Related In: Results  -  Collection

License 1 - License 2
Show All Figures
getmorefigures.php?uid=PMC4487215&req=5

Fig1: Eight cases (a–h) of connectivity in conserved protein complexes from two different PPI networks when UEDAMAlign adopts the same lenient criteria as AlignNemo does to extend a pair of homologous proteins. The nodes with different color come from different PPI networks. The full lines connecting two different color nodes represent their known homologous mappings. The dot lines represent artificial homologous mappings by a unbalanced Bi-random walk algorithm. The full lines connecting the same color nodes represent their interactions.
Mentions: The basic idea of UEDAMAlign is first dividing PPI networks into small subnetworks and then mapping proteins of subnetworks to the other PPI network. Many computational methods, such as Coach [36], MCL [37, 38], CMC [39], CFinder [40] and so on, have been proposed to detect protein complexes form a single PPI network and achieve good performance. Moreover, biological experiments have been implemented on several species and the data of known protein complexes is available. Consequently those known protein complexes or those predicted by computational methods can be conveniently used as partition of a PPI network. The main challenge of UEDAMAlign lies in mapping proteins in subnetworks of a PPI network to the other one in order to find common connected components. In the course of finding common connected components, UEDAMAlign adopts unequally lenient criteria to extend a pair of homologous proteins. The span distance of a protein pair in a single network is unequal with respect to the difference of input PPI networks, which is determined by inputting parameters l and r. For example, when taking the same lenient criteria as AlignNemo and DAMAlign do, UEDAMAlign absorbs a pair of homologous proteins into its predicted conserved protein complexes if at least one of protein in the homologous protein pair connects to the proteins in the predicted conserved protein complexes through a path of length not larger than 2. In this case, parameters l and r are set to 2. When parameters l and r are set to 2 and 3 respectively, UEDAMAlign locally extends a pair of homologous proteins if there exists a path of length not larger than 2 to connect the node in the homologous protein pair in PPI network one or a path of length not larger than 3 to connect the node in the homologous protein pair in PPI network two. Figure 1 shows eight cases of connectivity in conserved protein complexes from two different PPI networks when l and r are set to 2. Figure 2 shows eleven cases of connectivity in conserved protein complexes from two different PPI networks when l and r are set to 2 and 3 respectively. The nodes with different color come from different PPI networks. The full lines connecting two different color nodes represent their known homologous mappings. The dot lines represent artificial homologous mappings detected by unbalanced Bi-random walk algorithm. The full lines connecting the same color nodes represent their interactions.Figure 1

Bottom Line: The increase of protein-protein interaction (PPI) data of different species makes it possible to identify common subnetworks (conserved protein complexes) across species via local alignment of their PPI networks, which benefits us to study biological evolution.Comparisons are made between other six existing methods and UEDAMAlign.The experimental results show that UEDAMAlign outperforms other existing methods in recovering conserved protein complexes that both match well with known protein complexes and have similar functions.

View Article: PubMed Central - PubMed

Affiliation: The School of Information Science and Engineering, Central South University, Changsha, Hunan People's Republic of China ; The Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming, 650093 Yunnan People's Republic of China.

ABSTRACT
The increase of protein-protein interaction (PPI) data of different species makes it possible to identify common subnetworks (conserved protein complexes) across species via local alignment of their PPI networks, which benefits us to study biological evolution. Local alignment algorithms compare PPI network of different species at both protein sequence and network structure levels. For computational and biological reasons, it is hard to find common subnetworks with strict similar topology from two input PPI networks. Consequently some methods introduce less strict criteria for topological similarity. However those methods fail to consider the differences of the two input networks and adopt equally lenient criteria on them. In this work, a new dividing-and-matching-based method, namely UEDAMAlign is proposed to detect conserved protein complexes. This method firstly uses known protein complexes or computational methods to divide one of the two input PPI networks into subnetworks and then maps the proteins in these subnetworks to the other PPI network to get their homologous proteins. After that, UEDAMAlign conducts unequally lenient criteria on the two input networks to find common connected components from the proteins in the subnetworks and their homologous proteins in the other network. We carry out network alignments between S. cerevisiae and D. melanogaster, H. sapiens and D. melanogaster, respectively. Comparisons are made between other six existing methods and UEDAMAlign. The experimental results show that UEDAMAlign outperforms other existing methods in recovering conserved protein complexes that both match well with known protein complexes and have similar functions.

No MeSH data available.