Grid middleware infrastructure is a distributed environment suitable for many, typically large-scale, applications. An improved genome sequence alignment algorithm is presented that significantly reduces sequence matching computation time. Yet, very long sequences can still present computation challenges. A small-scale application is implemented on a shared memory system, on a cluster, and the grid-enabled cluster. Experimental results show comparable performance of the grid-enabled version, with scalability for large sequences. The grid offers application management, enables dynamic specification of parameters, and enables a choice of distributed computation nodes.