Par-PSSE: Software for Pairwise statistical significance estimation in parallel for local sequence alignment

Yuhong Zhang*, Md Mostofa Ali Patwary, Sanchit Misra, Ankit Agrawal, Wei keng Liao, Zhiguang Qin, Alok Choudhary

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


Pairwise statistical significance (PSS) has been recognized as a very useful method for homology detection. It can help in estimating whether the output of sequence alignment is evolutionarily link or just arisen by accident. However, pairwise statistical significance estimation (PSSE) poses a big challenge in terms of performance and scalability since it is both computationally intensive and data intensive to construct the empirical score distribution during the estimation. This paper presents a software library for estimating pairwise statistical significance in parallel, named Par-PSSE, implemented in C++ using OpenMP, MPI paradigms and their hybrids. Further, we apply the parallelization technique to estimate non-conservative PSS using standard, sequence-specific, and position-specific substitution matrices. These extensions have been found superior compared to the standard pairwise statistical significance in term of retrieval accuracy. Through distributing the compute-intensive kernels of the pairwise statistical significance estimation across multiple computational units, we achieve a speedup of up to 621.73× over the corresponding sequential implementation when using1024 cores.

Original languageEnglish (US)
Pages (from-to)200-208
Number of pages9
JournalInternational Journal of Digital Content Technology and its Applications
Issue number5
StatePublished - Mar 2012


  • Hybrid paradigm
  • MPI
  • Multi-core
  • OpenMP
  • Pairwise statistical significance

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications


Dive into the research topics of 'Par-PSSE: Software for Pairwise statistical significance estimation in parallel for local sequence alignment'. Together they form a unique fingerprint.

Cite this