Efficient BSP/CGM algorithms for the maximum subsequence sum and related problems

Página do item simplificado
dc.creatorLima, Anderson Corrêa de
dc.creatorBranco, Rodrigo Gonçalves de
dc.creatorC´aceres, Edson Norberto
dc.creatorGaioso, Roussian Di Ramos Alves
dc.creatorAquino, Samuel Benjoino Ferraz
dc.creatorSong, Siang Wun
dc.creatorMartins, Wellington Santos
dc.date.accessioned2018-06-08T11:15:24Z
dc.date.available2018-06-08T11:15:24Z
dc.date.issued2015
dc.description.abstractGiven a sequence of n numbers, with at least one positive value, the maximum subsequence sum problem consists in finding the contiguous subsequence with the largest sum or score, among all derived subsequences of the original sequence. Several scientific applications have used algorithms that solve the maximum subsequence sum. Particularly in Computational Biology, these algorithms can help in the tasks of identification of transmembrane domains and in the search for GC-content regions, a required activity in the operation of pathogenicity islands location. The sequential algorithm that solves this problem has O n time complexity. In this work we present BSP/CGM parallel algorithms to solve the maximum subsequence sum problem and three related problems: the maximum longest subsequence sum, the maximum shortest subsequence sum and the number of disjoints subsequences of maximum sum. To the best of our knowledge there are no parallel BSP/CGM algorithms for these related problems. Our algorithms use p processors and require O n/p parallel time with a constant number of communication rounds for the algorithm of the maximum subsequence sum and O log p communication rounds, with O n/p local computation per round, for the algorithm of the related problems. We implemented the algorithms on a cluster of computers using MPI and on a machine with GPU using CUDA, both with good speed-ups.pt_BR
dc.identifier.citationLIMA, Anderson C.; BRANCO, Rodrigo G.; CÁCERES, Edson N.; GAIOSO, Roussian R. A.; FERRAZ, Samuel ; SONG, Siang W. ; MARTINS, Wellington S. Efficient BSP/CGM algorithms for the maximum subsequence sum and related problems. Procedia Computer Science, New York, v. 51, p. 2754-2758, 2015.pt_BR
dc.identifier.doi10.1016/j.procs.2015.05.421
dc.identifier.issne- 1877-0509
dc.identifier.urihttp://repositorio.bc.ufg.br/handle/ri/15167
dc.language.isoengpt_BR
dc.publisher.countryEstados unidospt_BR
dc.publisher.departmentInstituto de Informática - INF (RG)pt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectParallel algorithmspt_BR
dc.subjectMulticorept_BR
dc.subjectGPUpt_BR
dc.subjectMaximum subsequence sum problempt_BR
dc.titleEfficient BSP/CGM algorithms for the maximum subsequence sum and related problemspt_BR
dc.typeArtigopt_BR

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Artigo - Anderson Corrêa de Lima - 2015.pdf
Tamanho:
358.15 KB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

INF - Artigos publicados em periódicos