CS 466

Algorithmic approaches in bioinformatics: (i) biological problems that can be solved computationally (e.g., discovering genes, and interactions among different genes and proteins); (ii) algorithmic techniques with wide applicability in solving these problems (e.g., dynamic programming and probabilistic methods); (iii) practical issues in translating the basic algorithmic ideas into accurate and efficient tools that biologists may use. Course Information: 3 undergraduate hours. 3 or 4 graduate hours. Prerequisite: CS 225.

Jones and Pevzner, An Introduction to Bioinformatics Algorihms.

work out optimal sequence alignment problems on toy sequences, and implement a program to do the same on modest sequence lengths. (1)
list the main challenges in genome assembly and explain high level algorithms used to solve them (1)
understand how statistical methods and HMMs in particular apply to gene finding, and implement the Viterbi algorithm for a simple HMM (1)
use online tools for gene set enrichment analyses and interpret results (1)
implement a “motif finding” method to find transcription factor binding sites in gene promoters (1) (2) (5)
perform hierarchical clustering on toy data sets manually, and on gene expression data sets (1)
build a maximum parsimony evolutionary tree for given sequences and a tree topology (1)
understand what is meant by RNA secondary structures and outline a dynamic programming algorithm for finding the structure with most base pairs or with least energy (1)

Basics of statistics and molecular biology
Sequence alignment using dynamic programming, pattern matching, BLAST
Genome sequencing and assembly
Gene finding with statistical approaches and HMM
Statistical testing and gene set analysis.
Motif finding and regulatory genomics
Clustering of microarray data
Gene classification from high throughput measurements
RNA secondary structure
Phylogenetics

Revisions in last 6 years	Approximately when revision was done	Reason for revision
Changed textbook	Spring 2011	Previous textbook lacked statistical aspects
Introduced mini project (implementation based)	Spring 2011	This was expected to increase the focus on programming aspects of the subject

Selected Elective.

2/15/2019