The scoring rule decides the best alignment
A scoring rule gives a reward for a match and a penalty for a mismatch or a gap. Change the rule and the best alignment can change with it.
You will see how a gap penalty changes a score. You will also see how local alignment finds the best matching region instead of lining up the whole length.
By the end of this lesson
Note
I can change the scoring rule and say how it changes the alignment score.
Key words
| Word | What it means |
|---|---|
| Gap penalty | the score taken away for each gap |
| Scoring rule | the match, mismatch and gap numbers used together |
| Global alignment | an alignment of the whole of both sequences |
| Local alignment | the best matching region of two sequences |
| Region | a stretch of letters inside a longer sequence |
The cells students fill in are left blank in this preview.
A bigger gap penalty makes gaps rarer
The gap penalty is the score taken away for each gap. When it is small, the best alignment uses gaps freely to line letters up. When it is large, gaps become too expensive and the alignment avoids them.
The same two sequences can therefore have very different scores under different rules.
Worked example: ACGT against AGT under three rules
| Match | Mismatch | Gap | Best score |
|---|---|---|---|
| +1 | -1 | -1 | 2 |
| +2 | -1 | -2 | 4 |
| +1 | -1 | -4 | -1 |
The cells students fill in are left blank in this preview.
Change the gap penalty and watch the score
def global_score(a, b, match, mismatch, gap):
table = []
for i in range(len(a) + 1):
table.append([0] * (len(b) + 1))
for i in range(1, len(a) + 1):
table[i][0] = i * gap
for j in range(1, len(b) + 1):
table[0][j] = j * gap
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
diagonal = table[i - 1][j - 1] + match
else:
diagonal = table[i - 1][j - 1] + mismatch
table[i][j] = max(diagonal, table[i - 1][j] + gap, table[i][j - 1] + gap)
return table[len(a)][len(b)]
for gap in [-1, -2, -4]:
print("gap", gap, "score", global_score("ACGT", "AGT", 1, -1, gap))
# Try gap -10. Does the score keep falling?
Local alignment keeps only the best region
A global alignment scores the whole of both sequences, even the ends that do not match. A local alignment looks for the best matching region and ignores the rest.
The rule is small. A cell never falls below 0, so a bad start is dropped. The answer is the highest cell anywhere in the table, not the bottom right.
Worked example: one pair, global and local
| Pair | Rule | Global score | Local score |
|---|---|---|---|
| TTACGTAGG and CCACGTACC | +2, -1, -2 | 6 | 10 |
| ACGT and ACGT | +2, -1, -2 | 8 | 8 |
| AAAA and TTTT | +2, -1, -2 | -4 | 0 |
The cells students fill in are left blank in this preview.
Find the best local score
def local_score(a, b, match, mismatch, gap):
table = []
for i in range(len(a) + 1):
table.append([0] * (len(b) + 1))
best = 0
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
diagonal = table[i - 1][j - 1] + match
else:
diagonal = table[i - 1][j - 1] + mismatch
cell = max(0, diagonal, table[i - 1][j] + gap, table[i][j - 1] + gap)
table[i][j] = cell
if cell > best:
best = cell
return best
print(local_score("TTACGTAGG", "CCACGTACC", 2, -1, -2))
# Try two sequences with nothing in common, such as "AAAA" and "TTTT".
Count the matching columns of the two sequences
docker exec jupyter python3 -c "print(sum(a == b for a, b in zip('TTACGTAGG', 'CCACGTACC')))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
The command finds the shared region
The two sequences have nine letters each. They match in five columns, and those five sit side by side in the shared region ACGTA.
Five matches at +2 each is 10, which is the local score. The ends do not match, which is why the global score is lower.
A common mistake
Warning
Many people think a local alignment is a better alignment than a global one. Neither is better. A global alignment asks how alike the whole sequences are. A local alignment asks whether any region of them is alike. Choose the one that fits the question.