BMCI 2006

The DIMACS Bio-Math Connect Institute

Rutgers University
July 16 - July 28, 2006


Outline of Topics to be Covered
Description of Helpful Mathematical Background Material
Math Pre-Program, Biology Pre-Program

 


Outline of Topics to be Covered

Week 1
Monday
Parallel Sessions
Math Background - 2 hours
Intro. to vertex-edge graphs
   - Directed and undirected graphs
   - Directed acyclic graphs

Dijkstra's algorithm on DAGs
A 2-regular graph is the union of disjoint cycles

Biology Background - 2 hours
Genes as sequences of nucleotides
Theory of evolution
   - mutation and selection
   - the neutral theory of evolution
   - similar genes appear across species
   - orthology and homology
DNA, Genomes, genes, introns and exons
Purines and pyrimidines

Parallel Sessions
Math Background - 1 hour
Counting
   - multiplication rule
   - number of ACGT strings of length n

Elementary probability
   - equally-likely outcomes
   - multiplication rule
   - complement probability

Biology Background - 1 hour
Amino acids and proteins
The genetic code
Transcription and Translation

Plenary Session #1
Computational BioMath - 1.25 hour
Rephrase Dijkstra's algorithm in terms of dynamic programming
   - what smaller solutions would help?
   - keeping track of smaller solutions

Global alignment
   - really a "shortest path" problem
   - use matrices to memoize solutions
   - read off of our dyn. prog. matrices
Tuesday
Parallel Sessions
Math Background - 1 hour
Trees
   - (connected, n-1 edges, no cycles)
   - binary, rooted and unrooted

Matrix Multiplication

Biology Background - 1 hour
Phylogenies
   - some examples and pictures
   - species vs. gene phylogeny

Various types of mutations
   - point substitutions
   - deletions and insertions
   - replication
   - rearrangement

Synonymous versus non-synonymous substitutions
Plenary Session #2
Computational BioMath - 1 hour
Variation
   - modify so that end gaps "don't count"

Local alignments
   - cutting our losses
Plenary Session #3
Computational BioMath - 1.25 hours
How BLAST works
   - searching for a 'seed'
   - algorithm for protein sequences
   - description of PAM matrices

PAM matrices
   - derivation of 'M' matrices
   - PAM matrices from 'M' matrices
Wednesday
Plenary Session #4
Computational BioMath - 1.5 hours
Introduction to parsimony
   - general idea in various contexts
   - specifically for trees

Given a tree and one base at each leaf
   - Fitch's algorithm for reconstruction

Generalize to longer (aligned) sequences

Suffix Trees
   - use
   - construction (intuitive method)

Week 1 Continued
Thursday
Plenary Session #5
Computational BioMath - 1.5 hours
Distance-based Phylogeny Reconstruction
   - definition(s) of distance
   - UPGMA

Neighbor joining method of Saitou and Nei
Friday
Plenary Session #6
Computational BioMath - 1.5 hours
Introduction to Phylogenetic Footprinting
    - footprinting by global alignment
    - Blanchette's FootPrinter algorithm

Week 2
Monday
Plenary Session #7
Computational BioMath - 1.5 hours

Genome rearrangement
   - some examples
   - sorting by reversals

Algorithm for oriented case
   - breakpoints
   - reality and desire diagram
   - cycles in the R&D diagram
   - components
   - hurdles
   - superhurdles and fortresses
   - summary of algorithm







Description of Helpful Mathematical Background Material
Combinatorics and Probability
 Graph Theory
 Mathematics
 Other
Counting Principles
   - multiplication (product) rule

Basics of probability
   - outcomes and events
   - equally likely outcomes
   - multiplication (product) rule
 What is a graph
   - vertices (nodes)
   - edges (arcs)

Regular graphs
   - in particular, 2-regular

Edge-weighted graphs

Trees
   - leaves
   - binary trees
   - rooted vs. unrooted
 Logarithms
   - logs base 2 and 10
   - facility with computations
   - log rules
       - log(ab) = log a + log b
       - log(ar) = r log a

Matrices
   - matrix multiplication
 

 Strings over an alphabet
   - substrings
   - superstrings
   - enumeration of strings