Parallel A-Star Multiple Sequence Alignment with Locality-Sensitive Hash Functions

In this paper, we propose and evaluate a parallel solution for the exact Multiple Sequence Alignment problem based on the A-Star algorithm. In our parallel solution, we use a multi-index data structure, templates and a locality-sensitive hash function. The results were collected in two machines (4 cores and 32 cores), with real and synthetic sequence sets ranging from 3 to 14 sequences. We show that our parallel solution executes 2.89× and 4.77× faster than a state-of-the-art parallel MSA tool, with a proportional increase in memory usage, when comparing 2 hard instances of the benchmark Bali base reference set 1.