IEEE Transactions on Parallel and Distributed Systems · 2012 · 71 citations · 34 references
ComputingBioinformaticsHigh-performance ComputingComputational BiologyParallel ComputingSequence AnalysisComputational GenomicsData ParallelismGenome AlignmentGraphics Processing Unit ComputingHardware AccelerationSequence AlignmentBiological Sequence AlignmentGpu Parallel AlgorithmsLocal AlignmentOptimal AlignmentParallel Algorithm ScalabilityScalable ComputingSmith - Waterman AlgorithmSmith-waterman Algorithm
In Genome Projects, biological sequences are aligned thousands of times, in a daily basis. The Smith-Waterman algorithm is able to retrieve the optimal local alignment with quadratic time and space complexity. So far, aligning huge sequences, such as whole chromosomes, with the Smith-Waterman algorithm has been regarded as unfeasible, due to huge computing and memory requirements. However, high-performance computing platforms such as GPUs are making it possible to obtain the optimal result for huge sequences in reasonable time. In this paper, we propose and evaluate CUDAlign 2.1, a parallel algorithm that uses GPU to align huge sequences, executing the Smith-Waterman algorithm combined with Myers-Miller, with linear space complexity. In order to achieve that, we propose optimizations which are able to reduce significantly the amount of data processed, while enforcing full parallelism most of the time. Using the NVIDIA GTX 560 Ti board and comparing real DNA sequences that range from 162 KBP (Thousand Base Pairs) to 59 MBP (Million Base Pairs), we show that CUDAlign 2.1 is scalable. Also, we show that CUDAlign 2.1 is able to produce the optimal alignment between the chimpanzee chromosome 22 (33 MBP) and the human chromosome 21 (47 MBP) in 8.4 hours and the optimal alignment between the chimpanzee chromosome Y (24 MBP) and the human chromosome Y (59 MBP) in 13.1 hours.
34
Julie Thompson, Desmond G. Higgins, Toby J. Gibson · Nucleic Acids Research · 1994 · 64.9K citations · Full text
Versatile and open software for comparing large genomes
Stefan Kurtz, Adam M. Phillippy, Arthur L. Delcher et al. · Genome biology · 2004 · 5.8K citations · Full text
An improved algorithm for matching biological sequences
Osamu Gotoh · Journal of Molecular Biology · 1982 · 1.8K citations
Optimal alignments in linear space
Eugene W. Myers, Webb Miller · Computer applications in the biosciences · 1988 · 1.2K citations