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

Charging Station: Conversions between Patterns and Numbers

Learn how to convert patterns into numbers and decode these numbers to get the original sequence.

Our approach to computing PatternToNumber(Pattern) is based on a simple observation. If we remove the final symbol from all lexicographically ordered k-mers, the resulting list is still ordered lexicographically (think about removing the final letter from every word in a dictionary). In the case of DNA strings, every (k − 1)-mer in the resulting list is repeated four times.

Get hands-on with 1300+ tech skills courses.