How Do We Compare Biological Sequences

• From Sequence Comparison to Biological Insights

• The Alignment Game and the Longest Common Subsequence
• The Chandigarh Gedi Problem
How Do We Compare Biological Sequences? • The Change Problem
Dynamic Programming and • Dynamic Programming and Backtracking Pointers
Divide-and Conquer Algorithms • From Chandigarh Gedi route to the Alignment Graph
• From Global to Local Alignment
• Penalizing Insertions and Deletions in Sequence Alignment

Phillip Compeau and Pavel Pevzner.

Bioinformatics Algorithms: An Active Learning Approach
Bioinformatics Algorithms: An Active Learning Approach.
©2018 by Compeau and Pevzner. All rights reserved. Copyright 2018 Compeau and Pevzner.

What are Antibiotics, Anyway? Antibiotics on the Molecular Level

Antibiotic 🡨 “a substance that kills bacteria” We will study Tyrocidine B1, an antibiotic produced by
Bacillus Brevis

Occur naturally because of Tyrocidine B1 is a “mini-protein” called a peptide: short

millions of years of string of amino acids
evolutionary warfare Valine Leucine Proline Phenylalanine Glutamine
Val-Lys-Leu-Phe-Pro-Trp-Phe-Asn-Gln-Tyr
Produced by fungi (e.g., V K L F P W F N Q Y
Lysine Phenylalanine Tryptophan Asparagine Tyrosine
molds) and bacteria
Bioinformatics Algorithms: An Active Learning Approach. Courtesy: Bios (Wikimedia) Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 Dodging the Dogma Dodging the Dogma

Transcription Translation Transcription Translation

DNA RNA Polymerase
RNA Ribosome
Protein DNA RNA Polymerase
RNA Ribosome
Protein

1963: Edward Tatum inhibits

1963: Edward Tatum inhibits the ribosome in Bacillus brevis.
the ribosome in Bacillus brevis.
Production of some peptides,
including tyrocidines, continues!

Bioinformatics Algorithms: An Active Learning Approach. Edward Tatum Bioinformatics Algorithms: An Active Learning Approach. Edward Tatum
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

Dodging the Dogma NRP Synthetase Adds One Amino Acid at a Time

Transcription Translation
DNA RNA Polymerase
RNA Ribosome
Protein

1969: Lipmann shows tyrocidines

are non-ribosomal peptides
(NRPs).

NRPs are synthesized not by the

ribosome but by NRP synthetase.
Bioinformatics Algorithms: An Active Learning Approach. Fritz Lipmann Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 These Three A-domains Do Not Look Similar These Three A-domains Do Not Look Similar

Same function = same sequence ? Same function = same sequence ?

YAFDLGYTCMFPVLLGGGELHIVQKETYTAPDEIAHYIKEHGITYIKLTPSLFHTIVNTASFAFDANFESLRLIVLGGEKIIPIDVIAFRKMYGHTEFINHYGPTEATIGA YAFDLGYTCMFPV LLGGGELHIVQKETYTAPDEIAHYI KEHGITYIKLTPSLFHTIVNTASFAFDANFESLRLIVLGGEKIIPIDVIAFRKMYGHTEFINHYGPTEATIGA

AFDVSAGDFARALLTGGQLIVCPNEVKMDPASLYAIIKKYDITIFEATPALVIPLMEYIYEQKLDISQLQILIVGSDSCSMEDFKTLVSRFGSTIRIVNSYGVTEACIDS AFDVSAGDFARAL LTGGQLIVCPNEVKMDPASLYAIIK KYDITIFEATPALVIPLMEYIYEQKLDISQLQILIVGSDSCSMEDFKTLVSRFGSTIRIVNSYGVTEACIDS

IAFDASSWEIYAPLLNGGTVVCIDYYTTIDIKALEAVFKQHHIRGAMLPPALLKQCLVSAPTMISSLEILFAAGDRLSSQDAILARRAVGSGVYNAYGPTENTVLS IAFDASSWEIYAP LLNGGTVVCIDYYTTIDIKALEAVF KQHHIRGAMLPPALLKQCLVSAPTMISSLEILFAAGDRLSSQDAILARRAVGSGVYNAYGPTENTVLS

just 3 conservative columns

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

Do they look similar now? And now?

Same function = same sequence ? Same function = same sequence ?

YAFDLGYTCMFPV LLGGGELHIVQKETYTAPDEIAHYI KEHGITYIKLTPSLFHTIVNTASFAFDANFESLRLIVLGGEKIIPIDVIAFRKMYGHTEFINHYGPTEATIGA YAFDLGYTCMFPV LLGGGELHIVQKETYTAPDEIAHYI KEHGITYIKLTPSLFHTIVNTASFAFDANFES LRLIVLGGEKIIPI DVIAFRKMY GHTE-FINHYGPTEATIGA

-AFDVSAGDFARA LLTGGQLIVCPNEVKMDPASLYAII KKYDITIFEATPALVIPLMEYIYEQKLDISQLQILIVGSDSCSMEDFKTLVSRFGSTIRIVNSYGVTEACIDS -AFDVSAGDFARA LLTGGQLIVCPNEVKMDPASLYAII KKYDITIFEATPALVIPLMEYI -YEQKLDISQ LQILIVGSDSCSME DFKTLVSRF GSTIRIVNSYGVTEACIDS

IAFDASSWEIYAP LLNGGTVVCIDYYTTIDIKALEAVF KQHHIRGAMLPPALLKQCLVSAPTMISSLEILFAAGDRLSSQDAILARRAVGSGVYNAYGPTENTVLS IAFDASSWEIYAP LLNGGTVVCIDYYTTIDIKALEAVF KQHHIRGAMLPPALLKQCLVSA ----PTMISSLEILFAAGDRLSSQ DAILARRAV GSGV-Y-NAYGPTENTVLS

