  Mass spectrometry (MS) based omics data analysis require significant time and
resources. To date, few parallel algorithms have been proposed for deducing
peptides from mass spectrometry-based data. However, these parallel algorithms
were designed, and developed when the amount of data that needed to be
processed was smaller in scale. In this paper, we prove that the communication
bound that is reached by the \emph{existing} parallel algorithms is
$\Omega(mn+2r\frac{q}{p})$, where $m$ and $n$ are the dimensions of the
theoretical database matrix, $q$ and $r$ are dimensions of spectra, and $p$ is
the number of processors. We further prove that communication-optimal strategy
with fast-memory $\sqrt{M} = mn + \frac{2qr}{p}$ can achieve
$\Omega({\frac{2mnq}{p}})$ but is not achieved by any existing parallel
proteomics algorithms till date. To validate our claim, we performed a
meta-analysis of published parallel algorithms, and their performance results.
We show that sub-optimal speedups with increasing number of processors is a
direct consequence of not achieving the communication lower-bounds. We further
validate our claim by performing experiments which demonstrate the
communication bounds that are proved in this paper. Consequently, we assert
that next-generation of \emph{provable}, and demonstrated superior parallel
algorithms are urgently needed for MS based large systems-biology studies
especially for meta-proteomics, proteogenomic, microbiome, and proteomics for
non-model organisms. Our hope is that this paper will excite the parallel
computing community to further investigate parallel algorithms for highly
influential MS based omics problems.
