skip to main content


Title: ConnectedAlign: a PPI network alignment method for identifying conserved protein complexes across multiple species
Abstract Background: In bioinformatics, network alignment algorithms have been applied to protein-protein interaction (PPI) networks to discover evolutionary conserved substructures at the system level. However, most previous methods aim to maximize the similarity of aligned proteins in pairwise networks, while concerning little about the feature of connectivity in these substructures, such as the protein complexes. Results: In this paper, we identify the problem of finding conserved protein complexes, which requires the aligned proteins in a PPI network to form a connected subnetwork. By taking the feature of connectivity into consideration, we propose ConnectedAlign, an efficient method to find conserved protein complexes from multiple PPI networks. The proposed method improves the coverage significantly without compromising of the consistency in the aligned results. In this way, the knowledge of protein complexes in well-studied species can be extended to that of poor-studied species. Conclusions: We conducted extensive experiments on real PPI networks of four species, including human, yeast, fruit fly and worm. The experimental results demonstrate dominant benefits of the proposed method in finding protein complexes across multiple species.  more » « less
Award ID(s):
1744661
NSF-PAR ID:
10109600
Author(s) / Creator(s):
Date Published:
Journal Name:
BMC bioinformatics
Volume:
supple 9
ISSN:
1471-2105
Page Range / eLocation ID:
45-51
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Research of Protein-Protein Interaction (PPI) Network Alignment is playing an important role in understanding the crucial underlying biological knowledge such as functionally homologous proteins and conserved evolutionary pathways across different species. Existing methods of PPI network alignment often try to improve the coverage ratio of the alignment result by aligning all proteins from different species. However, there is a fundamental biological premise that needs to be considered carefully: not every protein in a species can, nor should, find its homologous proteins in other species. In this work, we propose a novel alignment method to map only those proteins with the most similarity throughout the PPI networks of multiple species. For the similarity features of the protein in the networks, we integrate both topological features with biological characteristics to provide enhanced supports for the alignment procedures. For topological features, we apply a representation learning method on the networks that can generate a low dimensional vector embedding with its surrounding structural features for each protein. The topological similarity of proteins from different PPI networks can thus be transferred as the similarity of their corresponding vector representations, which provides a new way to comprehensively quantify the topological similarities between proteins. We also propose a new measure for the topological evaluation of the alignment results which better uncover the structural quality of the alignment across multiple networks. Both biological and topological evaluations on the alignment results of real datasets demonstrate our approach is promising and preferable against previous multiple alignment methods 
    more » « less
  2. Abstract—Protein-protein interaction (PPI) network alignment has been motivating researches for the comprehension of the underlying crucial biological knowledge, such as conserved evolutionary pathways and functionally conserved proteins throughout different species. Existing PPI network alignment methods have tried to improve the coverage ratio by aligning all proteins from different species. However, there is a fundamental biological justification needed to be acknowledged, that not every protein in a species can, nor should, find homologous proteins in other species. In this paper, we propose a novel approach for multiple PPI network alignment that tries to align only those proteins with the most similarities. To provide more comprehensive supports in computing the similarity, we integrate structural features of the networks together with biological characteristics during the alignment. For the structural features, we apply on PPI networks a representation learning method, which creates a low-dimensional vector embedding with the surrounding topologies of each protein in the network. This approach quantifies the structural features, and provides a new way to determine the topological similarity of the networks by transferring which as calculations in vector similarities. We also propose a new metric for the topological evaluation which can better assess the topological quality of the alignment results across different networks. Both biological and topological evaluations demonstrate our approach is promising and preferable against previous multiple alignment methods. 
    more » « less
  3. Protein-protein interaction (PPI) network alignment has been motivating researches for the comprehension of the underlying crucial biological knowledge, such as conserved evolutionary pathways and functionally conserved proteins throughout different species. Existing PPI network alignment methods have tried to improve the coverage ratio by aligning all proteins from different species. However, there is a fundamental biological justification needed to be acknowledged, that not every protein in a species can, nor should, find homologous proteins in other species. In this paper, we propose a novel approach for multiple PPI network alignment that tries to align only those proteins with the most similarities. To provide more comprehensive supports in computing the similarity, we integrate structural features of the networks together with biological characteristics during the alignment. For the structural features, we apply on PPI networks a representation learning method, which creates a low-dimensional vector embedding with the surrounding topologies of each protein in the network. This approach quantifies the structural features, and provides a new way to determine the topological similarity of the networks by transferring which as calculations in vector similarities. We also propose a new metric for the topological evaluation which can better assess the topological quality of the alignment results across different networks. Both biological and topological evaluations demonstrate our approach is promising and preferable against previous multiple alignment methods. 
    more » « less
  4. Abstract—Protein-protein interaction (PPI) network alignment has been motivating researches for the comprehension of the underlying crucial biological knowledge, such as conserved evolutionary pathways and functionally conserved proteins throughout different species. Existing PPI network alignment methods have tried to improve the coverage ratio by aligning all proteins from different species. However, there is a fundamental biological justification needed to be acknowledged, that not every protein in a species can, nor should, find homologous proteins in other species. In this paper, we propose a novel approach for multiple PPI network alignment that tries to align only those proteins with the most similarities. To provide more comprehensive supports in computing the similarity, we integrate structural features of the networks together with biological characteristics during the alignment. For the structural features, we apply on PPI networks a representation learning method, which creates a low-dimensional vector embedding with the surrounding topologies of each protein in the network. This approach quantifies the structural features, and provides a new way to determine the topological similarity of the networks by transferring which as calculations in vector similarities. We also propose a new metric for the topological evaluation which can better assess the topological quality of the alignment results across different networks. Both biological and topological evaluations demonstrate our approach is promising and preferable against previous multiple alignment methods. 
    more » « less
  5. Protein-protein interaction (PPI) network alignment has been motivating researches for the comprehension of the underlying crucial biological knowledge, such as conserved evolutionary pathways and functionally conserved proteins throughout different species. Existing PPI network alignment methods have tried to improve the coverage ratio by aligning all proteins from different species. However, there is a fundamental biological justification needed to be acknowledged, that not every protein in a species can, nor should, find homologous proteins in other species. In this paper, we propose a novel approach for multiple PPI network alignment that tries to align only those proteins with the most similarities. To provide more comprehensive supports in computing the similarity, we integrate structural features of the networks together with biological characteristics during the alignment. For the structural features, we apply on PPI networks a representation learning method, which creates a low-dimensional vector embedding with the surrounding topologies of each protein in the network. This approach quantifies the structural features, and provides a new way to determine the topological similarity of the networks by transferring which as calculations in vector similarities. We also propose a new metric for the topological evaluation which can better assess the topological quality of the alignment results across different networks. Both biological and topological evaluations demonstrate our approach is promising and preferable against previous multiple alignment methods. 
    more » « less