Bioinformatics Algorithms/

...

/

From Global to Local Alignment

From Global to Local Alignment

Let’s observe global alignment, local alignment, their problems, and some limitations of global alignment.

We'll cover the following...

Global alignment

You should now be ready to modify the alignment graph to solve a generalized form of the alignment problem that takes a scoring matrix as input.

Global Alignment Problem

Problem overview:
Find the highest-scoring alignment of two strings as defined by a scoring matrix.

Input: Two strings and a scoring matrix Score.
Output: An alignment of the strings whose alignment score (as defined by Score) is maximized among all possible alignments of the strings.

To solve the Global Alignment Problem, we still must find a longest path in the alignment graph after updating the edge weights to reflect the values in the scoring matrix (see figure below). Recalling that deletions correspond to vertical edges (↓), insertions correspond to horizontal edges (→), and matches/mismatches correspond to diagonal edges (↘/↘), we obtain the following recurrence for si,j_{i, j}, the length of a longest path from (0, 0) to (i, j):

si,j=max{si−1,j+Score(vi,−)si,j−1+Score(−,wj)si−1,j−1+Score(vi,wj).s_{i,j} = max \left\{\begin{matrix}s_{i-1,j} & + & Score(v_{i},-)\\ s_{i,j-1} & + & Score(-, w_{j})\\ s_{i-1,j-1} & + & Score(v_{i},w_{j}).\end{matrix}\right. ...