Summary

Alignment

Longest common subsequence

Edit Distance

Global Alignment

Local Alignment

Heuristic Alignment

// TODO: ROC graph!

Multiple Alignment

// TODO!

Progressive Multiple Alignment

// TODO!

Space efficient alignment

Sub-quadratic alignment

Substring Indexes

Keyword Trees

Suffix Trees

// TODO: Optimizations in Ukkonen's algorithm

Suffix Tree Applications

// TODO: Matching Statistics.

Common substrings

Matching patterns against text

Matching suffixes and prefixes

Sequencing and assembly

Sequencing by hybridization (SBH)

Motif Discovery

Position Weight Matrix (PWM)

Motif-discovery – exact methods

Motif-discovery – randomized methods

Hidden Markov Models (HMM)

Calculate the joint probability $P ( Q \& O )$ for a path $Q$ and a sequence $O$.

$$P( Q \& O ) = P ( Q | O ) \cdot P( O )$$

Viterbi Algorithm: Find the most probable state path given the observed sequence

Total time: O(TN^2) Space: O(TN)

Find the probability of a symbol sequence

Estimate/learn parameters

Baum-Welch estimation

RNA Secondary Structure Prediction

// TODO!