Search

Given two strings A and B of lengths na and nb, respectively, the All-substrings Longest Common Subsequence (ALCS) problem obtains, for any substring B' of B, the length of the longest string that is a subsequence of both A and B'. The sequential algorithm for this problem takes O(na nb) time and O(nb) space. We present a parallel algorithm for the ALCS problem on the Coarse-Grained Multicomputer (BSP/CGM) model with p < √na processors, that takes O(na nb/p) time, O(log p) communication rounds and O(nb √na) space per processor. The proposed algorithm also solves the basic Longest Common Subsequence (LCS) problem that finds the longest string (and not only its length) that is a subsequence of both A and B. To our knowledge, this is the best BSP/CGM algorithm in the literature for the LCS and ALCS problems.

Given a sequence A of real numbers, we wish to find a list of all nonoverlapping contiguous subsequences of A that are maximal. A maximal subsequence M of A has the property that no proper subsequence of M has a greater sum of values. Furthermore, M may not be contained properly within any subsequence of A with this property. This problem has several applications in Computational Biology and can be solved sequentially in linear time. We present a BSP/CGM algorithm that solves this problem using p processors in O(|A|=p) time and O(|A|=p) space per processor. The algorithm uses a constant number of communication rounds of size at most O(|A|=p). Thus, the algorithm achieves linear speedup and is highly scalable. To our knowledge, there are no previous known parallel BSP/CGM algorithms to solve this problem.

In this book chapter, the authors discuss some important communication issues to obtain a highly scalable computing system. They consider the CGM (Coarse-Grained Multicomputer) model, a realistic computing model to obtain scalable parallel algorithms. The communication cost is modeled by the number of communication rounds and the objective is to design algorithms that require the minimum number of communication rounds. They discuss some important issues and make considerations of practical importance, based on our previous experience in the design and implementation of parallel algorithms. The first issue is the amount of data transmitted in a communication round. For a practical implementation to be successful they should attempt to minimize this amount, even when it is already within the limit allowed by the CGM model. The second issue concerns the trade-off between the number of communication rounds which the CGM attempts to minimize and the overall communication time taken in the communication rounds. Sometimes a larger number of communication rounds may actually reduce the total amount of data transmitted in the communications rounds. These two issues have guided us to present efficient parallel algorithms for the string similarity problem, used as an illustration.

Alignments of sequences are widely used for biological sequence comparisons. Only biological events like mutations, insertions and deletions are usually modeled and other biological events like inversions are not automatically detected by the usual alignment algorithms. Alignment with inversions does not have a known polynomial algorithm and a simplification to the problem that considers only non-overlapping inversions were proposed by Schoniger and Waterman [20] in 1992 as well as a corresponding O(n6) solution. An improvement to an algorithm with O(n3 logn)-time complexity was announced in an extended abstract [1] and, in this present paper, we give an algorithm that solves this simplified problem in O(n3)-time and O(n2)-space in the more general framework of an edit graph. Inversions have recently [4,7,13,17] been discovered to be very important in Comparative Genomics and Scherer et al. in 2005 [11] experimentally verified inversions that were found to be polymorphic in the human genome. Moreover, 10% of the 1,576 putative inversions reported overlap RefSeq genes in the human genome. We believe our new algorithms may open the possibility to more detailed studies of inversions on DNA sequences using exact optimization algorithms and we hope this may be particularly interesting if applied to regions around known rearrangements boundaries. Scherer report 29 such cases and prioritize them as candidates for biological and evolutionary studies.

Given a sequence A of real numbers, we wish to find a list of all non-overlapping contiguous subsequences of A that are maximal. A maximal subsequence M of A has the property that no proper subsequence of M has a greater sum of values. Furthermore, M may not be contained properly within any subsequence of A with this property. This problem can be solved sequentially in linear time. We present a BSP/CGM algorithm that uses p processors and takes O (|A|/p) time and O (|A|/p) space per processor. The algorithm uses a constant number of communication rounds of size at most O (|A|/p). Thus the algorithm achieves linear speed-up and is highly scalable.

Comparison of the DNA sequences and genes of two genomes can be useful to investigate the common functionalities of the corresponding organisms and get a better understanding of how the genes or groups of genes are organized and involved in several functions. We use high-performance parallel computing to compare the whole genomes of two organisms, namely Xanthomonas axonopodis pv. citri and Xanthomonas campestris pv. campestris, each with more than five million base pairs. Our purpose is two-fold. First we intend to exploit the high-performance power of a cluster of low-cost microcomputers, propose a parallel solution to this problem, and show its feasibility with implementation and performance results. Second we do additional comparisons of the two genomes by locating and compare not only the homologous genes (expressed in terms of the 20-letter amino acids) but also compare the regions or gaps (in terms of the 4-letter DNA nucleotides) between the corresponding homologous genes. We have implemented the proposed comparison strategy to compare the two genomes Xanthomonas axonopodis pv. citri (Xac) and Xanthomonas campestris pv. campestris (Xcc). The parallel platform used is a Beowulf cluster of 64 nodes consisting of low cost microcomputers. Xac has 5175554 base pairs and 4313 protein-coding genes while Xcc has 5076187 base pairs and 4182 protein-coding genes. The parallel solution is based on the dynamic programming approach and presents not only less processing time, but also better quality results as compared to approaches based on Blast and EGG.

Given two strings X and Y of lengths m and n, respectively, the all-substrings longest common subsequence (ALCS) problem obtains the lengths of the subsequences common to X and any substring of Y. The sequential algorithm takes O(mn) time and O(n) space. We present a parallel algorithm for ALCS on a coarse-grained multicomputer (BSP/CGM) model with p < /spl radic/m processors that takes O(mn/p) time and O(n/spl radic/m) space per processor, with O(log p) communication rounds. The proposed parallel algorithm also solves the well-known LCS problem. To our knowledge this is the best BSP/CGM algorithm for the ALCS problem in the literature.

