Scalable remote homology detection and fold recognition in massive protein networks

Raphael Petegrosso, Zhuliu Li, Molly A. Srour, Yousef Saad, Wei Zhang, Rui Kuang

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


The global connectivities in very large protein similarity networks contain traces of evolution among the proteins for detecting protein remote evolutionary relations or structural similarities. To investigate how well a protein network captures the evolutionary information, a key limitation is the intensive computation of pairwise sequence similarities needed to construct very large protein networks. In this article, we introduce label propagation on low-rank kernel approximation (LP-LOKA) for searching massively large protein networks. LP-LOKA propagates initial protein similarities in a low-rank graph by Nyström approximation without computing all pairwise similarities. With scalable parallel implementations based on distributed-memory using message-passing interface and Apache-Hadoop/Spark on cloud, LP-LOKA can search protein networks with one million proteins or more. In the experiments on Swiss-Prot/ADDA/CASP data, LP-LOKA significantly improved protein ranking over the widely used HMM-HMM or profile-sequence alignment methods utilizing large protein networks. It was observed that the larger the protein similarity network, the better the performance, especially on relatively small protein superfamilies and folds. The results suggest that computing massively large protein network is necessary to meet the growing need of annotating proteins from newly sequenced species and LP-LOKA is both scalable and accurate for searching massively large protein networks.

Original languageEnglish (US)
Pages (from-to)478-491
Number of pages14
JournalProteins: Structure, Function and Bioinformatics
Issue number6
StatePublished - Jun 2019

Bibliographical note

Funding Information:
National Cancer Institute, Grant/Award Number: NIH R01CA225435; National Science Foundations, USA, Grant/Award Number: NSF III 1149697; CAPES Foundation, Ministry of Education of Brazil, Grant/Award Number: BEX 13250/13-2

Publisher Copyright:
© 2019 Wiley Periodicals, Inc.


  • distributed and cloud computing
  • fold recognition
  • machine learning
  • protein networks
  • remote homology detection


Dive into the research topics of 'Scalable remote homology detection and fold recognition in massive protein networks'. Together they form a unique fingerprint.

Cite this