Computational Biology Lecture 4: Overlap detection, Local Alignment, Space Efficient Needleman-Wunsch

An overlap of two sequences is considered an alignment where start and end gaps are ignored. This is also called semi-global alignment because we are globally aligning the two sequences but ignoring trailing gaps at both extremities. First we need to make clear what we mean by start and end gaps. Start gaps are gaps that occur before the first character in a sequence. Similarly, end gaps are gaps that occur after the last character of a sequence. Therefore, if the two sequences are x and y, start and end gaps can be either in x or in y. If the optimal overlap (or semi-global alignment) of x and y is to be computed, the basic Needleman-Wunsch algorithm will not work. Consider the following example of aligning x = CAGCACTTGGATTCTCGG and y = CAGCGTGG