Implementação e Avaliação de Desempenho do LCS Paralelo em Cluster Multicore
Abstract
Finding the longest common subsequence (LCS) is an important technique in DNA sequence alignment. Through dynamic programming it is possible n), to find the exact solution to the LCS, with space and time complexity of O(m x N), being m e n the sequence sizes. Parallel algorithms are essential, since large sequences require too much time and memory to be processed sequentially. Thus, the aim of this work is to implement and evaluate different parallel solutions for distributed memory machines, so that the amount of memory is equally divided among the various processing nodes.
References
Alves, C. E. R., Cáceres, E. N., Dehne, F., , and Song, S. W. (2003). A parallel wavefront algorithm for efcient biological sequence comparison. In Lecture Notes in Computer Science, pages 249–258.
Alves, T. A., Marzulo, L. A. J., and Franca, F. M. G. (2013). Unleashing parallelism in longest common subsequence using dataow. In 4th Workshop on Applications for Multi-Core Architectures.
Axelson-Fisk, M. (2010). Comparative Gene Finding: models, algorithms and implementation. Springer.
Batista, R. and Magalhaes, A. (2006). An exact and parallel strategy for local biological sequence alignment in user-restricted memory space. In Cluster 2006, pages 1–10.
Butenhof, D. R. (1997). Programming with POSIX threads. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
Cehn, C. and Schmidt, B. (2003). Computing large-scale alignments on a multi-cluster. In Cluster 2003, pages 38–45.
Chen, Y., Yu, S., and Leng, M. (2006). Parallel sequence alignment algorithm for clustering system. In Shangai. Knowledge Enterprise: Intelligent Strategies in Product Design, Manufacturing, and Management, pages 311–321.
D. A. Benson, M. Cavanaugh, K. C. I. K.-M. D. J. L. J. O. and Sayers, E. W. (2013). Genbank. Nucleic Acids Research, 41:36–42.
Dagum, L. and Menon, R. (1998). OpenMP: an industry standard API for shared-memory programming. IEEE Computational Science and Engineering, 5(1):46–55.
Dasgupta, S., Papadimitriou, C., and Vazirani, U. (2006). Algorithms. McGraw-Hill.
Martins, W., Cuvillo, J., Useche, F., Theobald, K., and Gao, G. (2001). A multithreaded parallel implementation of a dynamic programming algorithm for sequence comparison. In PSB proceedings, pages 311–322.
Naveed, T., Siddiqui, S., and Ahmed, S. (2005). Parallel needleman-wunsch algorithm for grid. In Proceedings of the PAK-US International Symposium on High Capacity Optical Networks and Enabling Technologies, pages 19–21.
Needleman, S. B. and Wunsch, C. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol, 48(3):443–453.
openMPI (último acesso 31/07/2014). open MPI. http://www.open-mpi.org/.
Rajko, S. and Aluru, S. (2004). Space and time optimal parallel sequence alignments. IEEE Trans. Parallel Distrib, 15(12):1070–1081.
Reinders, J. (2007). Intel threading building blocks : outtting C++ for multi-core processor parallelism. O’Reilly.
Seguel, J. and Torres, C. (2011). Parallelization of needleman-wunsch string alignment method. In BIOCOMP, 2011, pages 239–244.
Smith, T. F. and Waterman, M. (1981). Identication of common molecular subsequences. J. Mol. Biol, 147(1):195–197.
Steinfadt, U., Scherger, M., and Baker, J. W. (2006). A local sequence alignment algorithm using an associative model of parallel computation. In Proc. of IASTED Computational and Systems Biology, pages 38–43.
TBB FlowGraph (último acesso 31/07/2014). TBB FlowGraph. http: //www.threadingbuildingblocks.org/docs/help/reference/ flow_graph.htm.
Wagner, R. A. and Fischer, M. J. (1974). The string-to-string correction problem. J. ACM, 21(1):168–173.
Yap, T. K., Frieder, O., and Martino, R. L. (1998). Parallel computation in biological sequence analysis. IEEE Trans. Parallel Distrib, 9(3):283–294.
Alves, T. A., Marzulo, L. A. J., and Franca, F. M. G. (2013). Unleashing parallelism in longest common subsequence using dataow. In 4th Workshop on Applications for Multi-Core Architectures.
Axelson-Fisk, M. (2010). Comparative Gene Finding: models, algorithms and implementation. Springer.
Batista, R. and Magalhaes, A. (2006). An exact and parallel strategy for local biological sequence alignment in user-restricted memory space. In Cluster 2006, pages 1–10.
Butenhof, D. R. (1997). Programming with POSIX threads. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
Cehn, C. and Schmidt, B. (2003). Computing large-scale alignments on a multi-cluster. In Cluster 2003, pages 38–45.
Chen, Y., Yu, S., and Leng, M. (2006). Parallel sequence alignment algorithm for clustering system. In Shangai. Knowledge Enterprise: Intelligent Strategies in Product Design, Manufacturing, and Management, pages 311–321.
D. A. Benson, M. Cavanaugh, K. C. I. K.-M. D. J. L. J. O. and Sayers, E. W. (2013). Genbank. Nucleic Acids Research, 41:36–42.
Dagum, L. and Menon, R. (1998). OpenMP: an industry standard API for shared-memory programming. IEEE Computational Science and Engineering, 5(1):46–55.
Dasgupta, S., Papadimitriou, C., and Vazirani, U. (2006). Algorithms. McGraw-Hill.
Martins, W., Cuvillo, J., Useche, F., Theobald, K., and Gao, G. (2001). A multithreaded parallel implementation of a dynamic programming algorithm for sequence comparison. In PSB proceedings, pages 311–322.
Naveed, T., Siddiqui, S., and Ahmed, S. (2005). Parallel needleman-wunsch algorithm for grid. In Proceedings of the PAK-US International Symposium on High Capacity Optical Networks and Enabling Technologies, pages 19–21.
Needleman, S. B. and Wunsch, C. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol, 48(3):443–453.
openMPI (último acesso 31/07/2014). open MPI. http://www.open-mpi.org/.
Rajko, S. and Aluru, S. (2004). Space and time optimal parallel sequence alignments. IEEE Trans. Parallel Distrib, 15(12):1070–1081.
Reinders, J. (2007). Intel threading building blocks : outtting C++ for multi-core processor parallelism. O’Reilly.
Seguel, J. and Torres, C. (2011). Parallelization of needleman-wunsch string alignment method. In BIOCOMP, 2011, pages 239–244.
Smith, T. F. and Waterman, M. (1981). Identication of common molecular subsequences. J. Mol. Biol, 147(1):195–197.
Steinfadt, U., Scherger, M., and Baker, J. W. (2006). A local sequence alignment algorithm using an associative model of parallel computation. In Proc. of IASTED Computational and Systems Biology, pages 38–43.
TBB FlowGraph (último acesso 31/07/2014). TBB FlowGraph. http: //www.threadingbuildingblocks.org/docs/help/reference/ flow_graph.htm.
Wagner, R. A. and Fischer, M. J. (1974). The string-to-string correction problem. J. ACM, 21(1):168–173.
Yap, T. K., Frieder, O., and Martino, R. L. (1998). Parallel computation in biological sequence analysis. IEEE Trans. Parallel Distrib, 9(3):283–294.
Published
2014-10-08
How to Cite
LAUREDO, Alexandre et al.
Implementação e Avaliação de Desempenho do LCS Paralelo em Cluster Multicore.
Proceedings of the Symposium on High Performance Computing Systems (SSCAD), [S.l.], p. 27-38, oct. 2014.
ISSN 0000-0000.
Available at: <https://sol.sbc.org.br/index.php/sscad/article/view/14997>. Date accessed: 18 may 2024.
doi: https://doi.org/10.5753/wscad.2014.14997.
Section
Full Papers
