We investigate how clusters and grid computing can be combined with a service-oriented architecture. An important application is the parallelization of dataintensive algorithms as they are common in life sciences, such as the sequence alignment problem. We developed a prototype of a service-oriented parallel Basic Local Alignment Search Tool (BLAST) [1]. Using a standard grid middleware, the Globus Toolkit [19], we have distributed data and logic over several cluster nodes, all of which have access to a shared database. This allows us to parallelize BLAST by combining both functional and domain decomposition. In an experimental performance evaluation, we investigate the scalability and performance of the developed BLAST service. Our results show that dataintensive algorithms can be effectively parallelized using a service-oriented approach, offering linear scalability. At the same time, our approach facilitates the sharing of functionality through a programmatic interface and further offers plug-and-play extensibility.