ConceptTheory & Algos
Edit distance
The minimum number of edits including insertions, deletions, or substitutions needed to make a read exactly match a reference segment.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
4Each in their own terms, from the easiest level.
Erik Demaine
A metric for measuring the difference between two sequences by counting the minimum number of operations (insertions, deletions, substitutions) required to transform one into the other.Ryan O'Donnell
A measure of similarity between two strings, whose reduction from k-SAT helps prove lower bounds for running times.Can Firtina
The minimum number of edits needed to make a read exactly match the reference segment.
Lectures that assume it
3Connections
16The lectures that define it or assume it, and the concepts next to it.
Concepts9
Show 3 moreShow fewer
Lectures7
- Exponential Time Hypotheses: ETH and SETH
- Dynamic Programming III: Parenthesization, Edit Distance, Knapsack
- Arch4Health: 4th Workshop on Architecture for Health
- Fundamentals of Sequence Search and Alignment
- Efficient Fine-Grained Algorithms
- GateKeeper: FPGA-Accelerated Pre-Alignment Filtering