Bioinformatics AlgorithmsAn Active Learning Approach
You are reading the free online edition. Autograded code challenges and a certificate are in the interactive text, free to start.Solve these problems with autograders, free

Lesson 5.11

The Changing Faces of Sequence Alignment

4 min read3 code challenges✓ Read

In this lesson, we will describe three sequence comparison problems and let you apply what you have already learned to solve them. Hint: the idea is to frame each problem as an instance of the Longest Path in a DAG Problem.

Problem 1: Edit Distance

In 1966, Vladimir Levenshtein introduced the notion of the edit distance between two strings as the minimum number of edit operations needed to transform one string into another. Here, an edit operation is the insertion, deletion, or substitution of a single symbol. For example, TGCATACT can be transformed into ATCCGAT with six edit operations, implying that the edit distance between these strings is at most 6.

Edit distance 1

STOP and Think Can you transform TGCATACT into ATCCGAT using a smaller number of operations?

In fact, the edit distance between TGCATACT and ATCCGAT is 5:

Edit distance 2

Levenshtein introduced edit distance but did not describe an algorithm for computing it, which we leave to you.

Edit Distance Problem: Find the edit distance between two strings.

  • Input: Two strings.
  • Output: The edit distance between these strings.

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

Problem 2: Fitting Alignment

Say that we wish to compare the approximately 20,000 amino acid-long NRP synthetase from Bacillus brevis with the approximately 600 amino acid-long A-domain from Streptomyces roseosporus, the bacterium that produces the powerful antibiotic Daptomycin. We hope to find a region within the longer protein sequence v that has high similarity with all of the shorter sequence w. Global alignment will not work because it tries to align all of v to all of w; local alignment will not work because it tries to align substrings of both v and w. Thus, we have a distinct alignment application called the Fitting Alignment Problem.

“Fitting” w to v requires finding a substring v′ of v that maximizes the global alignment score between v′ and w among all substrings of v. For example, the best global, local, and fitting alignments of v = CGTAGGCTTAAGGTTA and w = ATAGATA are shown in the figure below (with mismatch and indel penalties equal to 1).

Fitting Alignment Problem: Construct a highest-scoring fitting alignment between two strings.

  • Input: Strings v and w as well as a matrix Score.
  • Output: A highest-scoring fitting alignment of v and w as defined by the scoring matrix Score.

Note in the figure that the optimal local alignment (with score 3) is not a valid fitting alignment. On the other hand, the score of the optimal global alignment (6 - 9 - 1 = -4) is smaller than that of the best fitting alignment (5 - 2 - 2 = +1).

Global local fitting

Figure: Global, local, and fitting alignments. Black symbols do not contribute to the local and fitting alignments and are only shown to illustrate flanking regions.

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

  • Input: Two nucleotide strings v and w, where v has length at most 1000 and w has length at most 100.
  • Output: A highest-scoring fitting alignment between v and w.

Problem 3: Overlap Alignment

In the chapter on genome assembly, we discussed how to use overlapping reads to assemble a genome, a problem that was complicated by errors in reads. Aligning the ends of the hypothetical reads shown below offers a way to find overlaps between error-prone reads.

ATGCATGCCGG
         T-CC-GAAAC

An overlap alignment of strings v = v1 ... vn and w = w1 ... wm is a global alignment of a suffix of v with a prefix of w. An optimal overlap alignment of strings v and w maximizes the global alignment score between an i-suffix of v and a j-prefix of w (i.e., between vi ... vn and w1 ... wj) among all i and j.

Overlap Alignment Problem: Construct a highest-scoring overlap alignment between two strings.
  • Input: Two strings and a matrix score.
  • Output: A highest-scoring overlap alignment between the two strings as defined by the scoring matrix score.

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

  • Input: Two strings v and w, each of length at most 1000.
  • Output: The score of an optimal overlap alignment of v and w, followed by an alignment of a suffix v' of v and a prefix w' of w achieving this maximum score.