Содержание курса
11
разделов
213
уроков
45
тестов
126
задач
145 ч.
обн. 2 года назад
Where in the Genome Does Replication Begin?
17 уроков
1.
A Journey of a Thousand Miles. . .
↗
2.
Hidden Messages in the Replication Origin
↗
3.
Some Hidden Messages are More Surprising than Others
↗
4.
An Explosion of Hidden Messages
↗
5.
The Simplest Way to Replicate DNA
↗
6.
Asymmetry of Replication
↗
7.
Peculiar Statistics of the Forward and Reverse Half-Strands
↗
8.
Some Hidden Messages are More Elusive than Others
↗
9.
A Final Attempt at Finding DnaA Boxes in E. coli
↗
10.
Epilogue: Complications in ori Predictions
↗
11.
CS: Generating the Neighborhood of a String
↗
12.
Detour: Big-O Notation
↗
13.
Detour: Probabilities of Patterns in a String
↗
14.
Detour: The Most Beautiful Experiment in Biology
↗
15.
Detour: Directionality of DNA Strands
↗
16.
Detour: The Towers of Hanoi
↗
17.
Detour: The Overlapping Words Paradox
↗
Which DNA Patterns Play the Role of Molecular Clocks?
17 уроков
1.
Do We Have a "Clock" Gene?
↗
2.
Motif Finding Is More Difficult Than You Think
↗
3.
Scoring Motifs
↗
4.
From Motif Finding to Finding a Median String
↗
5.
Greedy Motif Search
↗
6.
Motif Finding Meets Oliver Cromwell
↗
7.
Randomized Motif Search
↗
8.
How Can a Randomized Algorithm Perform So Well?
↗
9.
Gibbs Sampling
↗
10.
Gibbs Sampling in Action
↗
11.
Epilogue: How Does Tuberculosis Hibernate?
↗
12.
CS: Solving the Median String Problem
↗
13.
Detour: Gene Expression
↗
14.
Detour: DNA Arrays
↗
15.
Detour: Buffon's Needle
↗
16.
Detour: Complications in Motif Finding
↗
17.
Detour: Relative entropy
↗
How Do We Assemble Genomes?
23 урока
1.
Exploding Newspapers
↗
2.
The String Reconstruction Problem
↗
3.
String Reconstruction as a Walk in the Overlap Graph
↗
4.
Another Graph for String Reconstruction
↗
5.
Walking in the de Bruijn Graph
↗
6.
The Seven Bridges of Königsberg
↗
7.
Euler's Theorem
↗
8.
From Euler's Theorem to an Algorithm for Finding Eulerian Cycles
↗
9.
Assembling Genomes from Read-Pairs
↗
10.
Epilogue: Genome Assembly Faces Real Sequencing Data
↗
11.
CS: The Effect of Gluing on the Adjacency Matrix
↗
12.
CS: Generating All Eulerian Cycles
↗
13.
CS: Reconstructing a String from the Paired de Bruijn Graph
↗
14.
CS: Maximal Non-Branching Paths in a Graph
↗
15.
Detour: A Short History of DNA Sequencing Technologies
↗
16.
Detour: Repeats in the Human Genome
↗
17.
Detour: An Introduction to Graphs
↗
18.
Detour: Hamilton's Icosian Game
↗
19.
Detour: Tractable and Intractable Problems
↗
20.
Detour: From Euler to Hamilton to de Bruijn
↗
21.
Detour: The Seven Bridges of Kaliningrad
↗
22.
Detour: The BEST Theorem
↗
23.
Detour: Pitfalls of assembling double-stranded DNA
↗
How Do We Sequence Antibiotics?
20 уроков
1.
The Discovery of Antibiotics
↗
2.
How Do Bacteria Make Antibiotics?
↗
3.
Dodging the Central Dogma of Molecular Biology
↗
4.
Sequencing Antibiotics by Shattering Them into Pieces
↗
5.
A Brute Force Algorithm for Cyclopeptide Sequencing
↗
6.
A Branch-and-Bound Algorithm for Cyclopeptide Sequencing
↗
7.
Mass Spectrometry Meets Golf
↗
8.
From 20 to More than 100 Amino Acids
↗
9.
The Spectral Convolution Saves the Day
↗
10.
Epilogue: From Simulated to Real Spectra
↗
11.
CS: Generating the Theoretical Spectrum of a Peptide
↗
12.
CS: How Fast is CyclopeptideSequencing?
↗
13.
CS: Trimming the Peptide Leaderboard
↗
14.
Detour: Gause and Lysenkoism
↗
15.
Detour: The Discovery of Codons
↗
16.
Detour: Quorum Sensing
↗
17.
Detour: Molecular Mass
↗
18.
Detour: Selenocysteine and Pyrrolysine
↗
19.
Detour: Pseudo-polynomial Algorithm for the Turnpike Problem
↗
20.
Detour: Split genes
↗
How Do We Compare Biological Sequences?
20 уроков
1.
Cracking the Non-Ribosomal Code
↗
2.
Introduction to Sequence Alignment
↗
3.
The Manhattan Tourist Problem
↗
4.
Sequence Alignment is the Manhattan Tourist Problem in Disguise
↗
5.
An Introduction to Dynamic Programming: The Change Problem
↗
6.
The Manhattan Tourist Problem Revisited
↗
7.
From Manhattan to an Arbitrary DAG
↗
8.
Backtracking in the Alignment Graph
↗
9.
Scoring Alignments
↗
10.
From Global to Local Alignment
↗
11.
The Changing Faces of Sequence Alignment
↗
12.
Penalizing Insertions and Deletions in Sequence Alignment
↗
13.
Space-Efficient Sequence Alignment
↗
14.
Epilogue: Multiple Sequence Alignment
↗
15.
Detour: Fireflies and the Non-Ribosomal Code
↗
16.
Detour: Finding an LCS without Building a City
↗
17.
Detour: Constructing a Topological Ordering
↗
18.
Detour: PAM Scoring Matrices
↗
19.
Detour: Divide-and-Conquer Algorithms
↗
20.
Detour: Scoring Multiple Alignments
↗
Are There Fragile Regions in the Human Genome?
18 уроков
1.
Of Mice and Men
↗
2.
The Random Breakage Model of Chromosome Evolution
↗
3.
Sorting by Reversals
↗
4.
A Greedy Algorithm for Sorting by Reversals
↗
5.
Breakpoints
↗
6.
Rearrangements in Tumor Genomes
↗
7.
From Unichromosomal to Multichromosomal Genomes
↗
8.
Breakpoint Graphs
↗
9.
Computing the 2-Break Distance
↗
10.
Rearrangement Hotspots in the Human Genome
↗
11.
Epilogue: Synteny Block Construction
↗
12.
CS: From Genomes to the Breakpoint Graph
↗
13.
CS: Solving the 2-Break Sorting Problem
↗
14.
Detour: Why is the Gene Content of X Chromosomes So Conserved?
↗
15.
Detour: Discovery of Genome Rearrangements
↗
16.
Detour: The Exponential Distribution
↗
17.
Detour: Bill Gates and David X. Cohen Flip Pancakes
↗
18.
Detour: Sorting Linear Permutations by Reversals
↗
Which Animal Gave Us SARS?
19 уроков
1.
The Fastest Outbreak
↗
2.
Transforming Distance Matrices into Evolutionary Trees
↗
3.
Toward An Algorithm for Distance-Based Phylogeny Construction
↗
4.
Additive Phylogeny
↗
5.
Using Least Squares to Construct Approximate Phylogenies
↗
6.
Ultrametric Evolutionary Trees
↗
7.
The Neighbor-Joining Algorithm
↗
8.
Character-Based Tree Reconstruction
↗
9.
The Small Parsimony Problem
↗
10.
The Large Parsimony Problem
↗
11.
Epilogue: Evolutionary Trees Fight Crime
↗
12.
Detour: When Did HIV Jump from Primates to Humans?
↗
13.
Detour: Searching for a Tree Fitting a Distance Matrix
↗
14.
Detour: The Four Point Condition
↗
15.
Detour: Did Bats Give Us SARS?
↗
16.
Detour: Why Does the Neighbor-Joining Algorithm Work?
↗
17.
Detour: Computing Limb Lengths in the Neighbor-Joining Algorithm
↗
18.
Detour: Giant Panda: Bear or Raccoon?
↗
19.
Detour: Where Did Humans Come From?
↗
How Did Yeast Become a Wine Maker?
21 урок
1.
An Evolutionary History of Wine-Making
↗
2.
Identifying Genes Responsible for the Diauxic Shift
↗
3.
Introduction to Clustering
↗
4.
The Good Clustering Principle
↗
5.
Clustering as an Optimization Problem
↗
6.
Farthest First Traversal
↗
7.
k-Means Clustering
↗
8.
The Lloyd Algorithm
↗
9.
Clustering Genes Implicated in the Diauxic Shift
↗
10.
Limitations of k-means Clustering
↗
11.
From Coin Flipping to k-Means Clustering
↗
12.
Making Soft Decisions in Coin Flipping
↗
13.
Soft k-Means Clustering
↗
14.
Hierarchical Clustering
↗
15.
Epilogue: Clustering Tumor Samples
↗
16.
Detour: Whole Genome Duplication or a Series of Duplications?
↗
17.
Detour: Measuring Gene Expression
↗
18.
Detour: Microarrays
↗
19.
Detour: Proof of the Center of Gravity Theorem
↗
20.
Detour: Gene Expression Matrix to a Distance/Similarity Matrix
↗
21.
Detour: Clustering and Corrupted Cliques
↗
How Do We Locate Disease-Causing Mutations?
22 урока
1.
What Causes Ohdo Syndrome?
↗
2.
Introduction to Multiple Pattern Matching
↗
3.
Herding Patterns into a Trie
↗
4.
Preprocessing the Genome Instead
↗
5.
Suffix Trees
↗
6.
Suffix Arrays
↗
7.
The Burrows-Wheeler Transform
↗
8.
A First Attempt at Inverting the Burrows-Wheeler Transform
↗
9.
The First-Last Property and Burrows-Wheeler Inversion
↗
10.
Pattern Matching with the Burrows-Wheeler Transform
↗
11.
Speeding Up Burrows-Wheeler Pattern Matching
↗
12.
Where are the Matched Patterns?
↗
13.
Burrows and Wheeler Set Up Checkpoints
↗
14.
Epilogue: Mismatch-Tolerant Read Mapping
↗
15.
CS: Constructing a Suffix Tree
↗
16.
CS: Solving the Longest Shared Substring Problem
↗
17.
CS: Partial Suffix Array Construction
↗
18.
Detour: The Reference Human Genome
↗
19.
Detour: Rearrangements, Insertions, & Deletions in Human Genomes
↗
20.
Detour: The Aho-Corasick Algorithm
↗
21.
Detour: Suffix Arrays and Suffix Trees
↗
22.
Detour: Binary Search
↗
Why Have Biologists Still Not Developed an HIV Vaccine?
18 уроков
1.
Classifying the HIV Phenotype
↗
2.
Gambling with Yakuza
↗
3.
Two Coins Up the Dealer's Sleeve
↗
4.
Finding CG-Islands
↗
5.
Hidden Markov Models
↗
6.
The Decoding Problem
↗
7.
Finding the Most Likely Outcome of an HMM
↗
8.
Profile HMMs for Sequence Alignment
↗
9.
Classifying Proteins with Profile HMMs
↗
10.
Learning the Parameters of an HMM
↗
11.
Soft Decisions in Parameter Estimation
↗
12.
Baum-Welch Learning
↗
13.
The Many Faces of HMMs
↗
14.
Epilogue: Nature is a Tinkerer and not an Inventor
↗
15.
Detour: The Red Queen Effect
↗
16.
Detour: Glycosylation
↗
17.
Detour: DNA Methylation
↗
18.
Detour: Conditional Probability
↗
Was T. rex Just a Big Chicken?
18 уроков
1.
Paleontology Meets Computing
↗
2.
Which Proteins are Present in this Sample?
↗
3.
Decoding an Ideal Spectrum
↗
4.
From Ideal to Real Spectra
↗
5.
Peptide Sequencing
↗
6.
Peptide Identification
↗
7.
Peptide Identification and the Infinite Monkey Theorem
↗
8.
Spectral Dictionaries
↗
9.
T. rex Peptides: Contaminants or Ancient Treasure Trove?
↗
10.
Epilogue: From Unmodified to Modified Peptides (Part 1)
↗
11.
Epilogue: From Unmodified to Modified Peptides (Part 2)
↗
12.
Detour: Gene Prediction
↗
13.
Detour: Finding All Paths in a Graph
↗
14.
Detour: The Anti-Symmetric Path Problem
↗
15.
Detour: Transforming Spectra into Spectral Vectors
↗
16.
Detour: The Infinite Monkey Theorem
↗
17.
Detour: The Probabilistic Space of Peptides in a Dictionary
↗
18.
Detour: Are Terrestrial Dinosaurs Really the Ancestors of Birds?
↗