11526

QuickProbs – A Fast Multiple Sequence Alignment Algorithm Designed for Graphics Processors

Adam Gudys, Sebastian Deorowicz
Institute of Informatics, Faculty of Automatic Control, Electronics and Computer Science, Silesian University of Technology, Gliwice, Poland
PLoS ONE 9(2): e88901, 2014

@article{gudys2014quickprobs,

   title={QuickProbs-A Fast Multiple Sequence Alignment Algorithm Designed for Graphics Processors},

   author={Gudy{‘s}, Adam and Deorowicz, Sebastian},

   journal={PLOS ONE},

   volume={9},

   number={2},

   pages={e88901},

   year={2014},

   publisher={Public Library of Science}

}

Download Download (PDF)   View View   Source Source   Source codes Source codes

Package:

1204

views

Multiple sequence alignment is a crucial task in a number of biological analyses like secondary structure prediction, domain searching, phylogeny, etc. MSAProbs is currently the most accurate alignment algorithm, but its effectiveness is obtained at the expense of computational time. In the paper we present QuickProbs, the variant of MSAProbs customised for graphics processors. We selected the two most time consuming stages of MSAProbs to be redesigned for GPU execution: the posterior matrices calculation and the consistency transformation. Experiments on three popular benchmarks (BAliBASE, PREFAB, OXBench-X) on quad-core PC equipped with high-end graphics card show QuickProbs to be 5.7 to 9.7 times faster than original CPU-parallel MSAProbs. Additional tests performed on several protein families from Pfam database give overall speed-up of 6.7. Compared to other algorithms like MAFFT, MUSCLE, or ClustalW, QuickProbs proved to be much more accurate at similar speed. Additionally we introduce a tuned variant of QuickProbs which is significantly more accurate on sets of distantly related sequences than MSAProbs without exceeding its computation time. The GPU part of QuickProbs was implemented in OpenCL, thus the package is suitable for graphics processors produced by all major vendors.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: