Parallel reconstruction of neighbor-joining trees for large multiple sequence alignments using CUDA
School of Computer Engineering, Nanyang Technological University, Singapore 639798
Parallel and Distributed Processing Symposium, International, Vol. 0 (2009), pp. 1-8
@article{liu2009parallel,
title={Parallel reconstruction of neighbor-joining trees for large multiple sequence alignments using CUDA},
author={Liu, Y. and Schmidt, B. and Maskell, D.L.},
year={2009},
publisher={IEEE}
}
Computing large multiple protein sequence alignments using progressive alignment tools such as ClustalW requires several hours on state-of-the-art workstations. ClustalW uses a three-stage processing pipeline: (i) pairwise distance computation; (ii) phylogenetic tree reconstruction; and (iii) progressive multiple alignment computation. Previous work on accelerating ClustalW was mainly focused on parallelizing the first stage and achieved good speedups for a few hundred input sequences. However, if the input size grows to several thousand sequences, the second stage can dominate the overall runtime. In this paper, we present a new approach to accelerating this second stage using graphics processing units (GPUs). In order to derive an efficient mapping onto the GPU architecture, we present a parallelization of the neighbor-joining tree reconstruction algorithm using CUDA. Our experimental results show speedups of over 26× for large datasets compared to the sequential implementation.
November 27, 2010 by hgpu
