PrimAlign: PageRank-inspired Markovian alignment for large biological networks
Open Access
- 27 June 2018
- journal article
- conference paper
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 34 (13) , i537-i546
Abstract
Cross-species analysis of large-scale protein–protein interaction (PPI) networks has played a significant role in understanding the principles deriving evolution of cellular organizations and functions. Recently, network alignment algorithms have been proposed to predict conserved interactions and functions of proteins. These approaches are based on the notion that orthologous proteins across species are sequentially similar and that topology of PPIs between orthologs is often conserved. However, high accuracy and scalability of network alignment are still a challenge. We propose a novel pairwise global network alignment algorithm, called PrimAlign, which is modeled as a Markov chain and iteratively transited until convergence. The proposed algorithm also incorporates the principles of PageRank. This approach is evaluated on tasks with human, yeast and fruit fly PPI networks. The experimental results demonstrate that PrimAlign outperforms several prevalent methods with statistically significant differences in multiple evaluation measures. PrimAlign, which is multi-platform, achieves superior performance in runtime with its linear asymptotic time complexity. Further evaluation is done with synthetic networks and results suggest that popular topological measures do not reflect real precision of alignments. The source code is available at http://web.ecs.baylor.edu/faculty/cho/PrimAlign. Supplementary data are available at Bioinformatics online.Keywords
This publication has 34 references indexed in Scilit:
- SMETANA: Accurate and Scalable Algorithm for Probabilistic Alignment of Large-Scale Biological NetworksPLOS ONE, 2013
- A Network Synthesis Model for Generating Protein Interaction Network FamiliesPLOS ONE, 2012
- AlignNemo: A Local Network Alignment Method to Integrate Homology and TopologyPLOS ONE, 2012
- PINALOG: a novel approach to align protein interaction networks—implications for complex detection and function predictionBioinformatics, 2012
- Ensembl BioMarts: a hub for data retrieval across taxonomic spaceDatabase: The Journal of Biological Databases and Curation, 2011
- Topological network alignment uncovers biological function and phylogenyJournal of The Royal Society Interface, 2010
- IsoRankN: spectral methods for global alignment of multiple protein networksBioinformatics, 2009
- Global alignment of multiple protein interaction networks with application to functional orthology detectionProceedings of the National Academy of Sciences, 2008
- Metrics for GO based protein semantic similarity: a systematic evaluationBMC Bioinformatics, 2008
- Conserved patterns of protein interaction in multiple speciesProceedings of the National Academy of Sciences, 2005