Learn Before
  • Alignment

  • Minimum edit distance algorithm

Compute the alignment path

To better use the edit distance algorithm to generate an alignment, we can visualize the alignment as a path through a table, here referred to as the edit distance matrix. The tabular approach of creating a matrix is very helpful to deal with long strings. To compute the alignment path, first, we apply the minimum edit distance algorithm to each cell and store backpointers. Second, we perform a backtrace that starts from the last cell (at the final row and column) and follows the backpointers back to the first cell through the matrix. There might be multiple paths. Each complete path between the final cell and the first cell is a minimum distance alignment.

Image 0

0

1

5 years ago

Tags

Data Science

Related
  • Compute the alignment path

  • Levenshtein distance

  • Compute the alignment path

Learn After
  • Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology