A fundamental task in the area of computational biology is the search for relevant information within the large amount of available data. Among others, it is important to run tools such as BLAST - Basic Local Alignment Search Tool - effciently, which enables the comparison of biological sequences and discovery of homologies and other related information. However, the execution cost of BLAST is highly dependent on the database size, which has considerably increased. The evaluation of BLAST in distributed and parallel environments like PC clusters has been largely investigated in order to obtain better performances. This work reports a replicated allocation of the (sequences) database where each copy is also physically fragmented, with some fragments assigned as primary. This way we show that it is possible to execute BLAST with some nice characteristics of both replicated and fragmented conventional strategies, like flexibility and I/O parallelism. We propose two dynamic workload balancing strategies associated with this data allocation. We have adopted a non- intrusive approach, i.e., the BLAST code remains unchanged. These methods are implemented and practical results show that we achieve not only a balanced workload but also very good performances.