Several applications in computational biology have large runtime and memory requirements either because of large data sizes or the inherent time and memory complexity of the underlying algorithms. Parallel computing is an effective way to address both these concerns — run-time can be reduced by the use of multiple processors to solve the same problem and the scaling of memory with processors enables the solution of larger problems than otherwise possible. In this paper, we describe efficient parallel solutions for three important applications in computational biology: 1) Computing alignments of large stretches of genomes, 2) clustering Expressed Sequence Tags and 3) Computing the accessible surface area of protein molecules. We report experimental results on a 64-processor IBM xSeries parallel computer. We conclude the paper by arguing that parallel computational biology is an important subdiscipline that merits significant research attention.