For Fall 2023, CMSC892A meets on Tuesdays and Thursdays. A tentative course schedule is below. Typically, slides will be posted to ELMS right before the lecture and then linked here after (note that the slides linked well in advance of the lecture are being re-posted from last year; these may be changed before the lecture).
| Week | Day | Date | Class | Notes | Associated Reading |
|---|---|---|---|---|---|
| 1 | Tu | Aug 29th | Preliminaries 1 | Lecture: Class overview and some biological background [1_overview.pdf] [2_biol.pdf] | CP Appendix B (for those looking to review algorithms) |
| Th | Aug 31st | Preliminaries 2 | Lecture: Problems, Method Evaluation, and Data Processing (part 1); likely start the MSA module (see below) [3_probs-mthd-eval-and-data.pdf] | ||
| 2 | Tu | Sep 5th | Class canceled | ||
| Th | Sep 7th | Multiple Sequence Alignment | Lecture: Pairwise alignment (review) and then multiple sequence alignment, specifically generalized tree alignment problem, sum-of-pairs (SOP) alignment problem, STAR alignment [4_msa_part1.pdf] | CP Sections 9.1-9.5.3 and 9.12 | |
| 3 | Tu | Sep 12th | Modern MSA | Lecture: Consistency and maximum weight trace (MWT) problem, sequence profiles, aligning alignments, progressive alignment, iterative refinement, divide-and-conquer, popular MSA methods (Clustal W/Omega, T-Coffee, MAFFT, MUSCLE, PASTA) [5_msa_part2.pdf] | CP Sections 9.6-9.74, 9.10-9.16 |
| Th | Sep 14th | Profile Hidden Markov Models (HMMs) |
Lecture: Supervised training (Maximum Likelihood), decoding (Viterbi algorithm) (also of interest is unsupervised training with Baum-Welch algorithm and posterior decoding with Forward and Background algorithms)
[6_profile_hmms.pdf]
|
BSA Sections 5.1-5.8 | |
| 4 | Tu | Sep 21st | Variant Calling and Tree Basics | Data Processing (part 2 - variant calling); Tree Basics (e.g., clade, bipartition, contraction, refinement, etc.) [7_variant_calling.pdf] [8_trees.pdf] [8_trees_worksheet.pdf] | CP Sections 2.1-2.2.2, 2.3-2.3.4, 2.5-2.6, and 2.10 |
| Th | Sep 21st | Compatibility | Lecture: Constructing trees from clades (Hasse diagram approach), clade compatibility, bipartition compatibility, homoplasy, character compatibility, perfect phylogeny problem, maximum compatibility problem, infinite sites assumption [9_compatibility.pdf] | CP Sections 2.1-2.5, 4.4 | |
| 5 | Tu | Sep 26th | Parsimony | Lecture: Maximum parsimony problem (small and large), Fitch's algorithm, branch-and-bound, randomized taxon addition, search moves (NNI, SPR, TBR), consensus trees [10_parsimony.pdf] | CP Sections 4.1-4.3, 4.6-4.7, 6.1-6.2.3, Example 6.7 |
| Th | Sep 28th | CFN model and Maximum likelihood |
Lecture: How to generate data under Cavendar-Farris-Neyman (CFN) model, How to compute probability of characters under CFN model, Felsenstein's Pruning Algorithm, Maximum Likelihood problem, statistical consistency
[11_finite_sites.pdf]
|
CP Sections 1.1-1.4, 8.1, 8.5-8.6, 8.8 | |
| 6 | Tu | Oct 3rd | Molecular Sequence Evolution Models and Applications |
Lecture: Time-continuous Markov Chains, Jukes-Cantor model, Generalized Time Reversible (GTR) model, SHR assumptions as well as practical issues: insertions/deletions (missing data), model violations, varying rates across sites (CAT and GAMMA models), taxon sampling, uncertainty quantification (bootstrapping vs. Bayesian), phylogenetic placement and applications to taxonomic identification
|
CP Sections 8.2 |
| Th | Oct 5th | Population-level processes | Lecture: Population-level processes (coalescent and recombination), Multi-Species Coalescent (MSC) model, concatenation vs. coalescent methods, practical issues (recombination ratchet, gene tree estimation error, missing data, etc.) [12_species_tree_msc.pdf] | CP Sections 10.1-10.5.2 (skipping 10.5.1) | |
| 7 | Tu | Oct 10th | Triplet Methods | Lecture: Triplet methods for species tree estimation under MSC model - includes tree edit operations, compatibility supertrees, ASSU algorithm, STELAR, MP-EST [13_triplet_methods.pdf] | CP Section 10.5.1 |
| Th | Oct 12th | Distance and Quartet Methods |
Lecture: Quartet methods for species tree estimation under MSC model (includes All Quartets algorithm and ASTRAL), average gene tree internode distances, p-distances and model-corrected distances), additive and nearly additive, ultrametric, Naive Quartet method, UPGMA, and Neighbor Joining
[14_quartet_and_distance_methods.pdf]
|
CP Sections 10.5.1 (quartet methods), 7.7, 10.5.1 (distance methods) 5.1, 5.3-5.5.1, 8.4, 5.2, 5.6-5.10 | |
| 8 | Tu | Oct 17th | No lecture | Intentionally leaving free in case other lectures run long, review, + project discussion | |
| Th | Oct 19th | Tumor Phy I | Lecture by Dr. Salem Malikic: Overview of tumor evolution and Integer Linear Programming (ILP), Studying the history of tumor evolution from bulk sequencing data (method: CITUP) | CITUP paper | |
| 9 | Tu | Oct 24th | Tumor Phy II |
Lecture by Dr. Salem Malikic:
Inference of trees of tumor evolution from single-cell sequencing data under perfect phylogeny model (methods: SCITE and ScisTree).
|
SCITE paper and ScisTree paper |
| Th | Oct 26th | Tumor Phy III | Lecture by Dr. Salem Malikic: Exact ILP formulations for tree inference from single-cell data under subperfect phylogeny and k-Dollo evolutionary models (methods: PhISCS and gpps) | PhISCS paper and gpps paper | |
| 10 | Tu | Oct 31st | Tumor Phy IV | Lecture by Dr. Cenk Sahinalp Branch-and-bound for subperfect phylogeny (method: PhISCS-BnB), Identifying common evolutionary trajectories with ILP (method: CONETT) | PhISCS-BnB paper and CONETT paper |
| Th | Nov 2nd | Tumor Phy V |
Lecture by Dr. Cenk Sahinalp:
Quantifying uncertainy with partition function formulation, may also cover consensus trees
|
||
| 11 | Tu | Nov 7th | Species vs. tumor phylo | Lecture by Yunheng Han Models + methods for species vs. tumor phylogenies | Preprint (accepted at WABI 2023); Also TREE-QMC paper |
| Th | Nov 9th | Exam Review |
See this exam study guide for a list of concepts and problems; also review the graded homework
|
||
| 12 | Tu | Nov 14th | Species vs. tumor phylo, cont | Unpublished work (but will also review some core ideas for exam) | |
| Th | Nov 16th | Exam | In-class exam TODAY (Thursday, November 16th in IRB-2207 from 3:30pm-4:45pm ET)! | ||
| 13 | Tu | Nov 21st | No class! |
Extended thanksgiving break from classes
|
|
| Th | Nov 23rd | No class! | Thanksgiving break | ||
| 14 | Tu | Nov 28th | Phylo networks and Admixture graphs | Leveraging graph theoretic results for phylogenetics networks for admixture graph estimation | OrientAGraph paper |
| Th | Nov 30th | Ancestral recombination graphs | |||
| 15 | Tu | Dec 5th | Project Presentations | Schedule on ELMS | |
| Th | Dec 7th | Project Presentations | Schedule on ELMS | ||
| 17 | Mo | Dec 18th | Deadline | Project reports due today (Monday, December 18th at 11:59PM ET)! |