📗 -> 01/14/25: Bioinformatics Lecture 3
🎤 Vocab
❗ Unit and Larger Context
Small summary
✒️ -> Scratch Notes
Global Alignment
What is an alignment?
Alignment of x and y, resulting in 2 new sequences x’ and y’ such that |x’| = |y’| AND x’ contains either the characters in x as they appear in x OR ’_’.
x’ removed all ’_’ IS x
y’ removed all ’_’ IS y
AND x’[i] && y’[i] != ’_’ (not both spaces)
Global alignment is an alignment of x, y such that
is max for all possible alignments.
For all possible alignments, with sequences x and y, with lengths of x’ and y’ being n and m:
- Max length is n+rCr,
Maximal alignment is defined as the maximum of:
- Counting the last letter for both
- Counting n, but using a space for the last char in y
- Counting n, but using a space for the last char in x
OPT(n,m) returns the optimal/max alignment score for sequenceAND
- Counting n, but using a space for the last char in x
Ex)
OPT(0,2) for x=ata and y=aaa
- Returnsthe max alignment score for
AND - describing the alignment of x: ” and y: ‘aa’
- best alignment is x: ’__’ and y: ‘aa’
- = -2
DP Table for x=‘ata’ and y=‘aaa
| R | a | a | a | ||
|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | ||
| 0 | 0 | -1 | -2 | -3 | |
| a | 1 | -1 | 1 | 0 | -1 |
| t | 2 | -2 | 0 | 0 | -1 |
| a | 3 | -3 | -1 | 1 | 1 |
- Matrix R stores the OPT scores s.t. -
AND