موازی‌سازی کارا و تسریع عملیات انطباق رشته‌ها بر روی بستر پردازنده های چند هسته ای

نویسندگان
میلاد غفوری 1
آرمین احمدزاده 1
سعید گرگین 2
1 پژوهشگر، علوم کامپیوتر، پژوهشکده علوم کامپیوتر، پژوهشگاه دانشهای بنیادی، تهران، ایران
2 استادیار، مهندسی کامپیوتر، پژوهشکده برق و فناوری اطلاعات، سازمان پژوهشهای علمی و صنعتی ایران، تهران، ایران
چکیده
انطباق رشته‌ها یک بحث پایه‌ای و پرکاربرد در بیوانفورماتیک است که جهت یافتن میزان مشابهت توالی‌های آمینواسیدی و یا رشته‌های دی.ان.ای از آن استفاده می‌شود. عمل انطباق دو رشته با یکدیگر یک عمل پایه‌ای است که در انطباق‌های چندگانه نیز از آن استفاده می‌شود. یکی از الگوریتم‌های انطباق دو رشته، الگوریتم نیدلمن-وانچ است که در آن از شیوه‌ی برنامه‌سازی پویا برای انجام این عملیات استفاده می‌شود. از چالش‌های مطرح در این الگوریتم، بالا بودن پیچیدگی زمانی آن است که جهت بهبود در سرعت اجرای این الگوریتم از راه‌کارهایی موازی می‌توان استفاده نمود. ازاین‌رو با ظهور پردازنده‌های چندهسته‌ای و امکان انجام محاسبات به شکل موازی می‌توان تسریع قابل‌ملاحظه‌ای را به دست آورد. بر اساس روش‌های موازی‌سازی موجود برای این الگوریتم، در هر گام خانه‌های آرایه‌ی به‌کاررفته در روش برنامه‌سازی پویا یک قطر به‌طور هم‌زمان و موازی تکمیل می‌شود. در این مقاله با یک تغییر دیدگاه نسبت به مسئله و در نظر گرفتن یک تصور گراف‌گونه، روشی ارائه شده ‌است تا به نسبت روش‌های پیشین تسریع مناسبی را ارائه کند. نتایج به‌دست‌آمده نشان می‌دهد، در این پیاده‌سازی بهبود عملکردی تا حدود 5.9 برابر نسبت به پیاده‌سازی‌های پیشین حاصل می‌گردد..

