Computational Biology Lecture 19: Chaining local alignments

Having found the maximal matches between x and y, we can put some of them together to form a chain. These maximal matches can be considered as high scoring local alignments. The chain then represents a global alignment (not necessarily optimal). Therefore, this is one way of obtaining a sub-optimal global alignmnent based on high scoring chucks (local alignments). If the chaining of the local alignments can be done efficiently, for instance in better than O(n2) time, then we have a faster global alignment algorithm that produces a sub-optimal alignment, but a one that is good enough because it contains many high scoring local alignments. How can we chain those local alignments? These local alignments (obtained as matches) have different lengths, and each has the form (xa...xb, yc...yd). Therefore, each local alignment can be represented as a square in two dimensions as the figure below shows. a b