Princeton University
Computer Science Dept.

Computer Science 597
Advanced Topics in Computer Science
Computational Biology

Tandy Warnow

Fall 1997

Seminar on Computational Biology

Topic: evolutionary tree reconstruction methodology and algorithms in Biology and Linguistics.
Prerequisites: graduate course in discrete algorithms and interest in experimental algorithms and scientific issues. No biological or linguistic knowledge will be presumed.
Course will be held on Tuesdays from 10-12 in 301 Computer Science. This is a change from the original schedule!

September 15: introduction.
September 23.
Distance-based optimization problems and algorithms. Additive and ultrametric trees. Buneman four-point theorem. Combinatorics of trees and character encodings of tree topologies. Quartet-based tree reconstruction algorithms. Topology invariant neighborhoods of additive trees.
September 30.
Farach-Kannan-Warnow optimal ultrametric tree reconstruction and related algorithms. Agarwala et al. 3-approximation algorithm for the tex2html_wrap_inline26 -nearest tree problem.
October 7.
Stochastic models of iid site evolution, and performance of distance-based methods for trees under such models. Statistical performance issues.
October 14.
Character based tree reconstruction methods. Parsimony, compatibility, and maximum likelihood estimation. NP-hardness and approximation algorithms for parsimony and compatibility. Statistical properties of character-based methods.
October 21.
Perfect Phylogeny problem and algorithms. Triangulating colored graphs formulation.
November 4.
Combinatorial algorithms for fixed parameter perfect phylogeny.
November 11.
Graph theoretic algorithms for fixed parameter perfect phylogeny.
November 18.
Tree reconstruction in Historical Linguistics, and application of perfect phylogeny algorithms.
November 25.
Consensus tree problems and algorithms.
December 2.
Experimental performance analysis in biological systematics. Open questions and pressing debates. The role of experimental studies (why analytical results are not enough) and methodological problems.
December 8.
Other topics, as interest and time permits. Possible topics: Multiple sequence alignment, short quartet methods, ``real data", open problems in historical linguistics.
Instructor: Tandy Warnow, tandy@cs.princeton.edu. Office 206 Computer Science. Phone 258-2211. Office hours to be announced.