11 conservative columns 19 conservative columns!

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 Red Positions Encode Conservative Core of A-domains
Blue Positions in A-domains Define Non-Ribosomal Code

Each module adds a different Aa

YAFDLGYTCMFPV LLGGGELHIVQKETYTAPDEIAHYI KEHGITYIKLTPSLFHTIVNTASFAFDANFES LRLIVLGGEKIIPI DVIAFRKMY GHTE-FINHYGPTEATIGA YAFDLGYTCMFPVLLGGGELHIVQKETYTAPDEIAHYI KEHGITYIKLTPSLFHTIVNTASFAFDANFES LRLIVLGGEKIIPI DVIAFRKMY GHTE-FINHYGPTEATIGA

-AFDVSAGDFARA LLTGGQLIVCPNEVKMDPASLYAII KKYDITIFEATPALVIPLMEYI -YEQKLDISQ LQILIVGSDSCSME DFKTLVSRF GSTIRIVNSYGVTEACIDS -AFDVSAGDFARALLTGGQLIVCPNEVKMDPASLYAII KKYDITIFEATPALVIPLMEYI -YEQKLDISQ LQILIVGSDSCSME DFKTLVSRF GSTIRIVNSYGVTEACIDS

IAFDASSWEIYAP LLNGGTVVCIDYYTTIDIKALEAVF KQHHIRGAMLPPALLKQCLVSA ----PTMISSLEILFAAGDRLSSQ DAILARRAV GSGV-Y-NAYGPTENTVLS IAFDASSWEIYAPLLNGGTVVCIDYYTTIDIKALEAVF KQHHIRGAMLPPALLKQCLVSA ----PTMISSLEILFAAGDRLSSQ DAILARRAV GSGV-Y-NAYGPTENTVLS

Which positions are responsible for encoding different amino acids Asp, Orn, Val? LTKVGHIG Asp
VGEIGSID Orn
AWMFAAVL Val

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

Recap: Identifying the problem Sequence Alignment

To simplify matters, we will compare only two sequences at a time, returning to
multiple sequence comparison.
Returning to the A-domain example (reproduced below),
Hamming distance, which counts mismatches in two strings, rigidly assumes
It is completely unclear that we align the i-th symbol of one sequence against the i-th symbol of the
what algorithm we have used to decide where to insert the spaces, other.
or
how we should quantify the “best” alignment of the three sequences. Since biological sequences are subject to insertions and deletions, it is
often the case that the i-th symbol of one sequence corresponds to a
symbol at a completely different position in the other sequence. The goal,
then, is to find the most appropriate correspondence of symbols.
How Do We Compare Biological Sequences The Alignment Game
• From Sequence Comparison to Biological Insights
• The Alignment Game and the Longest Common Subsequence
• The Chandigarh Gedi Problem A T G T T A T A
• The Change Problem A T C G T C C
• Dynamic Programming and Backtracking Pointers
Alignment Game (maximizing the number of points):
• From Chandigarh Gedi route to the Alignment Graph
• From Global to Local Alignment You can think about maximizing the number of matched symbols in two strings
as a single-person game. At each turn, you have two choices. You can remove
• Penalizing Insertions and Deletions in Sequence Alignment the first symbol from each sequence, in which case you earn a point if the
symbols match; alternatively, you can remove the first symbol from either of the
two sequences, in which case you earn no points but may set yourself up to
earn more points in later moves. Your goal is to maximize the number of points.

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

The Alignment Game The Alignment Game

A T G T T A T A A T G T T A T A
A T C G T C C A T C G T C C
+1 +1+1

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 The Alignment Game The Alignment Game

A T - G T T A T A A T - G T T A T A
A T C G T C C A T C G T C C
+1+1 +1+1 +1

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

The Alignment Game The Alignment Game

A T - G T T A T A A T - G T T A T A
A T C G T C C A T C G T - C C
+1+1 +1+1 +1+1 +1+1

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 The Alignment Game The Alignment Game

A T - G T T A T A A T - G T T A T A
A T C G T - C C A T C G T - C - C
+1+1 +1+1 +1+1 +1+1

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

The Alignment Game What Is the Sequence Alignment?

matches insertions deletions mismatches

A T - G T T A T A A T - G T T A T A
A T C G T - C - C A T C G T - C - C
+1+1 +1+1 =4 +1+1 +1+1 =4

Alignment of two sequences is a two-row matrix:

1st row: symbols of the 1st sequence (in order) interspersed by “-”
2nd row: symbols of the 2nd sequence (in order) interspersed by “-”

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 Longest Common Subsequence How Do We Compare Biological Sequences
• From Sequence Comparison to Biological Insights
• The Alignment Game and the Longest Common Subsequence
A T - G T T A T A • The Chandigarh Gedi route Problem
A T C G T - C - C • The Change Problem
Matches in alignment of two sequences (ATGT) form their • Dynamic Programming and Backtracking Pointers
Common Subsequence • From Chandigarh gedi route to the Alignment Graph
Longest Common Subsequence Problem: Find a longest • From Global to Local Alignment
common subsequence of two strings. • Penalizing Insertions and Deletions in Sequence Alignment
• Input: Two strings.
• Output: A longest common subsequence of these
strings.
Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

Insights from the Most Boring City in India From Chandigarh to a Grid Graph

Walk from the

source to the
sink (only in the
South ↓ and East
→ directions)
and visit the
maximum
number of
attractions
 The Chandigarh “Gedi” route Problem 0
3
3
2 4 0

