Log In
Join
for free
Log In
Join
for free
Back To Course Home
Bioinformatics Algorithms
0% completed
Before Getting Started
Introduction to the Course
Where in the Genome Does DNA Replication Begin?
A Journey of a Thousand Miles
The Finding Origin of Replication Problem
DnaA Boxes
The Hidden Message Problem
Counting Words
Coding Challenge: Implement Pattern Count
The Frequent Words Problem
Some Hidden Messages are More Surprising than Others
Coding Challenge: Implement Pattern Matching
An Explosion of Hidden Messages
The Simplest Way to Replicate DNA
Asymmetry of Replication
Peculiar Statistics of the Forward and Reverse Half-Strands
Deamination
The Skew Diagram
Coding Challenge: Implement Minimum Skew
Some Hidden Messages are More Elusive than Others
A Final Attempt at Finding DnaA Boxes in E. coli
Epilogue: Complications in ori Predictions
Quiz
DNA Replication: Open Problems, Charging Stations, and Detours
Open Problem: Multiple Replication Origins in a Bacterial Genome
Open Problem: Finding Replication Origins in Archaea
Open Problem: Finding Replication Origins in Yeast
Open Problem: Computing Probabilities of Patterns in a String
Charging Station: The Frequency Array
Charging Station: Conversions between Patterns and Numbers
Charging Station: Finding Frequent Words by Sorting
Charging Station: Solving the Clump Finding Problem
Charging Station: Solving Frequent Words with Mismatches Problem
Charging Station: Generating the Neighborhood of a String
Charging Station: Find Frequent Words with Mismatching by Sorting
Detour : Big-O Notation
Detour: Probabilities of Patterns in a String
Detour: The Most Beautiful Experiment in Biology
Detour: Directionality of DNA Strands
Detour: The Towers of Hanoi
Detour: The Overlapping Words Paradox
How Do We Assemble Genomes?
Exploding Newspapers
The String Reconstruction Problem
String Reconstruction With Overlap Graph: From String To Graph
String Reconstruction With Overlap Graph: The Genome Vanishes
String Reconstruction with Overlap Graph: Graph Representation
String Reconstruction with Overlap Graph: Hamiltonian Paths
String Reconstruction with Gluing Nodes and De Bruijn Graphs
Walking in the de Bruijn Graph
De Bruijn Graphs: Another Way of Construction
De Bruijn Graphs: Construction from K-mer Composition
De Bruijn graphs: Comparison with Overlap Graphs
The Seven Bridges of Königsberg
Euler’s Theorem
Constructing Eulerian Cycles and Paths from Euler’s Theorem
Constructing Universal Strings
Assembling Genomes: From Reads to Read-Pairs
Assembling genomes: Transforming Read-Pairs to Long Virtual Reads
Assembling genomes: From Composition to Paired Composition
Assembling genomes: Paired De Bruijn Graphs
Epilogue: Genome Assembly Faces Real Sequencing Data
Quiz
Assemble Genomes: Charging Stations, and Detours
Charging Station: The Effect Of Gluing On the Adjacency Matrix
Charging Station: Generating All Eulerian Cycles
Charging Station: Reconstructing String in Paired De Bruijn Graph
Charging Station: Maximal Non-Branching Paths in a Graph
Detour: A Short History of DNA Sequencing Technologies
Detour: Repeats in the Human Genome
Detour: Graphs
Detour: The Icosian Game
Detour: Tractable and Intractable Problems
Detour: From Euler to Hamilton to de Bruijn
Detour: Pitfalls of Assembling Double-Stranded DNA
Detour: The BEST Theorem
How Do We Compare Biological Sequences?
The Discovery of Antibiotics
How Do Bacteria Make Antibiotics?
Where is Tyrocidine Encoded in the Bacillus Brevis Genome?
Dodging the Central Dogma of Molecular Biology
Cracking the Non-Ribosomal Code
From Protein Comparison to Non-Ribosomal Code
What do Oncogenes and Growth Factors Have in Common?
Introduction to Sequence Alignment
Sequence Alignment and the Longest Common Subsequence
The Manhattan Tourist Problem
Sightseeing in an Arbitrary Directed Graph
Sequence Alignment is the Manhattan Tourist Problem in Disguise
Making a case for Dynamic Programming: The Change Problem
Changing Money Recursively
Changing Money Using Dynamic Programming
The Manhattan Tourist Problem Revisited
From Manhattan to an Arbitrary Directed Acyclic Graph
Backtracking in the Alignment Graph
Scoring Alignments
From Global to Local Alignment
The Changing Faces of Sequence Alignment
The Changing Faces of Sequence Alignment: Fitting Alignment
The Changing Faces of Sequence Alignment: Overlap Alignment
Penalizing Insertions and Deletions in Sequence Alignment
Space Efficient Sequence Alignment
Epilogue: Multiple Sequence Alignment
Quiz
Biological Sequences: Detours
Detour: Fireflies and the Non-Ribosomal Code
Detour: Finding a Longest Common Subsequence
Detour: Constructing a Topological Ordering
Detour: PAM Scoring Matrices
Detour: Divide-and-Conquer Algorithms
Detour: Scoring Multiple Alignments
Conclusion
Final Remarks
The Frequent Words Problem
Find the most frequent k-mers in a string.
We'll cover the following
Most frequent k-mer
Solution explanation
Charging Station (The Frequency Array)
Frequent words in Vibrio Cholerae
Get hands-on with 1200+ tech skills courses.
Start Free Trial