Lesson 5.10

From Global to Local Alignment

7 min read2 code challenges✓ Read

Watch the lectureFrom Global to Local Alignment

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: Find a 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 over all 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. 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 s_{i, j}, the length of a longest path from (0, 0) to (i, j):

When the match reward is +1, the mismatch penalty is μ, and the indel penalty is σ, the alignment recurrence can be written as follows:

See the figure below for an example alignment graph.

Figure: AlignmentGraph(TGTTA, TCGT), with each edge colored according to whether the edge represents a match, mismatch, insertion, or deletion.

Code Challenge Solve the Global Alignment Problem. Solve at Cogniterra or Rosalind.Solve it with the autograderFree to start in the interactive text

• Input: Two protein strings written in the single-letter amino acid alphabet.
• Output: The maximum alignment score of these strings followed by an alignment achieving this maximum score. Use the BLOSUM62 scoring matrix for matches and mismatches as well as the indel penalty σ = 5.

Limitations of global alignment

Analysis of homeobox genes offers an example of a problem for which global alignment may fail to reveal biologically relevant similarities. These genes regulate embryonic development and are present in a large variety of species, from flies to humans. Homeobox genes are long, and they differ greatly between species, but an approximately 60 amino acid-long region in each gene, called the homeodomain, is highly conserved. For instance, consider the mouse and human homeodomains below.

The immediate question is how to find this conserved segment within the much longer genes and ignore the flanking areas, which exhibit little similarity. Global alignment seeks similarities between two strings across their entire length; however, when searching for homeodomains, we are looking for smaller, local regions of similarity and do not need to align the entire strings. For example, the global alignment between the two sequences below has 22 matches, 18 indels, and 2 mismatches, resulting in the score 22 − 18 - 2 = 2 (if σ = μ = 1).

However, these sequences can be aligned differently (with 17 matches and 32 indels) based on a highly conserved interval represented by the substrings CAGTCTATGTCAG and CAGTTATGTTCAG:

This alignment has fewer matches and a lower score of 17 − 32 = −15, even though the conserved region of the alignment contributes a score of 12 - 2 = 10, which is hardly an accident.

The figure below shows the two alignment paths corresponding to these two different alignments. The upper path, corresponding to the second alignment above, loses out because it contains many heavily penalized indels on either side of the diagonal corresponding to the conserved interval. As a result, global alignment outputs the biologically irrelevant lower path. How can we rule out biologically irrelevant alignments when local similarities are present?

Figure: Global and local alignments of two DNA strings that share a highly conserved interval. The relevant alignment that captures this interval (upper path) loses to an irrelevant alignment (lower path), since the former incurs heavy indel penalties.

When biologically significant similarities are present in some parts of sequences v and w and absent from others, biologists attempt to ignore global alignment and instead align substrings of v and w, which yields a local alignment of the two strings. The problem of finding substrings that maximize the global alignment score over all substrings of v and w is called the Local Alignment Problem.

Local Alignment Problem: Find the highest-scoring local alignment between two strings.

• Input: Strings v and w as well as a matrix score.
• Output: Substrings of v and w whose global alignment score (as defined by score) is maximized among all substrings of v and w.

The straightforward but inefficient way to solve the Local Alignment Problem is to find the longest path connecting every pair of nodes in the alignment graph (rather than just those connecting the source and sink, as in the Global Alignment Problem), and then to select the path having maximum weight over all these longest paths.

STOP and Think What is the runtime of this approach?

Free taxi rides in the alignment graph

For a faster approach, imagine a “free taxi ride” from the source (0, 0) to the node representing the start node of the conserved (red) interval in the figure below. Imagine also a free taxi ride from the end node of the conserved interval to the sink. If such rides were available, then you could reach the starting node of the conserved interval for free, instead of incurring heavy penalties as in global alignment. Then, you could travel along the conserved interval to its end node, accumulating many positive match scores while encountering few mismatch and deletion penalties. Finally, you could take another free ride from the end node of the conserved interval to the sink. The resulting score of this ride is equal to the alignment score of only the conserved intervals, as desired.

The only problem with the "free rides" idea is that we don’t know in advance where the local alignment (i.e., the conserved red interval in the figure below) starts and ends! Yet we can provide free rides from the source to all nodes and from all nodes to the sink.

Figure: Modifying the preceding figure by adding “free taxi ride” edges (having weight 0) connecting the source to the start node of the conserved interval and connecting the end node of the conserved interval to the sink. These new edges allow us to score only the local alignment containing the conserved interval.

Connecting the source (0, 0) to every other node by adding a zero-weight edge and connecting every node to the sink (n, m) by a zero-weight edge will result in a DAG perfectly suited for solving the Local Alignment Problem, shown below. Because of the free taxi rides, we no longer need to construct a longest path between every pair of nodes in the graph — the longest path from source to sink yields an optimal local alignment!

Figure: The local alignment algorithm introduces zero-weight edges (shown by blue dashed lines) connecting the source (0, 0) to every other node in the alignment graph, as well as zero-weight edges (shown by red dashed lines) connecting every node to the sink node.

The total number of edges in the above graph is O(|v| · |w|), which is still small. Since the runtime of finding a longest path in a DAG is defined by the number of edges in the graph, the resulting local alignment algorithm will be fast. As for computing the values s_{i, j} , adding zero-weight edges from (0, 0) to every node has made the source node (0, 0) a predecessor of every node (i, j). Therefore, there are now four edges entering (i, j), which adds only one new term to the longest path recurrence relation:

The recurrence above incorporates free rides from source = (0, 0), but it does not incorporate free rides into sink = (n, m). Since sink has every other node as a predecessor, s_{n, m} will be equal to the largest value of s_{i, j} over the entire alignment graph,

s_{n, m} = max_{0 ≤ i ≤ n, 0 ≤ j ≤ n}s_{i, j}

STOP and Think After computing all values s_{i, j} , how can you find where the path corresponding to the best local alignment starts and ends in the alignment graph?

You might still be wondering how we can take these free taxi rides through the alignment graph. The point is that you are in charge of designing whatever Manhattan-like DAG you like, as long as it adequately models the specific alignment problem at hand. Transformations like free taxi rides will become a common theme in this chapter. Various alignment problems can be solved by constructing an appropriate DAG with as few edges as possible (to minimize runtime), assigning edge weights to model the requirements of the problem, and then finding a longest path in this DAG.

Code Challenge Solve the Local Alignment Problem. Solve at Cogniterra or Rosalind.Solve it with the autograderFree to start in the interactive text

• Input: Two protein strings written in the single-letter amino acid alphabet.
• Output: The maximum score of a local alignment of the strings, followed by a local alignment of these strings achieving the maximum score. Use the PAM250 scoring matrix for matches and mismatches as well as the indel penalty σ = 5.