کلیدواژه‌ها

  • J. Tong, J. Pei and N. V. Grishin, "SFESA: a web server for pairwise alignment refinement by secondary structure shifts," BMC bioinformatics, vol. 16, p. 282, 2015.
  • "A One-Letter Notation for Amino Acid Sequences," IUPAC-IUB Commission on Biochemical Nomenclature (CBN), vol. 5, no. 2, p. 151–153, 1968.
  • F.Sanger, "The Arrangement of Amino Acids in Proteins," Advances in Protein Chemistry and Structural Biology, vol. 7, pp. 1-67, 1952.
  • R. Aasland, C. Abrams, C. Ampe, L. J. Ball, M. T. Bedford, G. Cesareni, M. Gimona, J. H. Hurley, T. Jarchau, V.-P. Lehto, M. A. Lemmon, R. Linding, B. J. Mayer, M. Nagai, M. Sudol, U. Walter and Steve, "Normalization of nomenclature for peptide motifs as ligands of modular protein domains," FEBS Letters, vol. 513, no. 1, pp. 141-144, 2002.
  • M. J. Bower, F. Cohen and R. Dunbrack, "Prediction of protein side-chain rotamers from a backbone-dependent rotamer library: a new homology modeling tool1," Journal of Molecular Biology, vol. 267, pp. 1268-1282, 1997.
  • S. Gálvez, D. Díaz, P. Hernández, F. J. Esteban, J. A. Caballero and G. Dorado, "Next-Generation Bioinformatics: Using Many-Core Processor Architecture to Develop a Web Service for Sequence Alignment," Bioinformatics, vol. 26, no. 5, p. 683–686, 2010.
  • S. Che, J. W. Sheaffer, M. Boyer, L. G. Szafaryn, L. Wang and K. Skadron, "A Characterization of the Rodinia Benchmark Suite with Comparison to Contemporary CMP Workloads," In Proceedings of the IEEE International Symposium on Workload Characterization (IISWC"10), pp. 1-11, 2010.
  • S. Che, M. Boyer, J. Meng, D. Tarjan, J. W. Sheaffer, S.-H. Lee and K. Skadron, "Rodinia: A Benchmark Suite for Heterogeneous Computing," Workload Characterization, 2009. IISWC 2009. IEEE International Symposium on, pp. 44-54, 2009.
  • R. Chenna, H. Sugawara, T. Koike, R. Lopez, T. J. Gibson, D. G. Higgins and J. D. Thompson, "Multiple sequence alignment with the Clustal series of programs," Nucleic Acids Research, vol. 31, no. 13, pp. 3497-3500, 2003.
  • V. O. Polyanovsky, M. A. Roytberg and V. G. Tumanyan, "Comparative analysis of the quality of a global algorithm and a local algorithm for alignment of two sequences," Algorithms for Molecular Biology, vol. 6, p. 25, 2011.
  • S. A.Shehab, A. Keshk and H. Mahgoub, "Fast Dynamic Algorithm for Sequence Alignment based on Bioinformatics," International Journal of Computer Applications, vol. 37, pp. 54-61, 2012.
  • X. Xia, Bioinformatics and the Cell. Springer, Boston, MA, pp. 23-48, 2007.
  • S. B. NEEDLEMAN and C. D. Wunsch, "A general method applicable to the search for similarities in the amino acid sequence of two proteins," Journal of Molecular Biology, vol. 48, no. 3, pp. 443–453, 1970.
  • S. HENIKOFF and J. G. HENIKOFF, "Amino acid substitution matrices from protein blocks," Proceedings of the National Academy of Sciences of the United States of America, vol. 89, no. 22, pp. 10915-10919, 1992.
  • D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences," Communications of the ACM, vol. 18, no. 6, pp. 341-343, 1975.
  • S. Maleki, M. Musuvathi and T. Mytkowicz, "Parallelizing dynamic programming through rank convergence," PPoPP "14 Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming, vol. 49, no. 8, pp. 219-232, 2014.
  • S. Maleki, M. Musuvathi and T. Mytkowicz, "Efficient parallelization using rank convergence in dynamic programming algorithms," Communications of the ACM, vol. 59, pp. 85-92, 2016.
  • S. A. Manavski and G. Valle, "CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment," BMC bioinformatics, vol. 9, 2008.
  • H. Hu and Z. Ji, "Parallelization of Needleman-Wunsch Algorithm Based on Software Pipelining," International Journal of Engineering and Manufacturing (IJEM), vol. 1, pp. 59-64, 2011.
  • D. Li and M. Becchi, "Multiple Pairwise Sequence Alignments with the Needleman-Wunsch Algorithm on GPU," in High Performance Computing, Networking, Storage and Analysis (SCC), 2012 SC Companion:, Salt Lake City, UT, 2012.
  • T. R. P. Siriwardena and D. N. Ranasinghe, "Accelerating global sequence alignment using CUDA compatible multi-core GPU," Information and Automation for Sustainability (ICIAFs), 2010 5th International Conference on, pp. 201-206, 2010.
  • O. Trelles-Salazar, E. Zapata and J. Carazo, "On an efficient parallelization of exhaustive sequence comparison algorithms on message passing architectures," Bioinformatics, vol. 10, no. 5, pp. 509-511, 1994.
  • S. Vinogradov, J. Fedorova, D. Curran, S. McIntosh-Smith and J. Cownie, "OpenMP 4.0 vs. OpenCL: Performance comparison," in Paper presented at The OpenMP Developers Conference (OpenMPCon), Aachen, Germany, 2015.
علوم رایانش و فناوری اطلاعات
دوره 17، شماره 1
بهار و تابستان
بهار 1398