Brute-force, Binary search, quicksort, binary trees, hashing, BWT

Dynamic programming, Fibonacci, Longest-increasing subsequencing, Edit Distance, Smith-Waterman, Dynamic Time Warp, BLAST

Graph representations, network motifs, modularity, breath-first-search, depth-first-search, eulerian path, traveling salesman, genome assembly, assembly validation.

Prokaryotic and Eukaryotic gene finding, Glimmer, GlimmerHMM, Forward algorithm, Viterbi, GHMM

Construct the BWT for a genome, and compute exact matches against it.

Details on BWT Construction and searching

Milestones in Molecular Biology and the rise of sequencing. Overview of computer systems, introduction to unix and scripting.

Introduction to Alignment and Algorithms, Suffix Arrays, Binary Search, QuickSort, Burrows-Wheeler Transform, Bowtie.

NCBI, UCSC, CSHL Meetings and Courses, Galaxy.

Background on tracking DNA replication with next-gen sequencing, Walk-through of analysis steps, Visualization of discovered replication sites.

Introduction to Matlab, working with variables and matrices, ploting, working with strings, working with structures, working with CEL arrays.

Introduction to Alignment and Algorithms, Suffix Arrays, Binary Search, QuickSort, Burrows-Wheeler Transform, Bowtie.

Theory and Practice of whole genome assembly and alignment highlighting the Celera Assembler.

Schedule of presentations and slides.

Theory and Practice of whole genome assembly and alignment highlighting Allpaths, SOAPdenovo, and the Celera Assembler.

Tutorial on using Allpaths for whole genome assembly

Data for challenge problem in the tutorial

In this class we explored the problem of finding exact occurrences of a query sequence in a large genome or database of sequences. Under this theme, we started by analyzing the brute force approach introducing the concepts of algorithm, complexity analysis, and E-values. Next we discussed suffix arrays as an index for accelerating the search, including analyzing the performance of binary search. We also considered two traditional algorithms for sorting (Selection Sort versus QuickSort) and their relative performance. In the second half of the class we discussed finding approximate occurrences of a short query sequence in a large genome or database of sequences. We first defined the problem by considering various metrics of an approximate occurrence such as hamming distance, or edit distance. We then considered different methods for computing inexact alignments including brute force global & local alignments, and seed-and-extend algorithms. Finally we discussed Bowtie as a Burrows-Wheeler transform based short read mapping algorithm for discovering alignments to reference genome.

In this session we reviewed the currently available sequencing technologies and best practices, focusing on the widely used Illumina sequencing platform, the up and coming PacBio sequencing platform, and the recently announced Oxford Nanopore instruments. Special attention was placed on the complexities and biases with Illumina.

The theme of this class was graphs and methods for graph analysis. The emphasis was on genome assembly but included a discussion of other biological networks including PPI networks, regulation networks, neuron interaction networks, and cell cycle graphs. In the class, we considered fundamental properties of graphs, such as nodes, edges, degrees, and shortest paths. We then examined in detail algorithms for searching graphs with a with breadth-first-search, and then approaches for finding minimum cost paths through weighed graphs (traveling salesman problem), including exhaustive search, greedy algorithms, and branch-and-bound. This lead to a discussion of the intractable nature of NP-complete problems, and reviewed several important examples (vertex cover, clique finding, knapsack problem, Hamiltonian cycle).