1700

Parallel reconstruction of neighbor-joining trees for large multiple sequence alignments using CUDA

Yongchao Liu, Bertil Schmidt, Douglas L. Maskell
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}

}

Download Download (PDF)   View View   Source Source   

633

views

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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: