If you can implement the Needeman-Wunsch dynamic algorithm you could get the gaps but not to reinvent the wheel, there is a CPAN module Algorithm::NeedlemanWunsch for that.

As for the substitutions, I am not clear on how strict your criteria are and the type of sequences you have but maybe FindMod at ExPasy can be a choice...

BLASTing would conduct local similarity searches which are not the OP's goal..