Jan 22, 2008

  Lecture 1  Introduction  SIMON

• What is Bioinformatics?
• How does it relate to Computational Biology
• Why study it?

• Homology, alignments and phylogeny
• Mapping
• Gene Finding
• Determinants of protein structure
• Identification of genetic structural/metabolic lesions from gene expression data

• Computational Molecular Biology vs BioInformatics
• Strings vs Large Data Arrays

  Lecture 2   Review of Probability  SIMON

• Uniform
• Exponential family (including Exponential, Gaussian, Dirichlet/Beta, Boltzmann, Gumbel)

• Standardization
• Expectation
• Moments
• Importance of the Covariance Matrix
• Cumulants

• Joint probability
• Conditional and Unconditional (independent) Probability
• Expansion of the joint probability expression
• The Markov assumption
  • Finite Markov chains
  • Transition probabilities
  • Simplifying properties of the Markov assumption

• Maxwell's Demon
• Coding, Huffman Coding
• Shannon entropy, Minimal description length

  Lecture 3 Review of Relevant Biology   SIMON

• DNA,RNA,Genetics

Jan 29, 2008

  Lecture 4 Review of Relevant Biology   SIMON

• Proteins Sequence and Folding

  Lecture 5  Computer Models SIMON

• Finite automata and Regular Languages
• Pushdown Automata and compilers
• Turing Machines and Phrase Structured Languages
• Language Acceptance and Problem Decidability

  Lecture 6  Algorithms in this course SIMON

• Nondeterministic Polynomial time solutions of problems
• The Satisfiability Problem –NP Complete
• Cook’s Theorem: Polynomial time mapping to SAT
• NP Hard Problems: the TSP, the partition problem, the shortest common superstring
• Mapping the double-digest problem to an NP complete problem

Feb 5, 2008

  Lecture 7  Techniques for hard problems, Heuristics MANDOIU

Hard problems in Bioinformatics very often involve:
• Permutations
• Branch and Bound
• Sort Reversals
• Simulated Annealing

Lecture 8   Algorithms on strings SIMON

Pattern recognition as applied to strings – matching vs alignment
Matching Algorithms
• Naive algorithm, smarter algorithms (Boyer-Moore)
• Finite Automaton models of string searching
• Hashing functions, modulo aritmetic, prime numbers and hashing schemes for searching-Rabin Karp algorithm
• Regular Expressions and RE processing engines
• Suffix trees

Two Sequence Alignment
• Global Alignment Needleman-Wunsch
• Local Alignment Smith-Waterman

Multiple Sequence Alignment (MSA) A hard problem
• Sum of Pairs Scoring
• Star Alignment heuristic

---

GENOMICS - SEQUENCING THE GENOME

FRAGMENTATION AND AMPLIFICATION,DNA SEQUENCING, FRAGMENT ASSEMBLY

---




Feb 12, 2008

Lecture 9 DNA amplification and sequencing GUNZL

Molecular Cloning-uses
Practicalities of cloning DNA and cDNA
Libraries
Amplifying DNA- the polymerase chain reaction
Vectors
DNA sequencing

GENOMICS - FRAGMENT ASSEMBLY

Lecture 11- Genetic Maps SIMON

• Restriction Maps
• Hybridization mapping
• The Human Genome Project- Shotgun Sequencing

---

GENOMICS - IDENTIFYING THE GENES IN THE DNA

ORFs, SIGNALS and GENEFINDING

---




Feb 19, 2008

Lecture 12 Motif Elicitation RAJASEKARAN

Lecture 13 - Introduction to Artificial Neural Networks RAJASEKARAN

The Perceptron as a simple model
More advanced ideas

Feb 26, 2008

Lecture 14 Motif Finding and MSA SIMON

Motifs by EM
Motif by Gibbs Sampling
MSA by Simulated Annealing

Lecture 15 Introduction to Gene finding SIMON

• Genetic Code,Introns,Exons, ORFs,Genes
• Prokaryotes: open reading frames
• ORF finding-problems in Eukaryotes

DETECTING GENES IN SEQUENCES OF DNA

Lecture 16 -The Hidden Markov Model for motif recognition SIMON

Markov chains for sequence recognition, intro to Hidden Markov Model HMMs for splice and gene finding
• Finite state nondeterministic automata (yet again)
• The Viterbi algorithm
• EM-the Baum Welch algorithm

---

GENOMICS - GENETIC DIVERSITY

MUTATION, HOMOLOGY,ANALOGY,PHYLOGENY

---




March 4, 2008

Lecture 17   Mutation SIMON

Mutation
• Mechanisms
• Types
• Lines,Sines, STRs and SNPs
• Forensic Genetics

Lecture 18 MEASURING EVOLUTIONARY TIME WITH A MOLECULAR CLOCK SIMON

Mutations to Clocks
• Stationary transition probabilities
• Jukes-Cantor model
• Kimura model

Lecture 19 - RECONSTRUCTING THE FAMILY TREE -PHYLOGENY SIMON

Phylogenetic searches
• About trees
• Character Based Phylogenies-Parsimony, Fitch's algorithm
• Distance Based Phylogenies- Unweighted Pair Group Method with Arithmetic Mean

March 11, 2008

Spring Break- No Class

---

GENOMICS - GENE EXPRESSION

REGULATION, EXPRESSION, LARGE DATA ARRAYS

---




March 18, 2008

Lecture 20 Introduction to Large Data Arrays:
Analysis of Gene Expression - Gene Arrays KREUGER

DATA REDUCTION AND ANALYTIC TECHNIQUES
• -fold test
• t-Test
• ANOVA
• Multivariate ANOVA

Lecture 21 Understanding your data SIMON

• Scale
• Outliers
• Noise
• Transformation

Lecture 22 Detecting and removing correlations and interdependence SIMON

Principal Component Analysis
Independent Component Analysis

March 25, 2008

Lecture 23 Clustering and Pattern Discovery SIMON

• Agglomeration vs Division
• Support Plane Vectors: Canonical Discriminant Analysis
• Other Pattern Analysis schemes: K-means (k-medioids)
• Neural Nets
• Self-organizing (Kohonen) maps

---

PROTEOMICS - PROTEINS, THE PRODUCT OF GENE EXPRESSION: PROTEINS IN EVOLUTION

SIMILARITY, HOMOLOGY,ANALOGY

---




April 1, 2008

Lecture 24 Protein Structure SIMON

Review of primary, secondary, tertiary and quaternary structure
• Sequence vis à vis structure
• Homology
• Analogy
• The importance of a motif in structure prediction

Lecture 25 Comparing Proteins SIMON

Lecture 26   BLAST SIMON

What BLAST does

How it works

Substitution matrices- continued
• Point Accepted Mutations
• Blocks and Prosite

Extreme Value Distribution and BLAST statistics

FOLDING AND STRUCTURE

April 8, 2008

Lecture 27 -Energetics of Protein Folds HOCH

Bioenergetics

Parameters in folding

Algorithms to estimate energy optimization

Lecture 28 Classification of Protein Folds Maciejewski

Lecture 29 Protein Structure Database Searching Maciejewski

DALI

April 15, 2008

April 22, 2008

Oral Presentations SIMON/Class