Read alignment: approximate matching

Very frequently, the reads may not match the reference genome exactly. The reasons for this may be natural genomic variation or sequencing errors. In these cases, an approximate matching algorithm can still find matches between the query and reference sequences, allowing the read alignment process to proceed. Approximate matching can also be useful when aligning reads from closely related organisms, as their genomes may have undergone some degree of evolution.

In this section you will learn how approximate matching algorithms work.

Approximate matching, Hamming and edit distance

Pigeonhole principle

Practical: Implementing the pigeonhole principle

Solving the edit distance problem

Using dynamic programming for edit distance

Practical: Implementing dynamic programming for edit distance

Edit distance for approximate matching

Problems to solve

Try to solve these problems after completing the section.

1. Counting Point Mutations

2. Finding a Shared Motif

3. Enumerating Gene Orders

4. Enumerating k-mers Lexicographically

If these were too easy for you, try unlocking the following set of Advanced problems

1. Longest Increasing Subsequence

2. k-Mer Composition

3. Finding a Shared Spliced Motif

4. Edit Distance

5. Edit Distance Alignment

6. Counting Optimal Alignments

Congratulations!

If you made it here, then congratulations! You have successfully completed this section. Move to the next portion of the guide with the arrow buttons below.