Load my reference implementation and scoring matrices
import dp2
from blosum62 import blosum62
dna_ident = dp2.makeIdent("ATGC")
dna_ident
{'A': {'A': 1, 'C': -1, 'G': -1, 'T': -1},
'C': {'A': -1, 'C': 1, 'G': -1, 'T': -1},
'G': {'A': -1, 'C': -1, 'G': 1, 'T': -1},
'T': {'A': -1, 'C': -1, 'G': -1, 'T': 1}}
Example from Day 7 slides
example1 = ("AGCGGTA","GAGCGGA")
(nw1a,nw1s) = dp2.nw(*example1, s = dna_ident)
print "\n".join(nw1a)
print nw1s
-AGCGGTA GAGCGG-A 4
example1 = ("AGCGGTA","GAGCGGA")
(nw1a,nw1s) = dp2.nw(*example1, s = dna_ident, debug = True)
G A G C G G A
0 -1 -2 -3 -4 -5 -6 -7
-1 -1 0 -1 -2 -3 -4 -5 A
-2 0 -1 1 0 -1 -2 -3 G
-3 -1 -1 0 2 1 0 -1 C
-4 -2 -2 0 1 3 2 1 G
-5 -3 -3 -1 0 2 4 3 G
-6 -4 -4 -2 -1 1 3 3 T
-7 -5 -3 -3 -2 0 2 4 A
[None, [(0, 0)], [(0, 1)], [(0, 2)], [(0, 3)], [(0, 4)], [(0, 5)], [(0, 6)]]
[[(0, 0)], [(0, 0)], [(0, 1)], [(1, 2)], [(1, 3)], [(1, 4)], [(1, 5)], [(0, 6), (1, 6)]]
[[(1, 0)], [(1, 0)], [(2, 1), (1, 2)], [(1, 2)], [(2, 3)], [(1, 4), (2, 4)], [(1, 5), (2, 5)], [(2, 6)]]
[[(2, 0)], [(2, 1)], [(2, 1)], [(2, 3)], [(2, 3)], [(3, 4)], [(3, 5)], [(3, 6)]]
[[(3, 0)], [(3, 0), (3, 1)], [(3, 1), (3, 2)], [(3, 2)], [(3, 4)], [(3, 4)], [(3, 5), (4, 5)], [(4, 6)]]
[[(4, 0)], [(4, 0), (4, 1)], [(4, 1), (4, 2)], [(4, 2), (4, 3)], [(4, 4)], [(4, 4), (4, 5)], [(4, 5)], [(5, 6)]]
[[(5, 0)], [(5, 1)], [(5, 1), (5, 2)], [(5, 3)], [(5, 4)], [(5, 5)], [(5, 6)], [(5, 6)]]
[[(6, 0)], [(6, 1)], [(6, 1)], [(6, 3)], [(6, 4)], [(6, 5)], [(6, 6)], [(6, 6)]]
Jermyn's test case (fixed sequence embedded in random context)
example2 = ("GCTAGGATAGGCAATTGGCCTAGTG",
"ATAGTAATTGGCCTGCTTGAG")
(nw2a,nw2s) = dp2.nw(*example2, s = dna_ident)
print "\n".join(nw2a)
print nw2s
GCTAGGATAGGCAATTGGCCTAG--T--G ------ATA-GTAATTGGCCT-GCTTGAG 3
example2 = ("GCTAGGATAGGCAATTGGCCTAGTG",
"ATAGTAATTGGCCTGCTTGAG")
(nw2a,nw2s) = dp2.nw(*example2, s = dna_ident, debug = True)
A T A G T A A T T G G C C T G C T T G A G
0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -20 -21
-1 -1 -2 -3 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 G
-2 -2 -2 -3 -3 -3 -4 -5 -6 -7 -8 -9 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 C
-3 -3 -1 -2 -3 -2 -3 -4 -4 -5 -6 -7 -8 -9 -8 -9 -10 -11 -12 -13 -14 -15 T
-4 -2 -2 0 -1 -2 -1 -2 -3 -4 -5 -6 -7 -8 -9 -9 -10 -11 -12 -13 -12 -13 A
-5 -3 -3 -1 1 0 -1 -2 -3 -4 -3 -4 -5 -6 -7 -8 -9 -10 -11 -11 -12 -11 G
-6 -4 -4 -2 0 0 -1 -2 -3 -4 -3 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -11 G
-7 -5 -5 -3 -1 -1 1 0 -1 -2 -3 -3 -3 -4 -5 -6 -7 -8 -9 -10 -9 -10 A
-8 -6 -4 -4 -2 0 0 0 1 0 -1 -2 -3 -4 -3 -4 -5 -6 -7 -8 -9 -10 T
-9 -7 -5 -3 -3 -1 1 1 0 0 -1 -2 -3 -4 -4 -4 -5 -6 -7 -8 -7 -8 A
-10 -8 -6 -4 -2 -2 0 0 0 -1 1 0 -1 -2 -3 -3 -4 -5 -6 -6 -7 -6 G
-11 -9 -7 -5 -3 -3 -1 -1 -1 -1 0 2 1 0 -1 -2 -3 -4 -5 -5 -6 -6 G
-12 -10 -8 -6 -4 -4 -2 -2 -2 -2 -1 1 3 2 1 0 -1 -2 -3 -4 -5 -6 C
-13 -11 -9 -7 -5 -5 -3 -1 -2 -3 -2 0 2 2 1 0 -1 -2 -3 -4 -3 -4 A
-14 -12 -10 -8 -6 -6 -4 -2 -2 -3 -3 -1 1 1 1 0 -1 -2 -3 -4 -3 -4 A
-15 -13 -11 -9 -7 -5 -5 -3 -1 -1 -2 -2 0 0 2 1 0 0 -1 -2 -3 -4 T
-16 -14 -12 -10 -8 -6 -6 -4 -2 0 -1 -2 -1 -1 1 1 0 1 1 0 -1 -2 T
-17 -15 -13 -11 -9 -7 -7 -5 -3 -1 1 0 -1 -2 0 2 1 0 0 2 1 0 G
-18 -16 -14 -12 -10 -8 -8 -6 -4 -2 0 2 1 0 -1 1 1 0 -1 1 1 2 G
-19 -17 -15 -13 -11 -9 -9 -7 -5 -3 -1 1 3 2 1 0 2 1 0 0 0 1 C
-20 -18 -16 -14 -12 -10 -10 -8 -6 -4 -2 0 2 4 3 2 1 1 0 -1 -1 0 C
-21 -19 -17 -15 -13 -11 -11 -9 -7 -5 -3 -1 1 3 5 4 3 2 2 1 0 -1 T
-22 -20 -18 -16 -14 -12 -10 -10 -8 -6 -4 -2 0 2 4 4 3 2 1 1 2 1 A
-23 -21 -19 -17 -15 -13 -11 -11 -9 -7 -5 -3 -1 1 3 5 4 3 2 2 1 3 G
-24 -22 -20 -18 -16 -14 -12 -12 -10 -8 -6 -4 -2 0 2 4 4 5 4 3 2 2 T
-25 -23 -21 -19 -17 -15 -13 -13 -11 -9 -7 -5 -3 -1 1 3 3 4 4 5 4 3 G
[None, [(0, 0)], [(0, 1)], [(0, 2)], [(0, 3)], [(0, 4)], [(0, 5)], [(0, 6)], [(0, 7)], [(0, 8)], [(0, 9)], [(0, 10)], [(0, 11)], [(0, 12)], [(0, 13)], [(0, 14)], [(0, 15)], [(0, 16)], [(0, 17)], [(0, 18)], [(0, 19)], [(0, 20)]]
[[(0, 0)], [(0, 0)], [(0, 1), (1, 1)], [(0, 2), (1, 2)], [(0, 3)], [(1, 4)], [(1, 5)], [(1, 6)], [(1, 7)], [(1, 8)], [(0, 9), (1, 9)], [(0, 10), (1, 10)], [(1, 11)], [(1, 12)], [(1, 13)], [(0, 14), (1, 14)], [(1, 15)], [(1, 16)], [(1, 17)], [(0, 18), (1, 18)], [(1, 19)], [(0, 20), (1, 20)]]
[[(1, 0)], [(1, 0), (1, 1)], [(1, 1)], [(1, 2), (2, 2)], [(1, 4)], [(1, 4)], [(1, 5), (2, 5)], [(1, 6), (2, 6)], [(1, 7), (2, 7)], [(1, 8), (2, 8)], [(1, 9), (2, 9)], [(1, 10), (2, 10)], [(1, 11)], [(1, 12), (2, 12)], [(2, 13)], [(2, 14)], [(1, 15), (2, 15)], [(2, 16)], [(2, 17)], [(2, 18)], [(2, 19)], [(2, 20)]]
[[(2, 0)], [(2, 0), (2, 1)], [(2, 1)], [(3, 2)], [(3, 3)], [(2, 4)], [(3, 5)], [(3, 6)], [(2, 7)], [(2, 8), (3, 8)], [(3, 9)], [(3, 10)], [(3, 11)], [(2, 12), (3, 12)], [(2, 13)], [(3, 14)], [(3, 15)], [(2, 16), (3, 16)], [(2, 17), (3, 17)], [(3, 18)], [(3, 19)], [(3, 20)]]
[[(3, 0)], [(3, 0)], [(3, 2)], [(3, 2)], [(4, 3)], [(4, 4)], [(3, 5)], [(3, 6), (4, 6)], [(4, 7)], [(4, 8)], [(4, 9)], [(4, 10)], [(4, 11)], [(4, 12)], [(4, 13), (3, 14)], [(3, 14)], [(3, 15), (4, 15)], [(3, 16), (4, 16)], [(3, 17), (4, 17)], [(3, 18), (4, 18)], [(3, 19)], [(4, 20)]]
[[(4, 0)], [(4, 1)], [(4, 1), (4, 2)], [(4, 3)], [(4, 3)], [(5, 4)], [(5, 5)], [(4, 6), (5, 6)], [(4, 7), (5, 7)], [(4, 8), (5, 8)], [(4, 9)], [(4, 10), (5, 10)], [(5, 11)], [(5, 12)], [(5, 13)], [(4, 14), (5, 14)], [(5, 15)], [(5, 16)], [(5, 17)], [(4, 18)], [(5, 19)], [(4, 20)]]
[[(5, 0)], [(5, 1)], [(5, 1), (5, 2)], [(5, 3)], [(5, 3), (5, 4)], [(5, 4)], [(5, 5), (6, 5)], [(5, 6), (6, 6)], [(5, 7), (6, 7)], [(5, 8), (6, 8)], [(5, 9)], [(5, 10)], [(6, 11)], [(6, 12)], [(6, 13)], [(5, 14), (6, 14)], [(6, 15)], [(6, 16)], [(6, 17)], [(5, 18), (6, 18)], [(6, 19)], [(5, 20)]]
[[(6, 0)], [(6, 0), (6, 1)], [(6, 1), (6, 2)], [(6, 2), (6, 3)], [(6, 4)], [(6, 4), (6, 5)], [(6, 5)], [(6, 6), (7, 6)], [(7, 7)], [(7, 8)], [(7, 9)], [(6, 11)], [(6, 11)], [(6, 12), (7, 12)], [(6, 13), (7, 13)], [(6, 14), (7, 14)], [(6, 15), (7, 15)], [(6, 16), (7, 16)], [(6, 17), (7, 17)], [(6, 18), (7, 18)], [(6, 19)], [(7, 20)]]
[[(7, 0)], [(7, 1)], [(7, 1)], [(7, 3)], [(7, 4)], [(7, 4)], [(7, 6)], [(7, 6)], [(7, 7)], [(7, 8), (8, 8)], [(8, 9)], [(8, 10)], [(8, 11)], [(7, 12), (8, 12)], [(7, 13)], [(8, 14)], [(8, 15)], [(7, 16), (8, 16)], [(7, 17), (8, 17)], [(8, 18)], [(8, 19)], [(7, 20), (8, 20)]]
[[(8, 0)], [(8, 0), (8, 1)], [(8, 2)], [(8, 2)], [(8, 4)], [(8, 5)], [(8, 5)], [(8, 6)], [(9, 7), (8, 8)], [(8, 8)], [(8, 9), (9, 9)], [(8, 10), (9, 10)], [(8, 11), (9, 11)], [(8, 12), (9, 12)], [(8, 14)], [(8, 14)], [(8, 15), (9, 15)], [(8, 16), (9, 16)], [(8, 17), (9, 17)], [(8, 18), (9, 18)], [(8, 19)], [(9, 20)]]
[[(9, 0)], [(9, 1)], [(9, 2)], [(9, 3)], [(9, 3)], [(9, 5)], [(9, 6)], [(9, 6), (9, 7)], [(9, 7)], [(9, 8), (10, 8), (9, 9)], [(9, 9)], [(9, 10), (10, 10)], [(10, 11)], [(10, 12)], [(10, 13)], [(9, 14)], [(10, 15)], [(10, 16)], [(10, 17)], [(9, 18)], [(10, 19)], [(9, 20)]]
[[(10, 0)], [(10, 1)], [(10, 2)], [(10, 3)], [(10, 3), (10, 4)], [(10, 4), (10, 5)], [(10, 6)], [(10, 6), (10, 7)], [(10, 7), (10, 8)], [(10, 8)], [(10, 9), (10, 10)], [(10, 10)], [(11, 11)], [(11, 12)], [(11, 13)], [(10, 14), (11, 14)], [(11, 15)], [(11, 16)], [(11, 17)], [(10, 18)], [(11, 19)], [(10, 20)]]
[[(11, 0)], [(11, 1)], [(11, 2)], [(11, 3)], [(11, 4)], [(11, 4), (11, 5)], [(11, 6)], [(11, 6), (11, 7)], [(11, 7), (11, 8)], [(11, 8), (11, 9)], [(11, 10)], [(11, 11)], [(11, 11)], [(11, 12), (12, 12)], [(12, 13)], [(12, 14)], [(11, 15), (12, 15)], [(12, 16)], [(12, 17)], [(12, 18)], [(12, 19)], [(12, 20)]]
[[(12, 0)], [(12, 0), (12, 1)], [(12, 2)], [(12, 2), (12, 3)], [(12, 4)], [(12, 4), (12, 5)], [(12, 5), (12, 6)], [(12, 6)], [(13, 7)], [(12, 8), (13, 8), (12, 9)], [(12, 10)], [(12, 11)], [(12, 12)], [(12, 12)], [(12, 13), (13, 13)], [(12, 14), (13, 14)], [(12, 15), (13, 15)], [(12, 16), (13, 16)], [(12, 17), (13, 17)], [(12, 18), (13, 18)], [(12, 19)], [(13, 20)]]
[[(13, 0)], [(13, 0), (13, 1)], [(13, 2)], [(13, 2), (13, 3)], [(13, 4)], [(13, 4), (13, 5)], [(13, 5), (13, 6)], [(13, 6), (13, 7)], [(13, 7)], [(13, 8), (14, 8)], [(13, 10)], [(13, 11)], [(13, 12)], [(13, 12), (13, 13)], [(13, 13)], [(13, 14), (14, 14)], [(13, 15), (14, 15)], [(13, 16), (14, 16)], [(13, 17), (14, 17)], [(13, 18), (14, 18)], [(13, 19)], [(13, 20), (14, 20)]]
[[(14, 0)], [(14, 1)], [(14, 1), (14, 2)], [(14, 3)], [(14, 4)], [(14, 4)], [(14, 6)], [(14, 7)], [(14, 7)], [(14, 8)], [(15, 9)], [(14, 11)], [(14, 12)], [(14, 12), (14, 13)], [(14, 13)], [(15, 14)], [(15, 15)], [(14, 16)], [(14, 17), (15, 17)], [(15, 18)], [(15, 19)], [(14, 20), (15, 20)]]
[[(15, 0)], [(15, 1)], [(15, 1), (15, 2)], [(15, 3)], [(15, 4)], [(15, 4), (15, 5)], [(15, 5), (15, 6)], [(15, 7)], [(15, 7), (15, 8)], [(15, 8)], [(16, 9)], [(16, 10)], [(15, 12)], [(15, 12), (15, 13)], [(15, 13), (15, 14)], [(15, 14)], [(15, 15), (16, 15)], [(15, 16)], [(15, 17)], [(16, 18)], [(16, 19)], [(16, 20)]]
[[(16, 0)], [(16, 1)], [(16, 2)], [(16, 3)], [(16, 3), (16, 4)], [(16, 5)], [(16, 5), (16, 6)], [(16, 7)], [(16, 8)], [(16, 9)], [(16, 9)], [(16, 10), (17, 10)], [(17, 11)], [(16, 12), (17, 12), (16, 13)], [(16, 14)], [(16, 14)], [(17, 15)], [(17, 16), (16, 17)], [(16, 17), (16, 18)], [(16, 18)], [(17, 19)], [(16, 20), (17, 20)]]
[[(17, 0)], [(17, 1)], [(17, 2)], [(17, 3)], [(17, 3), (17, 4)], [(17, 5)], [(17, 5), (17, 6)], [(17, 7)], [(17, 8)], [(17, 9)], [(17, 9), (17, 10)], [(17, 10)], [(18, 11)], [(18, 12)], [(18, 13), (17, 14)], [(17, 14), (17, 15)], [(17, 15)], [(17, 16), (18, 16)], [(17, 17), (18, 17), (17, 18)], [(17, 18), (17, 19)], [(17, 19)], [(17, 20)]]
[[(18, 0)], [(18, 1)], [(18, 2)], [(18, 3)], [(18, 4)], [(18, 5)], [(18, 5), (18, 6)], [(18, 7)], [(18, 8)], [(18, 9)], [(18, 10)], [(18, 11)], [(18, 11)], [(18, 12), (19, 12)], [(19, 13)], [(19, 14), (18, 15)], [(18, 15)], [(19, 16)], [(19, 17)], [(18, 19)], [(18, 19), (18, 20)], [(18, 21)]]
[[(19, 0)], [(19, 1)], [(19, 2)], [(19, 3)], [(19, 4)], [(19, 5)], [(19, 5), (19, 6)], [(19, 7)], [(19, 8)], [(19, 9)], [(19, 10)], [(19, 11)], [(19, 11), (19, 12)], [(19, 12)], [(20, 13)], [(20, 14)], [(19, 15), (20, 15), (19, 16)], [(19, 16)], [(19, 17), (20, 17)], [(19, 18), (20, 18), (19, 19)], [(19, 19), (19, 20)], [(19, 21)]]
[[(20, 0)], [(20, 1)], [(20, 1), (20, 2)], [(20, 3)], [(20, 4)], [(20, 4), (20, 5)], [(20, 5), (20, 6)], [(20, 7)], [(20, 7), (20, 8)], [(20, 8), (20, 9)], [(20, 10)], [(20, 11)], [(20, 12)], [(20, 13)], [(20, 13)], [(21, 14)], [(21, 15)], [(20, 16), (21, 16)], [(20, 17)], [(21, 18)], [(21, 19)], [(21, 20), (20, 21)]]
[[(21, 0)], [(21, 0), (21, 1)], [(21, 2)], [(21, 2), (21, 3)], [(21, 4)], [(21, 5)], [(21, 5)], [(21, 6), (21, 7)], [(21, 8)], [(21, 9)], [(21, 10)], [(21, 11)], [(21, 12)], [(21, 13)], [(21, 14)], [(21, 14)], [(21, 15), (22, 15)], [(21, 16), (22, 16)], [(21, 17), (22, 17), (21, 18)], [(21, 18)], [(21, 19)], [(22, 20)]]
[[(22, 0)], [(22, 1)], [(22, 2)], [(22, 3)], [(22, 3), (22, 4)], [(22, 5)], [(22, 6)], [(22, 6), (22, 7)], [(22, 8)], [(22, 9)], [(22, 9), (22, 10)], [(22, 10), (22, 11)], [(22, 12)], [(22, 13)], [(22, 14)], [(22, 14)], [(23, 15)], [(23, 16)], [(23, 17)], [(22, 18)], [(23, 19), (22, 20)], [(22, 20)]]
[[(23, 0)], [(23, 1)], [(23, 1), (23, 2)], [(23, 3)], [(23, 4)], [(23, 4), (23, 5)], [(23, 6)], [(23, 6), (23, 7)], [(23, 7), (23, 8)], [(23, 8), (23, 9)], [(23, 10)], [(23, 11)], [(23, 12)], [(23, 13)], [(23, 13), (23, 14)], [(23, 15)], [(23, 15)], [(23, 16)], [(23, 17), (24, 17)], [(24, 18)], [(24, 19)], [(23, 21)]]
[[(24, 0)], [(24, 1)], [(24, 2)], [(24, 3)], [(24, 3), (24, 4)], [(24, 5)], [(24, 6)], [(24, 6), (24, 7)], [(24, 8)], [(24, 9)], [(24, 9), (24, 10)], [(24, 10), (24, 11)], [(24, 12)], [(24, 13)], [(24, 14)], [(24, 14), (24, 15)], [(24, 15), (24, 16)], [(24, 17)], [(24, 17)], [(24, 18)], [(25, 19)], [(24, 20), (25, 20)]]