algorithm - Find optimal local alignment of two strings using local & global alignments

Question

I have a homework question that I trying to solve for many hours without success, maybe someone can guide me to the right way of thinking about it.

The problem:

We want to find an optimal local alignment of two strings S1 and S2, we know that there exists such an alignment with the two aligned substrings of S1 and S2 both of length at most q. Besides, we know that the number of the table cells with the maximal value, opt, is at most r. Describe an algorithm solving the problem in time O(mn+r*q^2) using working space of at most O(n+r+q^2).

Restrictions: run the algorithm of finding the optimal local alignment value, with additions to your choice (like the list of index pairs), only once. Besides, you can run any variant of the algorithm for solving the global optimal alignment problem as many times as you wish

I know the solution to this problem with running the local alignment many times and the global alignment only once, but not the opposite.

the global alignment algorithm:

the local alignment algorithm:

Any help would be appreciated.

question from:https://stackoverflow.com/questions/65645804/find-optimal-local-alignment-of-two-strings-using-local-global-alignments

Answer 1

Waitting for answers