[Bmi776] study guide for final exam

[Mark Craven]

Hi All,

Two comments about the exam:

1) I forgot to mention this in class, but you can bring
two pages of notes to use during the final exam.  Write
whatever you want on these pages.

2) Below is something of a study guide.  For each
major topic, I've listed the concepts you should 
understand, and the algorithms you should be able
to work in detail.

Mark



Probabilistic Sequence Analysis
	concepts to know
		the motif learning task
		EM algorithms
		Gibbs sampling
		tying parameters
		the MDD representation
		semi-Markov models (generalized HMMs)
		dynamic programming with semi-Markov models
		TWINSCAN paired sequence representation
		pairwise HMMs
		sensitivity/recall, specificity, precision
	be able to do
		MEME algorithm
		interpolated Markov models
		back-off models
		design HMMs with specified duration models

Sequence Alignment
	concepts to know
		the genome-alignment task
		genome rearrangements
		suffix trees
		tries
		threaded tries
		maximal unique matches (MUMs)
		multi-MUMs
		longest increasing subsequence problem
		constrained dynamic programming
		recursive anchoring
		overview of MUMMER/LAGAN/MLAGAN/Mauve algorithms
	be able to do
		show suffix trees for a given (set of) string(s)
		show trie/threaded trie for strings
		calculate MUMs and mult-MUMs

RNA structure modeling
        concepts to know
                RNA secondary structure
		the secondary structure prediction task
                how Nussinov can be generalized to do energy minimization
                transformational grammars
                probabilistic grammars
                the Chomsky hierarchy
                why CFGs are appropriate for RNA modeling
                what the Inside, CYK and Inside/Outside algorithms do
		using SCFGs for structure/sequence alignments
		using SCFGs to predict novel RNA genes
        be able to do
                the Nussinov algorithm
                show parse trees for a sequence with a given grammar
                Inside algorithm
		Inside/Outside algorithm

Biomedical Text Processing
	concepts to know
		the vector space model
		the ARROWSMITH system
		using EM to find themes in literature
		the experiment annotation task
		the named-entity recognition task
		the relation-extraction task
		hierarchical HMMs
		the gene/protein annotation task
		the CSM/CSC method
		the method for augmenting PSI-BLAST with text
	be able to do
		Schwartz & Hearst algorithm for recognizing abbreviations
		
Network Models
	concepts to know
		Bayesian networks
		dynamic Bayesian networks
		representing CPDs using tables, linear Gaussian models, trees
		the structure learning problem
		Bayesian approach to scoring networks
		the parameter learning problem
		Markov blankets
		the bootstrap method
		permutation testing
		how to elucidate causality
		the general inference problem
		
	be able to do
		the Sparse Candidate algorithm
		inference by enumeration
		inference by variable elimination