# Significance of Alignments

1. Sequence alignment
   - Inputs:
     - Explicit—Two sequences {a1, a2, ...., am} and {b1, b2, ...., bn} (e.g. query and database)
     - Implicit—A scoring procedure, e.g. pairwise scores s(ai,bj) and gap costs
   - Alignment algorithm: global, local, gapped, gapless (dynamic programming, applet)
   - Output: matching (sub)sequences with an overall score S . (example)
   - Significance: What is the probability of getting a score S by chance?
2. Statistics of gapless local alignments:
   - Random walks of scores as a function of matching length
   - Extreme Value Distributions, the Gumbel distribution
   - Tails of distribution in a gapless alignment
   - The Karlin-Dembo formula
3. Gapped alignments and Statistical Physics
   - Transfer Matrix method for Directed Paths in Random Media (PDF)
   - Dynamic Programming method for Sequence Alignment (Example)

- Tutorial by Ralf Bundschuh on Sequence Alignment (and associated paper)

(Detailed Lecture Notes (PDF))