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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.