1 0 2 4 3
3 2 4 2
Chandigarh Gedi Problem: Find a longest path in a
rectangular city grid. 3 6 5 2 1
•Input: A weighted rectangular grid. Greedy 0 7 3 3
algorithm?
•Output: A longest path from the source to the sink in
the grid. 4 4 5 2 1
3 3 0 2

5 6 8 5 3
1 3 2 2

0
3 2 4 0 Search for Longest Paths in a Directed Graph
3 5 9
1 0 2 4 3
3 2 4 2
13
Longest Path in a Directed Graph Problem: Find a
3 6 5 2 1 longest path between two nodes in an edge-weighted
Greedy 0 7 3 3 directed graph.
algorithm? 15 19 • Input: An edge-weighted directed graph with
4 4 5 2 1 source and sink nodes.
3 3 0 2
• Output: A longest path from source to sink in
20 the directed graph.
5 6 8 5 3
1 3 2 2
23
Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner.
 Do You See a Connection between A T C G T C C
the “Chandigarh Gedi route” and the Alignment Game? A
?
alignment → path T
A T - G T T A T A
A T - G T T A T A A T C G T - C - C
G
A T C G T - C - C ↘ ↘ → ↘ ↘ ↓ ↘ ↓ ↘
↘ ↘ → ↘ ↘ ↓ ↘ ↓ ↘ T
T
A
T

Bioinformatics Algorithms: An Active Learning Approach.

A
Copyright 2018 Compeau and Pevzner.

A T C G T C C A T C G T C C
A A
? ?
alignment → path T path → alignment T
A T - G T T A T A A T G T T - A T A
A T C G T - C - C
G - - A T C G T C C
G
↘ ↘ → ↘ ↘ ↓ ↘ ↓ ↘ ↓ ↓ ↘ ↘ ↘ → ↘ ↘ ↘
T T
highest-scoring
T alignment T
=
A longest path in a A
Chandigarh gedi
T T
route
A A
 A T C G T C C How Do We Compare Biological Sequences
How to build a A
“Chandigarh gedi • From Sequence Comparison to Biological Insights
route” for the T • The Alignment Game and the Longest Common Subsequence
Alignment Game • The Chandigarh Gedi Tourist Problem
and the G
• The Change Problem
Longest Common
Subsequence T • Dynamic Programming and Backtracking Pointers
Problem? • From Chandigarh Gedi route to the Alignment Graph
T
Diagonal red edges • From Global to Local Alignment
correspond to A • Penalizing Insertions and Deletions in Sequence Alignment
matching symbols
and have scores 1 T
A Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner.

The Change Problem Changing Money in a Greedy Way

Change Problem: Find the minimum number of coins
needed to make change. GreedyChange(money)
change ← empty collection of coins
•Input: An integer money and an array of positive
while money > 0
integers (coin1, . . . , coind). coin ← largest denomination that does not exceed money
•Output: The minimum number of coins with add coin to change
denominations (coin1, . . . , coind) that changes money. money ← money – coin
return change

Bioinformatics Algorithms: An Active Learning Approach.

Copyright 2018 Compeau and Pevzner.
 Changing Money in Supermarket Changing Money in Supermarket: GreedyChange Fails

40 Rs = 25+10+5 Toffees 40 Rs = 25+10+5 = 20+20

Greedy Greedy is not Optimal

Recursive Change Recursive Change

Given the denominations 6, 5, and 1, what is the minimum Given the denominations 6, 5, and 1, what is the minimum
number of coins needed to change 9 Rs? number of coins needed to change 9 Rs?
money 1 2 3 4 5 6 7 8 9 10 11 12 money 1 2 3 4 5 6 7 8 9 10 11 12
MinNumCoins ? MinNumCoins ? ? ? ?

MinNumCoins(9)= ? MinNumCoins(9)= ?

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 Recursive Change Recursive Change
Given the denominations 6, 5, and 1, what is the minimum Given the denominations 6, 5, and 1, what is the minimum
number of coins needed to change 9 Rs? number of coins needed to change 9 cents?
money 1 2 3 4 5 6 7 8 9 10 11 12 money 1 2 3 4 5 6 7 8 9 10 11 12
MinNumCoins ? ? ? ? MinNumCoins ? ? ? ?

