Introduction to Bioinformatics

About This Course

This course provides an introduction to the field of bioinformatics, with a focus on important bioinformatic tools and resources.

Course Syllabus

  • Introduction to Computers and Biology
    • Introduction and Computational Successes
    • Quick Biology Introduction
  • Exact String Search
    • Z-Algorithm
    • Knuth-Morris-Pratt and Boyer-Moore
    • Seminumerical String Matching
  • Dynamic Programming & Sequence Alignment
    • Introduction to Dynamic Programming
    • More Dynamic Programming Examples: Subset Sum & Knapsack
    • Global Sequence Alignment
    • Local Sequence Alignment
    • General & Affine Gap Penalties
    • Multiple Sequence Alignment
    • Linear-space Sequence Alignment
      • Python code for local, global alignment & RNA folding
      • Local and Global Alignment Web Demo
  • Genome Sequencing & Assembly
    • DNA (Sanger) Sequencing & Lander-Waterman Statistics
    • Introduction to Graphs
    • Genome Assembly Paradigms
    • Comparing Whole Genomes with MUMmer
  • Data Structures for String Queries
    • Introduction to Trees
    • (Optimal) Binary Search Trees
    • Suffix Tries & Trees
    • Suffix Arrays (including Skew Algorithm)
    • Burrows-Wheeler Transform
  • Structural Biology
    • RNA Folding
    • Protein Folding
    • Linear Programming
    • Side-chain Positioning
  • Pattern Discovery
    • Motif Finding with Gibbs Sampling
    • Bacterial Gene Finding
    • Hidden Markov Models and Eukaryotic Gene Finding
    • Profile Hidden Markov Models
  • Phylogenetics
    • Phylogenetics
  • Clustering Biological Networks
    • Yeast 2-hybrid
    • Other Interaction Experiments
    • Function Prediction
    • Network Modularity
    • Clustering via Minimum Spanning Trees
    • Kernighan-Lin Graph Partitioning & Clustering via Distances
    • MCL and Other Graph Clustering (MCODE, RNSC)
  • Aligning Biological Networks
    • PathBLAST
    • Alignment via Color Coding
    • IsoRank
  • Random Models of Network Evolution
    • Models of Network Evolution
    • Attack vs. Failure Response
    • Network Motifs & Symmetry Breaking

Background

  • Basic Data Structures
    • Lists, Stacks, and Queues
    • AVL Trees
    • Splay Trees
    • B-Trees
    • Skip Lists
    • Heaps
  • Interval & Spatial Data Structures
    • Quad trees(PR, MX, Point)
    • kd-Trees
    • Searching in kd-Trees
    • Range Trees
    • Interval Trees
    • Finding Closest Pair of Points
  • Programing Languages
    • Python
    • R
  • Network Flow Algorihtm
    • Network Flows
    • Bipartite Matching
    • Edge-disjoint paths
    • Flows with Demands, etc.
    • Shortest paths with negative weights
  • The Theory of NP-Completeness
    • The P and NP Complexity Classes
    • NP-completeness
    • SAT, Coloring, TSP Problems
    • 3-dimensional Matching, Subset Sum Problems