I am trying to figure out ways to find suboptimal alignments for sequences.

I know that Needleman - Wunsch gives the optimal alignment.

I also know that Waterman-Eggerton algorithm is a modification of the Smith-Waterman algorithm which gives suboptimal sequence alignments.

However, how do you find suboptimal global alignments? Is the only option to modify the traceback step in the Needleman Wunsch algorithm? (i.e finding all possible paths from right bottom corner to left top corner). Is there any way to award probability for these suboptimal alignments? One way that comes to my mind is to use the normalised score of the alignments.

Is there a formal name for such algorithm?