  Identifying similar protein sequences is a core step in many computational
biology pipelines such as detection of homologous protein sequences, generation
of similarity protein graphs for downstream analysis, functional annotation and
gene location. Performance and scalability of protein similarity searches have
proven to be a bottleneck in many bioinformatics pipelines due to increases in
cheap and abundant sequencing data. This work presents a new distributed-memory
software, PASTIS. PASTIS relies on sparse matrix computations for efficient
identification of possibly similar proteins. We use distributed sparse matrices
for scalability and show that the sparse matrix infrastructure is a great fit
for protein similarity searches when coupled with a fully-distributed
dictionary of sequences that allows remote sequence requests to be fulfilled.
Our algorithm incorporates the unique bias in amino acid sequence substitution
in searches without altering the basic sparse matrix model, and in turn,
achieves ideal scaling up to millions of protein sequences.