The maximum subsequence problem finds the contiguous subsequence of n real numbers with the highest sum. This problem appears in the analysis of DNA or protein sequences. It can be solved sequentially in O(n) time. In the 2-D version, given an n × n array A, the maximum subarray of A is the contiguous subarray that has the maximum sum. The sequential algorithm for the maximum subarray problem takes O(n 3) time. We present efficient BSP/CGM parallel algorithms that require a constant number of communication rounds for both problems. In the first algorithm, the sequence stored on each processor is reduced to only five numbers, so that the resulting values can be concentrated on a single processor which runs an adaptation of the sequential algorithm to obtain the result. The parallel algorithm requires O(n/p) computing time. In the second algorithm, the input array is partitioned equally among the processors and we first reduce each subarray to a sequence, and then apply the first algorithm to solve it. The parallel algorithm takes O(n 3/p) computing time. The good performance of the parallel algorithms is confirmed by experimental results run on a 64-node Beowulf parallel computer.

In this paper we present a parallel wavefront algorithm for computing an alignment between two strings A and C, with |A| = m and |C| = n. On a distributed memory parallel computer of p processors each with O((m + n)/p) memory, the proposed algorithm requires O(p) communication rounds and O(mn/p) local computing time. The novelty of this algorithm is based on a compromise between the workload of each processor and the number of communication rounds required, expressed by a parameter called α. The proposed algorithm is expressed in terms of this parameter that can be tuned to obtain the best overall parallel time in a given implementation. We show very promising experimental results obtained on a 64-node Beowulf machine. A characteristic of the wavefront communication requirement is that each processor communicates with few other processors. This makes it very suitable as a potential application for grid computing.

Based on a CGM/BSP parallel algorithm for computing the transitive closure of an acyclic directed graph (digraph), we present a modified version that works for any digraph and show very promising implementation results. The original CGM/BSP algorithm for acyclic digraphs uses a linear extension labeling of the vertices. With this labeling, the original algorithm can be shown to require log p + 1 communication rounds, where p is the number of processors. The modified CGM/BSP algorithm works for any digraph and does not use the linear extension labeling. In theory the modified version no longer guarantees the O(log p) bound on the number of communication rounds, as shown by an artificially elaborated example that requires more than log p + 1 communication rounds. In practice, however, all the graphs tested use at most log p + 1 communication rounds. The implementation results are very promising and show the efficiency and scalability of the proposed modified algorithm, and compare favorably with other parallel implementations.

Problemas de alinhamento de cadeias são fundamentais em aplicações diversas, das quais se destacam as relacionadas à Biologia Molecular. O alinhamento de duas cadeias A e B indica quão semelhantes elas são ou quais operações são necessárias para transformar uma em outra. Uma variação do problema de alinhamento de cadeias envolve comparar a cadeia A com todas as subcadeias de B. Para este problema, são conhecidos algoritmos seuqenciais que o resolvem em tempo O(|A||B|log(|A|+|B|)), um dos quais é apresentado nesta tese. É também apresentado um algoritmo seqüencial de tempo O(|A||B|) para um caso especial de alinhamento de todas as subcadeias, que envolve a busca pela maior subseqüência comum a duas cadeias. Propomos novos algoritmos paralelos para estes problemas, utilizando um modelo próprio para máquinas de memória distribuída, o CGM (Coarse Grained Multicomputers). Um dos objetivos fundamentais no desenvolvimento de algoritmos CGM é a redução do número de rodadas de comunicação, se possível tornando-o dependente apenas do número de processadores (p). Os algoritmos aqui propostos apresentam aceleração (speed-up) linear e apenas O(log p) etapas de comunicação. Não há algoritmos do nosso conhecimento com tais características na literatura not available

In this paper we present a coarse-grained parallel algorithm for solving the string edit distance problem for a string A and all substrings of a string C. Our method is based on a novel CGM/BSP parallel dynamic programming technique for computing all highest scoring paths in a weighted grid graph. The algorithm requires \log p rounds/supersteps and O(\fracn^2p\log m) local computation, where $p$ is the number of processors, p^2 \leq m \leq n. To our knowledge, this is the first efficient CGM/BSP algorithm for the alignment of all substrings of C with A. Furthermore, the CGM/BSP parallel dynamic programming technique presented is of interest in its own right and we expect it to lead to other parallel dynamic programming methods for the CGM/BSP.

O uso de um sistema de memória compartilhada permite grande iteração entre os processadores de uma máquina MIMD e oferece um paradigma de programação bastante simples. No entanto, a implementação de sistemas de memória compartilhada eficientes apresenta diversos desafios, devido à alta largura de faixa e à baixa latência média requeridos. Uma solução economicamente viável é associar uma cache a cada processador, armazenando cópias dos dados mais usados nestas caches. Diversas técnicas têm sido estudadas e implementadas para que não ocorram problemas de coerência entre cópias de um mesmo dado guardadas em caches distintas. Uma técnica pouco explorada é a utilização de caches write-through com verificação de consistência para todas as escritas geradas pelos processadores. A impopularidade desta técnica se deve à alta largura de faixa requerida para a memória principal. Este trabalho mostra que, em algumas circunstâncias, o uso de caches write-through pode apresentar vantagens sobre o uso de caches copy back com protocolos de posse de blocos, apresentando desempenhos menos dependentes da codificação dos programas.