CS 395T: Algorithms for Computational Biology
Instructor: Tandy Warnow
- Location: CBA 4.340
- Time: TuTh 2:00-3:30
- Office hours for April 28 - May 13:
- Wednesday May 30, 4-5
- Wednesday May 7, 3-5 (sign up for 15 minute slots). Please
bring your homeworks and exam (and project proposal) to this time slot.
The course topic is algorithm design in computational
molecular biology, but we will focus our study on two
related topics: multiple sequence alignment and phylogeny
(evolutionary history) reconstruction. These problems
are intimately related because the inference of an
evolutionary history generally involves first obtaining
a multiple alignment of the sequences, and then reconstructing
a tree on the aligned sequences (though a simultaneous
approach can also be taken). Both these problems are
individually enormously computationally intensive -
computational approaches generally involve attempts to
solve NP-hard optimization problems, and months of
analysis can be used to estimate the phylogeny, without
any guarantee of optimality. Thus, algorithmic
development, firmly grounded in mathematical theory,
is needed by the biological research community.
The goal of the course is to enable the students to do high
quality research (both mathematical and algorithmic) for both
multiple sequence alignment and phylogeny reconstruction.
The mathematical foundations of phylogeny reconstruction
are quite elegant and deep, and so most of our discussion
will be focused there.
We will cover the statistical models used to describe evolution of
molecular sequences, the primary optimization problems, and the
mathematical theory needed to predict the performance of
reconstruction methods under the models. The course will also
present a large spectrum of algorithms (both deterministic
with established theory, and heuristics) that have been developed
for these problems. In addition, we will have several lectures from
guest biologists with whom I collaborate.
No background in biology is assumed for this course.
The mathematics used in developing algorithms for both phylogeny
reconstruction and multiple sequence alignment combines combinatorics
and graph theory (including the theory of chordal graphs), complexity
theory, and probability and statistics. Students with good preparation
in at least one of these areas will be able to begin doing algorithm
development early on. However, abundant research opportunities exist
for those students without significant mathematical training: simulation
studies of existing methods is an important methodology within the field,
and has resulted in many highly influential and important publications
in major scientific journals. Therefore, students of all backgrounds
(including from biology) are welcome.
The grading scheme is:
- Class participation: 5%
Class notes: 10%
The course requires a final project of each student:
click here for a list of suggested topics.
Your final project should be a paper of about 15 pages, in a format
appropriate for submission to a journal.
The grade on the final project will be 30% writing, 30% summary of the
literature you discuss, and 40% commentary (i.e., insight,
critical and thoughtful discussion of the issues that come up).
The final project is due at the beginning of the final exam.
The final exam will cover all the material discussed in the course,
and will be closed book.
You are also responsible for four of the papers that were presented
the paper by Wayne Maddison (presented on March 19)
on phylogenetic networks by Jin et al. (presented
on March 25)
the paper by Nakhleh et al. (presented
on April 8)
and the paper by
Gusfield et al. (presented on April 24)
You are not responsible for the proofs but are responsible for
knowing the results (but only the ones that
appear in the talks - not everything).
Analysis, a course taught by Luay Nakhleh at Rice University. His
course website has slides from his course, a reading list,
and a list of software tools (some for alignment and some for
phylogeny reconstruction), all of which are likely to be helpful
101, a website provided by UC Berkeley for teaching about evolution.
Recommended (not required) reading
An overview of phylogeny
reconstruction, by C. Randall Linder
and T. Warnow.
Handbook of Computational Molecular Biology, Chapman and Hall, 2005, Chapter 19-1.
Disk Covering Methods: improving
the accuracy and speed of large-scale phylogenetic analyses,
by T. Warnow,
Handbook of Computational Molecular Biology, Chapman and Hall, 2005,
Network (Reticulate) Evolution: Biology, Models, and Algorithms,
by C. Randal Linder, Bernard M.E. Moret, Luay Nakhleh, and Tand Warnow.
Tutorial presented at the Pacific Symposium on Biocomputing 2004.
Jan 15, 2008: (PPT) (PDF)
Jan 17, 2008: (PPT)
Jan 22, 2008. Part 1:
(PPT) (PDF) and
February 5, 2008. Analyzing sets of trees: consensus methods
February 7, 2008. Serita Nelesen will talk about
her research on efficient techniques for storing
sets of trees compactly.
February 12, 2008. Recap of earlier work.
February 14, 2008. Dynamic programming and global pairwise alignment.
February 19, 2008. Species phylogenies and gene trees: conflict and resolution.
February 21, 2008. Multiple sequence alignment: NP-hardness.
Scribe notes by Rahul Suri
February 25, 2008. Beginnings of reticulate evolution.
February 28, 2008. Scribe notes by Sindhu Raghavan
March 4, 2008.
Scribe notes by Bakhtiyar Uddin
March 19, 2008. Rajan presented the paper by Wayne Maddison
March 25, 2008. Sindhu Raghavan presented a paper by
Jin, Nakhleh, Snir, and Tuller,
Inferring phylogenetic networks by the parsimony criterion: a
Scribe notes by Badri Narayanan Champakesan
March 27, 2008. T.D. Luckett and Rahul Suri
the RIATA-HGT paper by Nakhleh et al.
Click here for
the PPT, and
here for the PDF
of their presentation.
Also see (PDF) for the scribe
- April 1. Jeffrey Matthew presented the paper
by Addario-Berry, Hallet, and Lagergren,
"Towards identifying lateral gene transfer events", PSB 2008.
- April 8. Mahesh Prabhu presented
"Reconstructing reticulate evolution in species - theory and
practice", by Nakhleh et al (JCB 2005)
- April 10, review of previous papers.
- April 15. Bakhtiyar Uddin presents the paper
"Constructing Splits Graphs" by Andreas Dress and Daniel Huson
Click here for Rajan's
- April 17 and 22. Vikas Taliwal, discussing
paper by Gusfield, Bansal, Bafna, and Song,
"A decomposition theory for phylogenetic networks and
incompatible characters." (PPT)
See here for Mahesh's
- April 24. Two talks: Badri Narayanan, talking about
"Optimal reconstruction of root-unknown phylogenetic networks with
constrained and structured recombination" by Dan Gusfield
John Leavitt, talking about
"A regulator of G protein signaling interaction surface linked to effector specificity"
See (PDF) for Peggy Wang's scribe notes.
- April 29. Two talks: Peggy Wang (PPT), discussing
D. Huson and D. Bryant: Application of phylogenetic networks in evolution. MBE 23(2):254-267, 2006,
Razieh Nakbeh Zaeem (PPT).
May 1, 2008. Guest lecturer: Professor Bill Press (UTCS).
Homework #2 (due Feb 21): Do
one of the following problems.
(1) Give a dynamic programming algorithm for computing the longest leaf-to-leaf path in a tree. (Here we define the length of a path to be the number of edges in the path.) This is also called the "topological diameter" of the tree. Analyze the running time.
Give a dynamic programming algorithm for the longest common subsequence
between two strings. This is the same problem as finding
the minimum number of deletions from the two strings so
that the result is two identical strings. Thus, the longest common
subsequence of AAAAAAAAAA and CATTAGAA is AAAA. Analyze the running time.
Take home midterm, due Thursday March 20 (in class).
Click here for the PDF file.
Important! There are some slight problems with the midterm.
Please click here for
a PDF file with the corrections, and some additional comments.
In class final exam (May 13), closed book.
Your final project is due on May 13, the day of the final exam. Please
provide me with a 2 page proposal for the project by
April 29 (list paper(s) you will
read and questions you will discuss). I will give this
proposal back to you with comments by May 1.
Papers on networks to read
for the "Who's Who of Phylogenetic Networks" and some of these papers.
- W. Maddison, Gene Trees in Species Trees, Systematic Biology 46(3): 523-536,
- L. Nakhleh, T. Warnow, C. R. Linder, and K. St. John.
Reconstruction of phylogenetic networks: theory and practice.
Journal Computational Biology, Vol 12(6): 796-811, 2005
L. Nakhleh, D. Ruths, and L-S. Wang.
RIATA-HGT: a fast and accurate heuristic for reconstructing horizontal gene
transfer. COCOON 2005, Vol. 3595:84-93, 2005
- G. Jin, L. Nakhleh, S. Snir, and
T. Tuller. Maximum likelihood of phylogenetic networks. Bioinformatics,
Vol 22(21):2604-2611, 2006.
- L. Nakhleh and L-S. Wang. Phylogenetic networks: properties and
relationship to trees and clusters. TCSB2, Vol. 3680:82-99, LNCS, 2005.
- D. Bryant, V. Moulton, and A. Spiller, Consistency of the Neighbor-Net
Algorithm. AMB, Vol 2(8), 2007.
- G. Jin, L. Nakhleh, S. Snir, T. Tuller. Inferring phylogenetic networks
by the maximum parsimony criterion: a case study. MBE, Vol. 24(1):324-337, 2007.
- B. Holland, G. Conner, K. Huber, and V. Moulton. Imputing
supertrees and supernetworks from quartets. Systematic Biology, Vol. 56(1): 57-67,
- O. Gauthier, F-J. Lapointe. Seeing the trees for the network: consensus,
information content, and superphylogenies.
Systematic Biology, Vol 56(2):345-355, 2007.
- M. Bordewich and C. Semple. Computing the hybridization number of two
phylogenetic trees is fixed-parameter tractable. TCBB, Vol 4:458-466, 2007.
- D. Gusfield, V. Bansal, V. Bafna, and Y. Song.
A decomposition theory for phylogenetic networks and incompatible characters.
Journal Computational Biology, Vol 14(10):1247-1272, 2007.
- D. Gusfield. Optimal, efficient reconstruction of root-unknown
phylogenetic networks with constrained and structured recombination.
JCSS, 2005 Special Issue on Computational Biology, Vol. 70, p. 381-398.
- Y. Song, Z. Ding, D. Gusfield, C. Langley, Y. Wu.
Algorithms to distinguish the role of gene-conversion from single-crossover
recombination in the derivation of SNP sequences in populations.
J. Computational Biology, Dec. 2007, Vol. 14, No. 10: 1273-1286.
- Y. Song, Y. Wu and D. Gusfield.
Efficient computation of close lower and upper bounds on the minimum number
of recombinations in biological sequence evolution.
Proceedings of ISMB 2005.
- M. Hallet, J. Lagergren, and A. Tofigh.
Simultaneous identification of duplications and lateral transfers.
in RECOMB 2004, pp. 347-356.
- M. Hallett and J. Lagergren. Efficient algorithms for
laeral gene transfers problems.
Submitted to SICOMP.
- M. Hallett and J. Lagergren. Efficient algorithms for
lateral gene transfers problems.
RECOMB 2001, pp. 141-148.
- L. Addario-Berry, M. Hallet and J. Lagergren.
Towards identifying lateral gene transfer events.
- D. Huson. Split networks and reticulate networks.
In Reconstructing Evolution, new mathematical and computational advances,
Edited by O. Gascuel and M. Steel,
pp. 247-276, Oxford Univ. Press. 2007.
D. Huson and T. Kloepper. Beyond Galled Trees - decomposition
and computation of galled networks.
RECOMB 2007, Vol. 4453:211-227.
D. Huson and D. Bryant. Application of phylogenetic networks
in evolution. MBE 23(2):254-267, 2006.
- A. Dress and D. Huson. Constructing splits graphs.
TCBB Vol 1(3):109-115, 2004.