{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T15:02:12Z","timestamp":1775919732017,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T00:00:00Z","timestamp":1604448000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T00:00:00Z","timestamp":1604448000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100010221","name":"Higher Education Commision, Pakistan","doi-asserted-by":"publisher","award":["This research work was funded by the Higher Education Commission(HEC) of Pakistan and the Ministry of Planning, Development and Reforms under the National Center in Big Data and Cloud Computing."],"award-info":[{"award-number":["This research work was funded by the Higher Education Commission(HEC) of Pakistan and the Ministry of Planning, Development and Reforms under the National Center in Big Data and Cloud Computing."]}],"id":[{"id":"10.13039\/501100010221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n              <jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>High throughput experiments have generated a significantly large amount of protein interaction data, which is being used to study protein networks. Studying complete protein networks can reveal more insight about healthy\/disease states than studying proteins in isolation. Similarly, a comparative study of protein\u2013protein interaction (PPI) networks of different species reveals important insights which may help in disease analysis and drug design. The study of PPI network alignment can also helps in understanding the different biological systems of different species. It can also be used in transfer of knowledge across different species. Different aligners have been introduced in the last decade but developing an accurate and scalable global alignment algorithm that can ensures the biological significance alignment is still challenging.<\/jats:p>\n              <\/jats:sec>\n              <jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>This paper presents a novel global pairwise network alignment algorithm, SAlign, which uses topological and biological information in the alignment process. The proposed algorithm incorporates sequence and structural information for computing biological scores, whereas previous algorithms only use sequence information. The alignment based on the proposed technique shows that the combined effect of structure and sequence results in significantly better pairwise alignments. We have compared SAlign with state-of-art algorithms on the basis of semantic similarity of alignment and the number of aligned nodes on multiple PPI network pairs. The results of SAlign on the network pairs which have high percentage of proteins with available structure are 3\u201363% semantically better than all existing techniques. Furthermore, it also aligns 5\u201314% more nodes of these network pairs as compared to existing aligners. The results of SAlign on other PPI network pairs are comparable or better than all existing techniques. We also introduce <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\hbox {SAlign}^{\\mathrm{mc}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                    <mml:msup>\n                      <mml:mtext>SAlign<\/mml:mtext>\n                      <mml:mi>mc<\/mml:mi>\n                    <\/mml:msup>\n                  <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, a Monte Carlo based alignment algorithm, that produces multiple network alignments with similar semantic similarity. This helps the user to pick biologically meaningful alignments.<\/jats:p>\n              <\/jats:sec>\n              <jats:sec>\n                <jats:title>Conclusion<\/jats:title>\n                <jats:p>The proposed algorithm has the ability to find the alignments that are more biologically significant\/relevant as compared to the alignments of existing aligners. Furthermore, the proposed method is able to generate alternate alignments that help in studying different genes\/proteins of the specie.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s12859-020-03827-5","type":"journal-article","created":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T10:03:06Z","timestamp":1604484186000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["SAlign\u2013a structure aware method for global PPI network alignment"],"prefix":"10.1186","volume":"21","author":[{"given":"Umair","family":"Ayub","sequence":"first","affiliation":[]},{"given":"Imran","family":"Haider","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1867-974X","authenticated-orcid":false,"given":"Hammad","family":"Naveed","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,4]]},"reference":[{"issue":"17","key":"3827_CR1","doi-asserted-by":"publisher","first-page":"i438","DOI":"10.1093\/bioinformatics\/btu450","volume":"30","author":"S Hashemifar","year":"2014","unstructured":"Hashemifar S, Xu J. Hubalign: an accurate and efficient method for global alignment of protein\u2013protein interaction networks. Bioinformatics. 2014;30(17):i438\u201344.","journal-title":"Bioinformatics"},{"key":"3827_CR2","first-page":"56","volume-title":"Protein mover\u2019s distance: a geometric framework for solving global alignment of PPI networks","author":"M Liu","year":"2017","unstructured":"Liu M, Ding H. Protein mover\u2019s distance: a geometric framework for solving global alignment of PPI networks. Berlin: Springer; 2017. p. 56\u201369."},{"issue":"7","key":"3827_CR3","doi-asserted-by":"publisher","first-page":"677","DOI":"10.7150\/ijbs.8430","volume":"10","author":"L Yang","year":"2014","unstructured":"Yang L, Zhao X, Tang X. Predicting disease-related proteins based on clique backbone in Protein\u2013Protein interaction network. Int. J Biol Sci. 2014;10(7):677.","journal-title":"Int. J Biol Sci"},{"key":"3827_CR4","unstructured":"Breda A, Valadares NF, de Souza ON, Garratt RC. Protein structure, modelling and applications. Bioinformatics in tropical disease research: a practical and case-study approach [Internet]. 2007."},{"issue":"20","key":"3827_CR5","doi-asserted-by":"publisher","first-page":"3155","DOI":"10.1093\/bioinformatics\/btw348","volume":"32","author":"L Meng","year":"2016","unstructured":"Meng L, Striegel A, Milenkovi\u0107 T. Local versus global biological network alignment. Bioinformatics. 2016;32(20):3155\u201364.","journal-title":"Bioinformatics"},{"issue":"3","key":"3827_CR6","first-page":"472","volume":"19","author":"PH Guzzi","year":"2017","unstructured":"Guzzi PH, Milenkovi\u0107 T. Survey of local and global biological network alignment: the need to reconcile the two sides of the same coin. Brief Bioinform. 2017;19(3):472\u201381.","journal-title":"Brief Bioinform"},{"issue":"17","key":"3827_CR7","doi-asserted-by":"publisher","first-page":"i658","DOI":"10.1093\/bioinformatics\/btw447","volume":"32","author":"S Hashemifar","year":"2016","unstructured":"Hashemifar S, Ma J, Naveed H, Canzar S, Xu J. ModuleAlign: module-based global alignment of protein\u2013protein interaction networks. Bioinformatics. 2016;32(17):i658\u201364.","journal-title":"Bioinformatics"},{"issue":"13","key":"3827_CR8","doi-asserted-by":"publisher","first-page":"1654","DOI":"10.1093\/bioinformatics\/btt202","volume":"29","author":"B Neyshabur","year":"2013","unstructured":"Neyshabur B, Khadem A, Hashemifar S, Arab SS. NETAL: a new graph-based method for global alignment of protein\u2013protein interaction networks. Bioinformatics. 2013;29(13):1654\u201362.","journal-title":"Bioinformatics"},{"issue":"1","key":"3827_CR9","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1186\/s12859-016-1395-9","volume":"17","author":"E Kazemi","year":"2016","unstructured":"Kazemi E, Hassani H, Grossglauser M, Modarres HP. PROPER: global protein interaction network alignment through percolation matching. BMC Bioinform. 2016;17(1):527.","journal-title":"BMC Bioinform"},{"issue":"1","key":"3827_CR10","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1109\/TCBB.2016.2613098","volume":"15","author":"A Elmsallati","year":"2018","unstructured":"Elmsallati A, Msalati A, Kalita J. Index-based network aligner of protein\u2013protein interaction networks. IEEE\/ACM Trans Comput Biol Bioinform (TCBB). 2018;15(1):330\u20136.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform (TCBB)"},{"issue":"20","key":"3827_CR11","doi-asserted-by":"publisher","first-page":"2931","DOI":"10.1093\/bioinformatics\/btu409","volume":"30","author":"V Saraph","year":"2014","unstructured":"Saraph V, Milenkovi\u0107 T. MAGNA: maximizing accuracy in global network alignment. Bioinformatics. 2014;30(20):2931\u201340.","journal-title":"Bioinformatics"},{"issue":"1","key":"3827_CR12","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1038\/s41598-017-01085-9","volume":"7","author":"N Malod-Dognin","year":"2017","unstructured":"Malod-Dognin N, Ban K, Pr\u017eulj N. Unified alignment of protein\u2013protein interaction networks. Sci Rep. 2017;7(1):953.","journal-title":"Sci Rep"},{"issue":"suppl-1","key":"3827_CR13","doi-asserted-by":"publisher","first-page":"D535","DOI":"10.1093\/nar\/gkj109","volume":"34","author":"C Stark","year":"2006","unstructured":"Stark C, Breitkreutz BJ, Reguly T, Boucher L, Breitkreutz A, Tyers M. BioGRID: a general repository for interaction datasets. Nucleic Acids Res. 2006;34(suppl-1):D535\u20139.","journal-title":"Nucleic Acids Res"},{"issue":"1","key":"3827_CR14","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1186\/1752-0509-6-92","volume":"6","author":"J Das","year":"2012","unstructured":"Das J, Yu H. HINT: high-quality protein interactomes and their applications in understanding human disease. BMC Syst Biol. 2012;6(1):92.","journal-title":"BMC Syst Biol"},{"issue":"14","key":"3827_CR15","doi-asserted-by":"publisher","first-page":"2409","DOI":"10.1093\/bioinformatics\/btv161","volume":"31","author":"V Vijayan","year":"2015","unstructured":"Vijayan V, Saraph V, Milenkovi\u0107 T. MAGNA++: maximizing accuracy in global network alignment via both node and edge conservation. Bioinformatics. 2015;31(14):2409\u201311.","journal-title":"Bioinformatics"},{"issue":"35","key":"3827_CR16","doi-asserted-by":"publisher","first-page":"12763","DOI":"10.1073\/pnas.0806627105","volume":"105","author":"R Singh","year":"2008","unstructured":"Singh R, Xu J, Berger B. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proc Nat Acad Sci. 2008;105(35):12763\u20138.","journal-title":"Proc Nat Acad Sci"},{"issue":"21","key":"3827_CR17","doi-asserted-by":"publisher","first-page":"2765","DOI":"10.1093\/bioinformatics\/btt486","volume":"29","author":"L Chindelevitch","year":"2013","unstructured":"Chindelevitch L, Ma CY, Liao CS, Berger B. Optimizing a global alignment of protein interaction networks. Bioinformatics. 2013;29(21):2765\u201373.","journal-title":"Bioinformatics"},{"issue":"23","key":"3827_CR18","doi-asserted-by":"publisher","first-page":"3105","DOI":"10.1093\/bioinformatics\/bts592","volume":"28","author":"R Patro","year":"2012","unstructured":"Patro R, Kingsford C. Global network alignment using multiscale spectral signatures. Bioinformatics. 2012;28(23):3105\u201314.","journal-title":"Bioinformatics"},{"issue":"9","key":"3827_CR19","doi-asserted-by":"publisher","first-page":"1239","DOI":"10.1093\/bioinformatics\/bts119","volume":"28","author":"HT Phan","year":"2012","unstructured":"Phan HT, Sternberg MJ. PINALOG: a novel approach to align protein interaction networks-implications for complex detection and function prediction. Bioinformatics. 2012;28(9):1239\u201345.","journal-title":"Bioinformatics"},{"issue":"13","key":"3827_CR20","doi-asserted-by":"publisher","first-page":"2182","DOI":"10.1093\/bioinformatics\/btv130","volume":"31","author":"N Malod-Dognin","year":"2015","unstructured":"Malod-Dognin N, Pr\u017eulj N. L-GRAAL: lagrangian graphlet-based network aligner. Bioinformatics. 2015;31(13):2182\u20139.","journal-title":"Bioinformatics"},{"key":"3827_CR21","doi-asserted-by":"crossref","unstructured":"Crawford J, Milenkovi\u0107 T. Great: graphlet edge-based network alignment. IEEE; 2015. p. 220\u2013227.","DOI":"10.1109\/BIBM.2015.7359684"},{"issue":"7","key":"3827_CR22","doi-asserted-by":"publisher","first-page":"917","DOI":"10.1093\/bioinformatics\/btt071","volume":"29","author":"AE Alada\u011f","year":"2013","unstructured":"Alada\u011f AE, Erten C. SPINAL: scalable protein interaction network alignment. Bioinformatics. 2013;29(7):917\u201324.","journal-title":"Bioinformatics"},{"issue":"10","key":"3827_CR23","doi-asserted-by":"publisher","first-page":"1274","DOI":"10.1093\/bioinformatics\/btm087","volume":"23","author":"JZ Wang","year":"2007","unstructured":"Wang JZ, Du Z, Payattakool R, Yu PS, Chen CF. A new method to measure the semantic similarity of GO terms. Bioinformatics. 2007;23(10):1274\u201381.","journal-title":"Bioinformatics"},{"key":"3827_CR24","first-page":"296","volume-title":"An information-theoretic definition of similarity","author":"D Lin","year":"1998","unstructured":"Lin D, et al. An information-theoretic definition of similarity, vol. 98. Princeton: Citeseer; 1998. p. 296\u2013304."},{"key":"3827_CR25","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1613\/jair.514","volume":"11","author":"P Resnik","year":"1999","unstructured":"Resnik P. Semantic similarity in a taxonomy: an information-based measure and its application to problems of ambiguity in natural language. J Artif Intell Res. 1999;11:95\u2013130.","journal-title":"J Artif Intell Res"},{"issue":"1","key":"3827_CR26","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1186\/1471-2105-7-302","volume":"7","author":"A Schlicker","year":"2006","unstructured":"Schlicker A, Domingues FS, Rahnenf\u00fchrer J, Lengauer T. A new measure for functional similarity of gene products based on gene ontology. BMC Bioinform. 2006;7(1):302.","journal-title":"BMC Bioinform"},{"issue":"1","key":"3827_CR27","doi-asserted-by":"publisher","first-page":"15107","DOI":"10.1038\/s41598-018-33219-y","volume":"8","author":"C Zhao","year":"2018","unstructured":"Zhao C, Wang Z. GOGO: an improved algorithm to measure the semantic similarity between gene ontology terms. Sci Rep. 2018;8(1):15107.","journal-title":"Sci Rep"},{"issue":"7","key":"3827_CR28","doi-asserted-by":"publisher","first-page":"976","DOI":"10.1093\/bioinformatics\/btq064","volume":"26","author":"G Yu","year":"2010","unstructured":"Yu G, Li F, Qin Y, Bo X, Wu Y, Wang S. GOSemSim: an R package for measuring semantic similarity among GO terms and gene products. Bioinformatics. 2010;26(7):976\u20138.","journal-title":"Bioinformatics"},{"issue":"suppl-2","key":"3827_CR29","doi-asserted-by":"publisher","first-page":"W345","DOI":"10.1093\/nar\/gkp463","volume":"37","author":"Z Du","year":"2009","unstructured":"Du Z, Li L, Chen CF, Yu PS, Wang JZ. G-SESAME: web tools for GO-term-based gene similarity analysis and knowledge discovery. Nucleic Acids Res. 2009;37(suppl-2):W345\u20139.","journal-title":"Nucleic Acids Res"},{"issue":"1","key":"3827_CR30","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1186\/s12859-017-1600-5","volume":"18","author":"Q Wei","year":"2017","unstructured":"Wei Q, Khan IK, Ding Z, Yerneni S, Kihara D. NaviGO: interactive tool for visualization and functional similarity and coherence analysis with gene ontology. BMC Bioinform. 2017;18(1):177.","journal-title":"BMC Bioinform"},{"issue":"1","key":"3827_CR31","doi-asserted-by":"publisher","first-page":"1692","DOI":"10.1038\/s41598-018-37119-z","volume":"9","author":"DM Bis-Brewer","year":"2019","unstructured":"Bis-Brewer DM, Danzi MC, Wuchty S, Z\u00fcchner S. A network biology approach to unraveling inherited axonopathies. Sci Rep. 2019;9(1):1692.","journal-title":"Sci Rep"},{"issue":"1","key":"3827_CR32","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1093\/aob\/mcy237","volume":"124","author":"M Bouzid","year":"2019","unstructured":"Bouzid M, He F, Schmitz G, H\u00e4usler RE, Weber APM, Mettler-Altmann T, et al. Arabidopsis species deploy distinct strategies to cope with drought stress. Ann Bot. 2019;124(1):27\u201340.","journal-title":"Ann Bot"},{"issue":"5","key":"3827_CR33","first-page":"798","volume":"18","author":"X Peng","year":"2016","unstructured":"Peng X, Wang J, Peng W, Wu FX, Pan Y. Protein-protein interactions: detection, reliability assessment and applications. Brief Bioinform. 2016;18(5):798\u2013819.","journal-title":"Brief Bioinform"},{"issue":"4","key":"3827_CR34","doi-asserted-by":"publisher","first-page":"e59","DOI":"10.1371\/journal.pcbi.0030059","volume":"3","author":"H Yu","year":"2007","unstructured":"Yu H, Kim PM, Sprecher E, Trifonov V, Gerstein M. The importance of bottlenecks in protein networks: correlation with gene essentiality and expression dynamics. PLoS Comput Biol. 2007;3(4):e59.","journal-title":"PLoS Comput Biol"},{"issue":"6995","key":"3827_CR35","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1038\/nature02555","volume":"430","author":"JDJ Han","year":"2004","unstructured":"Han JDJ, Bertin N, Hao T, Goldberg DS, Berriz GF, Zhang LV, et al. Evidence for dynamically organized modularity in the yeast protein-protein interaction network. Nature. 2004;430(6995):88.","journal-title":"Nature"},{"key":"3827_CR36","first-page":"73","volume-title":"Fast and accurate NCBI BLASTP: acceleration with multiphase FPGA-based prefiltering","author":"A Mahram","year":"2010","unstructured":"Mahram A, Herbordt MC. Fast and accurate NCBI BLASTP: acceleration with multiphase FPGA-based prefiltering. Cambridge: ACM; 2010. p. 73\u201382."},{"issue":"7","key":"3827_CR37","doi-asserted-by":"publisher","first-page":"2302","DOI":"10.1093\/nar\/gki524","volume":"33","author":"Y Zhang","year":"2005","unstructured":"Zhang Y, Skolnick J. TM-align: a protein structure alignment algorithm based on the TM-score. Nucleic Acids Res. 2005;33(7):2302\u20139.","journal-title":"Nucleic Acids Res"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-020-03827-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-020-03827-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-020-03827-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,7]],"date-time":"2020-11-07T17:03:03Z","timestamp":1604768583000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-020-03827-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,4]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["3827"],"URL":"https:\/\/doi.org\/10.1186\/s12859-020-03827-5","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,4]]},"assertion":[{"value":"5 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"500"}}