کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875080 | 1441472 | 2018 | 38 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
PA-Star: A disk-assisted parallel A-Star strategy with locality-sensitive hash for multiple sequence alignment
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: PA-Star: A disk-assisted parallel A-Star strategy with locality-sensitive hash for multiple sequence alignment PA-Star: A disk-assisted parallel A-Star strategy with locality-sensitive hash for multiple sequence alignment](/preview/png/6875080.png)
چکیده انگلیسی
Multiple Sequence Alignment (MSA) is a basic operation in Bioinformatics, and is used to highlight the similarities among a set of sequences. The MSA problem was proven NP-Hard, thus requiring a high amount of memory and computing power. This problem can be modeled as a search for the path with minimum cost in a graph, and the A-Star algorithm has been adapted to solve it sequentially and in parallel. The design of a parallel version for MSA with A-Star is subject to challenges such as irregular dependency pattern and substantial memory requirements. In this paper, we propose PA-Star, a locality-sensitive multithreaded strategy based on A-Star, which computes optimal MSAs using both RAM and disk to store nodes. The experimental results obtained in 3 different machines show that the optimizations used in PA-Star can achieve an acceleration of 1.88Ã in the serial execution, and the parallel execution can attain an acceleration of 5.52Ã with 8 cores. We also show that PA-Star outperforms a state-of-the-art MSA tool based on A-Star, executing up to 4.77Ã faster. Finally, we show that our disk-assisted strategy is able to retrieve the optimal alignment when other tools fail.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 112, Part 2, February 2018, Pages 154-165
Journal: Journal of Parallel and Distributed Computing - Volume 112, Part 2, February 2018, Pages 154-165
نویسندگان
Daniel Sundfeld, Caina Razzolini, George Teodoro, Azzedine Boukerche, Alba Cristina Magalhaes Alves de Melo,