High-Performance Direct Pairwise Comparison of Large Genomic Sequences

Many applications in comparative genomics lend themselves to implementations that take advantage of common high-performance features in modern microprocessors. However, the common suggestion that a data-parallel, multithreaded, or high-throughput implementation is possible often ignores the complexity of actually creating such software. In this paper, we present two parallel algorithms for a classic comparative genomics algorithm, the dot plot. First, we describe a data-parallel algorithm that achieves speedups of up to 14.4x over the sequential version for large genomic comparisons. Then, we use the new algorithm as the base for a coarse-grained parallel version, suitable for multiprocessor and cluster environments, that scales linearly with the number of processors. These speedups introduce the opportunity to perform full pairwise comparisons on entire genomes on a much larger scale than previously possible. We also present the experimental, model-driven approach used to develop the algorithm that allowed us to carefully study and evaluate implementation options and to fully understand the parameters affecting its performance