MinNumCoins(3)=
MinNumCoins(9-6)+1 = MinNumCoins(3)+1
MinNumCoins(4)=
MinNumCoins(8)=
?
MinNumCoins(9)= min{ MinNumCoins(9-5)+1 = MinNumCoins(4)+1
MinNumCoins(9-1)+1 = MinNumCoins(8)+1

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

Recursive Change RecursiveChange

Given the denominations 6, 5, and 1, what is the minimum RecursiveChange(money, coins)
number of coins needed to change 9 cents? if money = 0
return 0
money 1 2 3 4 5 6 7 8 9 10 11 12 MinNumCoins 🡨 infinity
MinNumCoins ? ? ? ? ? ? for i 🡨 1 to |coins|
if money ≥ coini
NumCoins 🡨
MinNumCoins(3)= RecursiveChange(money-coini, coins)
MinNumCoins(4)=
MinNumCoins(8)=
? if numCoins + 1 < MinNumCoins
MinNumCoins 🡨 numCoins + 1
return MinNumCoins

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
Changing Money by Dynamic Programming Changing Money by Dynamic Programming
Hint. Wouldn’t it be nice to know all the values of Given the denominations 6, 5, and 1, what is the minimum
number of coins needed to change 9 cents?
MinNumCoins(money – coini)
money 0 1 2 3 4 5 6 7 8 9 10 11 12
by the time we need to compute
MinNumCoins 0 1 2 3 4 1 1 2 3 ?
MinNumCoins(money)?
Richard
Instead of the time-consuming calls: Bellman

RecursiveChange(money-coini, Coins, d)
we would simply look up the values of
MinNumCoins(money - coini)

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

“Programming” in “Dynamic Programming”

DPChange
Has Nothing to Do with Programming!
Richard Bellman developed this idea in 1950s working on an
DPChange(money, coins) Air Force project.
MinNumCoins(0) 🡨 0
for m 🡨 1 to money At that time, his approach seemed completely impractical.
MinNumCoins(m) 🡨 infinity
for i 🡨 1 to |coins| He wanted to hide that he is really doing math from the
if m ≥ coini Secretary of Defense. Richard
Bellman
if MinNumCoins(m – coini) + 1 < MinNumCoins(m)
“…What name could I choose? I was interested in planning but planning, is not a
MinNumCoins(m) 🡨 MinNumCoins(m – coini)+ 1 good word for various reasons. I decided therefore to use the word,
return MinNumCoins(money) “programming” and I wanted to get across the idea that this was dynamic. It
was something not even a Congressman could object to. So I used it as an
umbrella for my activities.”

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 How Do We Compare Biological Sequences 3 4
2 0
• From Sequence Comparison to Biological Insights
There are 1 0 2 4 3
• The Alignment Game and the Longest Common Subsequence only 2 ways
3 2 4 2
• The Chandigarh Gedi Tourist Problem to arrive to
• The Change Problem the sink:
by moving 3 6 5 2 1
• Dynamic Programming and Backtracking Pointers South ↓ 0 7 3 3
• From Chandigarh Gedi route to the Alignment Graph or by moving
East → 4 4 5 2 1
• From Global to Local Alignment
• Penalizing Insertions and Deletions in Sequence Alignment 3 3 0 2

5 6 8 5 3
South
1 3 2 2
or
Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner. East?

South or East? 0
3 2 4 0

1 0 2 4 3
SouthOrEast(n,m)
if n=0 and m=0 3 2 4 2
1
return 0
4 6 5 2 1
if n>0 and m>0
0 7 3 3
x 🡨 SouthOrEast(n-1,m)+weight of edge “↓”into (n,m) 5
y 🡨 SouthOrEast(n,m-1)+ weight of edge “→”into (n,m) 4 4 5 2 1
return max{x,y} 3 3 0 2
return -infinity
5 6 8 5 3
1 3 2 2
Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 3 2 4 0 3 2 4 0
0 3 5 9 9 0 3 5 9 9
South
1 0 2 4 3 or 1 0 2 4 3
3 2 4 2 East? 3 2 4 2
1 1 4
1+3 > 3+0
4 6 5 2 1 4 6 5 2 1
0 7 3 3 0 7 3 3
5 5
4 4 5 2 1 4 4 5 2 1
3 3 0 2 3 3 0 2
9 9
5 6 8 5 3 5 6 8 5 3
1 3 2 2 1 3 2 2
14 14
Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

3 2 4 0 3 2 4 0
0 3 5 9 9 0 3 5 9 9
We arrived South
to (1,1) 1 0 2 4 3 or 1 0 2 4 3
by the bold
3 2 4 2 East? 3 2 4 2
edge: 1 4 1 4
5+0 < 4+6
3 4 6 5 2 1 4 6 5 2 1
4
0 7 3 3 0 7 3 3
5 5 10
4 4 5 2 1 4 4 5 2 1
3 3 0 2 3 3 0 2
9 9
5 6 8 5 3 5 6 8 5 3
1 3 2 2 1 3 2 2
14 14
Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 3 2 4 0 3 2 4 0
0 3 5 9 9 0 3 5 9 9
We arrived
to (2,1) 1 0 2 4 3 1 0 2 4 3
by the bold
3 2 4 2 3 2 4 2
edge: 1 4 1 4
4 6 5 2 1 4 6 5 2 1
6
0 7 3 3 0 7 3 3
5 10 5 10
10
4 4 5 2 1 4 4 5 2 1
3 3 0 2 3 3 0 2
9 9 14
5 6 8 5 3 5 6 8 5 3
1 3 2 2 1 3 2 2
14 14 20
Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

3 2 4 0 3 2 4 0
0 3 5 9 9 0 3 5 9 9
South South
or 1 0 2 4 3 or 1 0 2 4 3
East? 3 2 4 2 East? 3 2 4 2
1 4 7 1 4 7
5+2 > 4+2 5+2 > 4+2
4 6 5 2 1 4 6 5 2 1
0 7 3 3 0 7 3 3
5 10 5 10
4 4 5 2 1 4 4 5 2 1
3 3 0 2 3 3 0 2
9 14 9 14
5 6 8 5 3 5 6 8 5 3
1 3 2 2 1 3 2 2
14 20 14 20
Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 3 2 4 0 3 2 4 0
0 3 5 9 9 0 3 5 9 9
1 0 2 4 3 1 2 4
Backtracking
3 2 4 2 pointers: 3 2
1 4 7 13 15 1 4 7 13 15
the best way
4 6 5 2 1 to get to 4 6
each node
0 7 3 3 7 3 3
5 10 17 20 24 5 10 17 20 24

4 4 5 2 1 4 4 5 2 1
3 3 0 2
9 14 22 22 25 9 14 22 22 25
5 6 8 5 3 5 6 8
1 3 2 2 2 2
14 20 30 32 34 14 20 30 32 34
Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

Dynamic Programming Recurrence

How Do We Compare Biological Sequences
• From Sequence Comparison to Biological Insights
• The Alignment Game and the Longest Common Subsequence
si, j: the length of a longest path from (0,0) to (i,j)
• The Chandigarh Gedi route Problem
• The Change Problem
si-1, j + weight of edge “↓”into (i,j) • Dynamic Programming and Backtracking Pointers
si, j = max {
si, j-1 + weight of edge “→”into (i,j) • From Chandigarh Gedi route to the Alignment Graph
• From Global to Local Alignment
• Penalizing Insertions and Deletions in Sequence Alignment

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 Dynamic Programming Recurrence for the Dynamic Programming Recurrence for the
Alignment Graph Longest Common Subsequence Problem
si, j: the length of a longest path from (0,0) to (i,j) si, j: the length of a longest path from (0,0) to (i,j)

si-1, j + weight of edge “↓” into (i,j) si-1, j + 0

si, j= max { si, j-1 + weight of edge “→” into (i,j)
si-1, j-1+ weight of edge “↘” into (i,j)
si, j= max { si, j-1 + 0
si-1, j-1+ 1, if vi=wj

red edges ↘ – weight 1 red edges ↘ – weight 1

other edges – weight 0 other edges – weight 0

A T C G T C C A T C G T C C
A A
backtracking pointers backtracking pointers
for the Longest for the Longest
Common Subsequence
T Common Subsequence
T

red edges ↘ – weight 1 G G

other edges – weight 0
T T
T T
A A
T T
A A
 Computing Backtracking Pointers 0
3
3
2
5
4
9
0
9
Why did we
store the 1 2 4
si,j-1+0 backtracking 3 2
si,j ← max{ si-1,j+0 pointers? 1 4 7 13 15
si-1,j-1+1, if vi=wj 4 6
7 3 3
5 10 17 20 24
“→”, if si,j=si,j-1
backtracki,j ← {“↓", if si,j=si-1,j 4 4 5 2 1
“↘”, if si,j=si-1,j-1+1 9 14 22 22 25
5 6 8
2 2
14 20 30 32 34
Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner.

A T C G T C C
3 2 4 0
0 3 5 9 9 A
What is the backtracking pointers
1 2 4 for the Longest
optimal T
Common Subsequence
alignment 1 3 4 7 13
2
15
path? G
4 6
7 3 3 T
5 10 17 20 24

4 4 5 2 1
T

9 14 22 22 25 A
5 6 8 T
2 2
14 20 30 32 34 A
LCSBACKTRACK(V, W)
for i0 to v

Si00
for j0 to [w
So.j0
for i 1 to

for j1 to w

Si-1,j
si - max Si,j-1
Si-1,j-1+1, if v; = wj
We now need to find a path from the source to the sink formed by the
if Si,j = Si-1.1 highlighted edges. The algorithm above solves the Longest Common
Backtracki,"" Subsequence Problem by using the information in Backtrack.
else if Si.j = Si,j-1
Backtracki,"" OUTPUTLCS(Backtrack, v, i, j) outputs an LCS between the i-prefix of v and
the j-prefix of w. The initial invocation that outputs an LCS of v and w is
else if Si,jSj-1,j-1+ 1
= and v; = Wj OUTPUTLCS(Backtrack, v, |v|, |w|)
Backtracki,j""
return Backtrack

How Do We Compare Biological Sequences

What is wrong with LCS scoring?
• From Sequence Comparison to Biological Insights
• The Alignment Game and the Longest Common Subsequence
• The Chandigarh Gedi route Problem
• The Change Problem
• Dynamic Programming and Backtracking Pointers
• From Chandigarh Gedi route to the Alignment Graph
• From Global to Local Alignment
• Penalizing Insertions and Deletions in Sequence Alignment
• Space-Efficient Sequence Alignment
• Multiple Sequence Alignment

Bioinformatics Algorithms: An Active Learning Approach.

Copyright 2018 Compeau and Pevzner.
Below, we highlight the purple amino acids representing the non-ribosomal signatures.
Although these signatures are grouped in eight conserved columns in Marahiel's align-
Current (Primitive) Scoring
ment from the beginning of the chapter, only five of these columns have "survived" in
the LCS alignment above, making it impossible to infer the non-ribosomal signatures: #matches
YAFDL--G-YTCMFP--VLL-GGGELHIV---Q-K-E--T-YTAPDEIAHYIK--EHGITYI---KLTPSL-FHT
-AFDVSAGD----FARA-LLTGG-QL-IVCPNEVKMDPASLY-A---I---IKKYD--IT-IFEA--TPALV---

IVNTASFAFDANFE-----S-LR-LIVLGG-----EKIIPIDVIAFRK-M---YGHTEFI---NHYGPTEATIGA
IPLMEYIY-----EQKLDISQLQILIV-GSDSCSME-----D---F-KTLVSRFGST--IRIVNSYGVTEACIDS To generalize the alignment scoring model, we still award +1 for
matches, but we also penalize mismatches by some positive
The frivolous matches hiding the real evolutionary scenario have appeared because constant µ (the mismatch penalty) and indels by some positive
nothing stopped us from introducing an excessive number of indels when building
constant s (the indel penalty). As a result, the score of an
an LCS. Recalling our original alignment game in which we rewarded matched sym-

bols, we need some way of penalizing indels and mismatches. First, let's handle indels.
alignment is equal to
Say that inaddition to assigning matches a premium of +1, we assess each indel a
penalty top-scoring alignment of the A-domains gets closer to the biologically
of -4. The
correct alignment, with six of the columns corresponding to correctly aligned signatures.
#matches − μ · #mismatches − σ ·
YAFDLGYTCMFP-VLL-GGGELHIV-QKETYTAPDEI-AHYIKEHGITYI-KLTPSLFHTIVNTASFAFDANFE
-AFDVS-AGDFARALLTGG-QL-IVCPNEVKMDPASLYA-IIKKYDIT-IFEATPAL--VIPLME-YIYEQKLD
#indels
-S-LR-LIVLGGEKIIPIDVIAFRKM---YGHTE-FINHYGPTEATIGA
ISQLQILIV-GSDSC-SME--DFKTLVSRFGSTIRIVNSYGVTEACIDS
Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner.

Biologists have further refined this cost function to allow for the fact that some
Mismatches and Indel Penalties mutations may be more likely than others, which calls for mismatches and indel
penalties that differ depending on the specific symbols involved. We will extend the
k-letter alphabet to include the space symbol and then construct a (k + 1) ⇥ (k + 1)
#matches − 3 · #mismatches − 2 · #indels scoring matrix Score holding the score of aligning every pair of symbols. The scoring
matrix for comparing DNA sequences (k = 4) when all mismatches are penalized by µ
A T - G T T A T A and all indels are penalized by s is shown below.

A T C G T - C – C
+1+1-2+1+1-2-3-2-3=-7 A C G T −
A +1 −μ −μ −μ -σ
C −μ +1 −μ −μ -σ
G −μ −μ +1 −μ -σ
T −μ −μ –μ +1 -σ
− -σ -σ -σ -σ
Scoring matrix
Although scoring matrices for DNA sequence comparison are usually defined only
by the parameters µ and s, Scoring Matrices for Amino Acid Sequences
Y (Tyr) often mutates into F (score +7)
but rarely mutates into P (score -5)

A C G T − Prefer refer to Pages 285-287 of

A +1 −3 −5 −1 -3 reference book
C −4 +1 −3 −2 -3 BLOSUM62 and PAM50
G −9 −7 +1 −1 -3
T −3 −5 –8 +1 -4
− -4 -2 -2 -1
Even more general scoring matrix

-5 7
scoring matrices for protein sequence comparison weight
different mutations differently and become quite involved
Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner.

Dynamic Programming Recurrence for the Dynamic Programming Recurrence for the
Alignment Graph Alignment Graph
si-1, j - σ
si-1, j + weight of edge “↓” into (i,j)
si, j-1 - σ
si, j= max { si, j-1 + weight of edge “→” into (i,j) si, j= max { si-1, j-1 + 1, if vi=wj
si-1, j-1+ weight of edge “↘” into (i,j)
si-1, j-1 - μ, if vi≠wj

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 Dynamic Programming Recurrence for the Global Alignment
Alignment Graph
Global Alignment Problem: Find the highest-scoring
si-1, j + score(vi,-)
alignment between two strings by using a scoring matrix.
si, j= max { si, j-1 + score(-,wj)
si-1, j-1+ score(vi,wj) • Input: Strings v and w as well as a matrix score.

• Output: An alignment of v and w whose alignment

score (as defined by the scoring matrix score) is
maximal among all possible alignments of v and w.

Bioinformatics Algorithms: An Active Learning Approach.

Copyright 2018 Compeau and Pevzner.

Homeobox Genes
Which Alignment is Better?
• Two genes in different species
may be similar over short • Alignment 1: score = 22 (matches) - 20 (indels)=2.
conserved regions and dissimilar
over remaining regions. GCC-C-AGT--TATGT-CAGGGGGCACG--A-GCATGCAGA-
GCCGCC-GTCGT-T-TTCAG----CA-GTTATG--T-CAGAT
• Homeobox genes have a short
region called the homeodomain
that is highly conserved among • Alignment 2: score = 17 (matches) - 30 (indels)=-13.
species.
• A global alignment may not find the ---G----C-----C--CAGTTATGTCAGGGGGCACGAGCATGCAGA
homeodomain because it would try to GCCGCCGTCGTTTTCAGCAGTTATGTCAG-----A------T-----
align the entire sequence.

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 Which Alignment is Better? G
G C C G C C G T C G T T T T C A G C A G T T A T G T C A G A T

C
C

• Alignment 1: score = 22 (matches) - 20 (indels)=2. C

A −−−G−−−−C−−−−−C−− CAGTTATGTCAGGGGGCACGAGCATGCAGA
G GCCGCCGTCGTTTTCAG CAGTTATGTCAG−−−−−A−−−−−−T −−−−
T
Local alignment
T
A
GCC-C-AGT--TATGT-CAGGGGGCACG--A-GCATGCAGA- T
G
GCCGCC-GTCGT-T-TTCAG----CA-GTTATG--T-CAGAT T
C
A
G
G
G
G
G
• Alignment 2: score = 17 (matches) - 30 (indels)=-13. C
A
C
G
---G----C-----C--CAGTTATGTCAGGGGGCACGAGCATGCAGA A
G
GCCGCCGTCGTTTTCAGCAGTTATGTCAG-----A------T----- C
A
GCC−C−AGT−TATGT-CAGGGGGCACG−−A−GCATGCAGA
-
local alignment T
G
GCCGCC−GTCGT-T-TTCAG----CA−GTTATG−T−CAGA
T
C
A Global alignment
C
A

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

G
G C C G C C G T C G T T T T C A G C A G T T A T G T C A G A T
Local Alignment
C
C
C
A
G
T
T
A
T
G
T
C
A
G
G Global alignment
G
G
G
C
A
C
G
A
G
C
A
T
G
C
A
C
A

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
Local Alignment= Global Alignment in a Subrectangle Local Alignment Problem

Local Alignment Problem: Find the highest-scoring local

alignment between two strings.
Compute a Global
Alignment within • Input: Strings v and w as well as a matrix score.
Global alignment
each rectangle to
get a Local • Output: Substrings of v and w whose global alignment
Alignment (as defined by the matrix score), is maximal among all
global alignments of all substrings of v and w.

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

Free Ola Rides!

Local Alignment Problem G
G C C G C C G T C G T T T T C A G C A G T T A T G T C A G A T

Imagine a “free taxi ride” from the

C source (0, 0) to the node representing
C the start node of the conserved (red)
C
A interval, and a free taxi ride from the
G end node of the conserved interval to
The straightforward but inefficient way to solve the Local Alignment Problem is T
T
the sink.

to find the longest path connecting every pair of nodes in the alignment graph A
T Then you could reach the starting
(rather than just those connecting the source and sink, as in the Global G
T
node of the conserved interval for
free, instead of incurring heavy
Alignment Problem), and then to select the path having maximum weight over
C
A penalties as in global alignment -you
all these longest paths.
G
travel along the conserved interval to its
G
G end node, accumulating positive match
G scores and fewer penalties. Finally, you
Calculate the runtime of this approach? G
take another free ride from the end
C
A node of the conserved interval to the
C sink. The resulting score of this ride is
G
A equal to the alignment score of only the
G conserved intervals, as desired.
C
A
T Problem with the "free rides" idea is that
G we don’t know in advance where the
C local alignment starts and ends!
A
C
A
GCC−C−AGT−TATGT-CAGGGGGCACG−−A−GCATGCACA −−−G−−−−C−−−−−C−− CAGTTATGTCAGGGGGCACGAGCATGCACA
- GCCGCCGTCGTTTTCAG CAGTTATGTCAG−−−−−A−−−−−−T −−−−
GCCGCC−GTCGT-T-TTCAG----CA−GTTATG−T−CAGA Local alignment
T
Global alignment
What Do Free Ola Rides Mean in the Terms of the Alignment Graph? Building gedi route for the Local Alignment Problem

How many edges have we added?

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

Dynamic Programming for the Local Alignment Dynamic Programming for the Local Alignment
weight of edge from (0,0) to (i,j) 0
si-1, j + weight of edge “↓” into (i,j) si-1, j + weight of edge “↓” into (i,j)
si, j= max { si, j-1 + weight of edge “→” into (i,j) si, j= max { si, j-1 + weight of edge “→” into (i,j)
si-1, j-1+ weight of edge “↘” into (i,j) si-1, j-1+ weight of edge “↘” into (i,j)

Why no free rides from end of The recurrence above

local alignment to sink ? incorporates free Ola from
source = (0, 0), but it does not
incorporate free rides into sink
= (n, m). Since sink has every
other node as a predecessor,
sn, m will be equal to the largest
value of si, j over the entire
alignment graph,
 How Do We Compare Biological Sequences
• From Sequence Comparison to Biological Insights
• The Alignment Game and the Longest Common Subsequence
• The Chandigarh gedi route Problem
• The Change Problem
• Dynamic Programming and Backtracking Pointers
• From Chandigarh gedi route to the Alignment Graph
• From Global to Local Alignment
• Penalizing Insertions and Deletions in Sequence Alignment
• Multiple Sequence Alignment
Large insertions or deletions might result from a single event

In nature, a series of k indels often come as a single event rather than a

Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. series of k single nucleotide events

Scoring Gaps More Adequate Gap Penalties

• We previously assigned a fixed penalty σ to Affine gap penalty for a gap of length k: σ+ε·(k-1)
each indel.
• However, this fixed penalty may be too severe σ - the gap opening penalty
for a series of 100 consecutive indels. ε - the gap extension penalty
• A series of k indels often represents a single σ > ε, since starting a gap should be penalized
evolutionary event (gap) rather than k events: more than extending it.

two gaps GATCCAG GATCCAG a single gap

(lower score) GA-C-AG GA--CAG (higher score)

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
Modelling Affine Gap Penalties by Long Edges Building Gedi route with Affine Gap Penalties
σ+ε∙2

σ+ε σ+ε

We have just added O(n3) edges to the

Bioinformatics Algorithms: An Active Learning Approach. graph… Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

Building Gedi route on 3 levels How can we emulate

this path in the 3-level
Manhattan?

loweri-1,j - ε σ
upper level loweri,j = max {
middlei-1,j - σ 0
bottom level (deletions) σ upperi,j-1 - ε
(insertions) upperi,j = max {
middlei,j-1 - σ

middle level loweri,j

ε middlei,j = max { middlei-1,j-1 + score(vi,wj)
(matches/mismatches)
upperi,j

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 Percent Accepted Mutation
Scoring Matrices
(PAM or Dayhoff) Matrices
By Margaret Dayhoff in 1978
Amino acid substitutions were estimated using:
– Alignment of common protein sequences
Protein scoring matrices – PAM and BLOSUM – 1572 amino acid substitutions/changes in 71 groups of protein which are at least 85%
similar

Nucleic acid scoring matrices – Jukes Cantor and Kimura models

- Number of changes of each amino acid into every other amino acid was counted
- Relative mutability evaluated by counting the number of changes of each amino acid
divided by a normalization factor (this would normalize the data for variations in amino acid
composition, mutation rate, and sequence length)
- The amino acid exchange counts and mutability values were used to generate a 20 x 20
mutation probability matrix representing all possible amino acid changes.

“Because these changes are observed in closely related proteins, they represent amino
acid substitutions that do not significantly change the function of the protein. Hence they
are called "accepted mutations," defined as amino acid changes "accepted" by natural
selection.”

Percent Accepted Mutation

(PAM or Dayhoff) Matrices

PAM matrices converted to log-odds matrix

- Calculate odds ratio for each substitution
- Taking scores in previous matrix
- Divide by frequency of amino acid
- Convert ratio to log10 and multiply by 10
- Take average of log odds ratio for converting A to B and converting B to A
Since the changes are independent of previous mutational events,
the PAM1 matrix can be multiplied by itself N times to give the transition
matrices for sequences that have undergone N mutations.

• PAM1 is 1 mutation/ 100 Aa

• PAM10 is 10 mutations/100 Aa
• PAM250 is 250 /100 Aa & so on.

Greater numbers mean bigger evolutionary distance

 Percent Accepted Mutation Percent Accepted Mutation
(PAM or Dayhoff) Matrices (PAM or Dayhoff) Matrices
By Henikoff and Henikoff, 1992. BLOck SUbstitution Matrices To deal with overrepresentation of amino acid substitutions occurring in the most closely
- Derived from a database of local alignments of relatively distantly related protein related members of the family, a consensus sequence of the block is formed. Sequences
sequences. within blocks are clustered according to their level of identity. Sequences that were n%
- Looked at a large set of ~2000 amino acid patterns organized into blocks, which are identical to the consensus were grouped together to form the BLOSUM-n matrix;
conserved regions within protein families as identified by the protein database, Greater numbers mean smaller evolutionary distance.
PROSITE. Ex. sequences 62% identical were grouped together to form the BLOSUM-62 matrix
- Blocks were also signatures of a protein family, indicating that members of the family
could be found by searching for these blocks P (Observed AAi-AAj)
Log( P(Expected AAi-AAj)
)

Scoring Matrices for Amino acids Scoring Matrices for Nucleic acids
• PAM (Percent Accepted Mutation) / MDM (Mutation Data Matrix ) / Dayhoff Two mutation models:
– Derived from global alignments of closely related sequences. – Jukes-Cantor Model of evolution: alpha = common rate of base substitution
– Matrices for greater evolutionary distances are extrapolated from lesser ones.
– The number with the matrix (PAM40, PAM100) refers to the evolutionary distance; – Kimura Model of Evolution: alpha = rate of transitions; beta= rate of transversions
greater numbers are greater distances. • Transitions (No change in ring size Pyrimidine to Pyrimidine, Purine to Purine)
– PAM-1 corresponds to about 1 million years of evolution • Transversions (Change in ring size Purine to Pyrimidine)

• BLOSUM (Blocks Substitution Matrix)

– Derived from local, ungapped alignments of distantly related sequences
– All matrices are directly calculated; no extrapolations are used
– The number after the matrix (BLOSUM62) refers to the minimum percent identity of the
blocks used to construct the matrix; greater numbers are lesser distances.
– The BLOSUM series of matrices generally perform better than PAM matrices for local
similarity searches.
– For local alignment, Blosum 62 is often superior

When comparing closely related proteins one should use lower PAM or higher BLOSUM
matrices, For distantly related proteins higher PAM or lower BLOSUM matrices.
 Scoring Matrices for Nucleic acids Drawbacks of DP
Two mutation models: Guaranteed optimal alignment between 2 sequences
– Jukes-Cantor Model of evolution: alpha = common rate of base substitution
given a scoring scheme.
– Kimura Model of Evolution: alpha = rate of transitions; beta= rate of transversions
• Transitions (No change in ring size Pyrimidine to Pyrimidine, Purine to Purine)
• Transversions (Change in ring size Purine to Pyrimidine) 2 main drawbacks are
Rate of transitions > transversions compute - O(n2) and O(n3)
memory intensive - O(n2) space

Linear space algorithms have been used in order to deal

with one drawback to dynamic programming - concentrate
only on those areas of the matrix more likely to contain the
maximum alignment eg. Myers-Miller algorithm but it is
compute intensive

Application: Cystic Fibrosis (Extra) Approximately 1 in 25 Humans Carry a Faulty CF Gene

• Cystic fibrosis (CF): An often • In the early 1980s biologists

fatal disease which affects the hypothesized that CF is
respiratory system and caused by mutations in an
produces an abnormally large
amount of mucus.
unidentified gene.
– Mucus is a slimy material
that coats epithelial • When BOTH parent carry a
surfaces and is secreted faulty gene, there is a 25%
into fluids such as saliva. chance that their child will
have cystic fibrosis.

Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.
 Where Is the Cystic Fibrosis Gene? Where Is the Cystic Fibrosis Gene?
• In the late 1980s, biologists • In the late 1980s, biologists
narrowed the search for the CF gene narrowed the search for the CF gene
to a small region on chromosome 7. to a small region on chromosome 7.
• One of these genes was similar to • One of these genes was similar to
ATP binding proteins that act as ATP binding proteins that act as
transport channels responsible for Chromosome 7 transport channels responsible for
secretion. secretion.
• Hint: cystic fibrosis involves sweet • Hint: cystic fibrosis involves sweet
secretion with abnormally high secretion with abnormally high
sodium levels. sodium levels.

Searching all new sequences against sequence databases is

now the first order of business in genomics.
Adenosine Triphosphate (ATP) transports chemical energy within cells.
Bioinformatics Algorithms: An Active Learning Approach. Bioinformatics Algorithms: An Active Learning Approach.
Copyright 2018 Compeau and Pevzner. Copyright 2018 Compeau and Pevzner.

CFTR: Cystic Fibrosis Transmembrane Conductance Regulator What is the most prevalent genetically
inherited disease in India? (In course)
The CFTR protein controls the flow of
ions in and out of cells inside the lungs [Link]

[Link]
sicklecellanemia

[Link]

What gene is involved?

What kind of mutations lead to this disease?
What are the current ideas behind solving this disease?

Bioinformatics Algorithms: An Active Learning Approach.

Copyright 2018 Compeau and Pevzner.