# Sequence Alignment with general gap penalties: proof of optimal substructure

I am very well-aware of how optimal substructure for pairwise global sequence alignment using the Needleman-Wunsch algorithm works.

However, I have merely seen hand-waving explanations for the optimal substructure property for sequence alignment using a general/arbitrary gap penalty function (I realize that concave penalties are normally used but the the substructure will be the same for concave and arbitrary case)...

Can anyone provide a formal proof of what the optimal substructure is for the general (or concave) gap penalties?

Thanks