# Read alignment: approximate matching

Often, reads do not exactly match the reference genome, owing to natural genomic variations or errors introduced during sequencing. In such instances, approximate matching algorithms facilitate identifying similarities between the query and reference sequences, enabling the alignment of reads. This approach is especially useful when working with organisms that are closely related, as their genomes may have evolved somewhat differently over time.

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

### Approximate matching, Hamming and edit distance

{% embed url="<https://www.youtube.com/watch?v=MCvHeW13DsE&list=PL2mpR0RYFQsBiCWVJSvVAO3OJ2t7DzoHA&index=30>" %}

### Pigeonhole principle

{% embed url="<https://www.youtube.com/watch?v=duatMINEGgE&list=PL2mpR0RYFQsBiCWVJSvVAO3OJ2t7DzoHA&index=31>" %}

### Practical: Implementing the pigeonhole principle

{% embed url="<https://www.youtube.com/watch?v=9M8aNFgwNG0&list=PL2mpR0RYFQsBiCWVJSvVAO3OJ2t7DzoHA&index=32>" %}

### Solving the edit distance problem

{% embed url="<https://www.youtube.com/watch?v=8Q2IEIY2pDU&list=PL2mpR0RYFQsBiCWVJSvVAO3OJ2t7DzoHA&index=33>" %}

### Using dynamic programming for edit distance

{% embed url="<https://www.youtube.com/watch?v=0KzWq118UNI&list=PL2mpR0RYFQsBiCWVJSvVAO3OJ2t7DzoHA&index=34>" %}

### Practical: Implementing dynamic programming for edit distance

{% embed url="<https://www.youtube.com/watch?v=Xg6uyW9Bscs&list=PL2mpR0RYFQsBiCWVJSvVAO3OJ2t7DzoHA&index=35>" %}

### Edit distance for approximate matching

{% embed url="<https://www.youtube.com/watch?v=NjfNZzJiu8o&list=PL2mpR0RYFQsBiCWVJSvVAO3OJ2t7DzoHA&index=36>" %}

## Problems to solve

Try to solve these problems after completing the section.

1. [Counting Point Mutations](https://rosalind.info/problems/hamm/)
2. [Finding a Shared Motif](https://rosalind.info/problems/lcsm/)
3. [Enumerating Gene Orders](https://rosalind.info/problems/perm/)
4. [Enumerating k-mers Lexicographically](https://rosalind.info/problems/lexf/)

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

1. [Longest Increasing Subsequence](https://rosalind.info/problems/lgis/)
2. [k-Mer Composition](https://rosalind.info/problems/kmer/)
3. [Finding a Shared Spliced Motif](https://rosalind.info/problems/lcsq/)
4. [Edit Distance](https://rosalind.info/problems/edit/)
5. [Edit Distance Alignment](https://rosalind.info/problems/edta/)
6. [Counting Optimal Alignments](https://rosalind.info/problems/ctea/)

## 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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://edu.abi.am/bioinformatics-algorithms/read-alignment-approximate-matching.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.