Whole genome alignment using a multithreaded parallel implementation

Alignment of long DNA sequences is a challenging task due to its high demands for computational power and memory. We have developed a multithreaded parallel implementation of a sequence alignment algorithm that is able to align whole genomes with reliable output and reasonable cost. The implementation is based on a fine-grain multithreaded execution model, the EARTH model, which effectively tolerates latency through the overlapping of computation and communication. Human and mice mitochondrial genomes, human and Drosophila mitochondrial genomes are aligned respectively to demonstrate that the implementation can be used to align both closely related as well as less similar genomes. Results from Mycoplasma genitalium and Mycoplasma pneumoniae genomes, which are much larger than the tested mitochondrial genomes, are also presented. From the output, the homologous regions can be easily detected. This tool should facilitate alignment of syntenic regions, strain to strain comparisons, identification of regulatory elements and evolutionary comparisons as well. Keywords — Multithreading, Parallelism, Alignment, Genome, DNA. I