Implementação e Avaliação de Desempenho do LCS Paralelo em Cluster Multicore
Resumo
Encontrar a maior subsequência comum (LCS) entre duas sequências é uma técnica muito utilizada para o alinhamento de sequências de DNA. Através da programação dinâmica se consegue a solução exata para o LCS, com complexidade de tempo e espaço O(m x n), onde m e n são os tamanhos das sequências. Algoritmos paralelos são fundamentais, tanto pelo tempo de processamento, quanto pela quantidade de memória necessária para processar sequências grandes. Logo, o objetivo deste trabalho é implementar e avaliar quatro versões paralelas do LCS para máquinas com memória distribuída, otimizando o paralelismo entre nós e também dentro de cada nó e buscando uso homogêneo de memória nos nós de processamento.
Referências
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.
Publicado
08/10/2014
Como Citar
LAUREDO, Alexandre; DE MESQUITA, Joyce; SANTIAGO, Leandro; DE CASTRO, Maria Clicia; SENA, Alexandre; MARZULO, Leandro.
Implementação e Avaliação de Desempenho do LCS Paralelo em Cluster Multicore. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 15. , 2014, São José dos Campos.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2014
.
p. 27-38.
DOI: https://doi.org/10.5753/wscad.2014.14997.
