Genalign — A high performance implementation for aligning the compressed DNA sequences

摘要

In molecular biology, sequence alignment is a way of arranging DNA, RNA or protein sequences to identify regions of similarity between the sequences. However, this is a challenging problem since the DNA sequences are huge in size and the databases are growing at an exponential rate. It requires tremendous amount of memory and large computational power. For example, the human genome in raw format ranges from 2 to 30 Tera-bytes. The inherent property of DNA is that it contains many repeats which makes it highly compressible. This paper presents a new approach of aligning the sequences after compressing them. The alignment consists of both ungapped and gapped alignment. Multi-cores and GPUs can be used to align these huge sequences quickly on the compressed sequences. The focus mainly is on aligning the huge sequences accurately. The ungapped alignment achieves a speedup of upto 56 on K20 Kepler GPUs and the gapped alignment achieves a speedup of upto 15 on multi-cores.