Portal de Periódicos da CAPES

Capítulo de livro Produção Nacional Revisado por pares

BIBTEX RIS

A Parallel Wavefront Algorithm for Efficient Biological Sequence Comparison

2003; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-44843-8_27

1611-3349

C. E. R. Alves, Edson N. Cáceres, F. Dehne, S. W. Song,

DNA and Biological Computing

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.