3
$\begingroup$

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

$\endgroup$

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.