MIT 6.00 Problem Set 3 - Problems 2-4 Answers

Black Checked Woodpecker, Costa Rica

Python Code Answer:

# MIT 6.00 Problem Set 3 - Problems 2-4

from string import *

def subStringMatchExact(target, key):
    index = 0
    starts = []

    if key == '':
        for i in range(0, len(target)):
            starts.append(i)

    else:        
        while True:
            index = find(target, key, index)
            if index == -1:
                break

            starts.append(index)
            index += len(key) 

    return tuple(starts)

target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'

key10 = 'q'
key11 = 'atg'
key12 = 'atgc'
key13 = 'atgca' 

print "\n----------Problem 2----------\n"

print subStringMatchExact(target1, key10)             
print subStringMatchExact(target1, key11)
print subStringMatchExact(target1, key12)
print subStringMatchExact(target1, key13)

print subStringMatchExact(target2, key10)
print subStringMatchExact(target2, key11)
print subStringMatchExact(target2, key12)                
print subStringMatchExact(target2, key13)


print "\n----------Problem 3----------\n"

target = 'atgacatgca'

key1 = 'a'
key2 = 'gc'

starts1 = subStringMatchExact(target, key1)
starts2 = subStringMatchExact(target, key2)

print "starts1: ", starts1
print "starts2: ", starts2

def constrainedMatchPair(substr1, substr2, length):
    valid = []

    for n in substr1:
        for k in substr2:
            if n + length + 1 == k:
                valid.append(n)

    return tuple(valid)
            

print constrainedMatchPair(starts1, starts2, len(key1))



### START MIT CODE ###

# Grimson, Guttag, 6.00 Introduction to Computer Science and Programming, 
# Fall 2008. (Massachusetts Institute of Technology: MIT OpenCouseWare), 
# http://ocw.mit.edu (Accessed July 13, 2011). 
# License: Creative Commons BY-NC-SA
# http://ocw.mit.edu/terms/#cc

def subStringMatchOneSub(key,target):
    """search for all locations of key in target, with one substitution"""
    allAnswers = ()
    for miss in range(0,len(key)):
        # miss picks location for missing element
        # key1 and key2 are substrings to match
        key1 = key[:miss]
        key2 = key[miss+1:]
        print '\nbreaking key',key,'into',key1,key2

        # match1 and match2 are tuples of locations of start of matches
        # for each substring in target
        match1 = subStringMatchExact(target,key1)
        match2 = subStringMatchExact(target,key2)

        # when we get here, we have two tuples of start points
        # need to filter pairs to decide which are correct
        filtered = constrainedMatchPair(match1,match2,len(key1))
        allAnswers = allAnswers + filtered
        print 'match1',match1
        print 'match2',match2
        print 'possible matches for',key1,key2,'start at',filtered
    return allAnswers

### END MIT CODE ###



subStringMatchOneSub('atgc','atgaatgcatggatgtaaatgcag')
print "\nTrial 2\n" 
print subStringMatchExact('atgctttgtgctttacgctttatactttatga', 'atgc')

subStringMatchOneSub('atgc','atgctttgtgctttacgctttatactttatga')

print "\n----------Problem 4----------\n"

def subStringMatchExactlyOneSub(target, key):
    matches = []
    exact = subStringMatchExact(target, key)
    oneSub = subStringMatchOneSub(key, target)
    for i in oneSub:
        for j in exact:
            if j == i:
                break
            else:                
                matches.append(i)

    return tuple(matches)


print subStringMatchExactlyOneSub('atgctttgtgctttacgctttatactttatga', 'atgc')

Output:

----------Problem 2----------

()
(0, 5, 15)
(5, 15)
(5, 15)
()
(0, 4, 8, 12, 18)
(4, 18)
(4, 18)

----------Problem 3----------

starts1:  (0, 3, 5, 9)
starts2:  (7,)
(5,)

breaking key atgc into  tgc
match1 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
, 21, 22, 23)
match2 (5, 19)
possible matches for  tgc start at (4, 18)

breaking key atgc into a gc
match1 (0, 3, 4, 8, 12, 16, 17, 18, 22)
match2 (6, 20)
possible matches for a gc start at (4, 18)

breaking key atgc into at c
match1 (0, 4, 8, 12, 18)
match2 (7, 21)
possible matches for at c start at (4, 18)

breaking key atgc into atg
match1 (0, 4, 8, 12, 18)
match2 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
, 21, 22, 23)
possible matches for atg  start at (0, 4, 8, 12, 18)

Trial 2

(0,)

breaking key atgc into  tgc
match1 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)
match2 (1, 8)
possible matches for  tgc start at (0, 7)

breaking key atgc into a gc
match1 (0, 14, 21, 23, 28, 31)
match2 (2, 9, 16)
possible matches for a gc start at (0, 14)

breaking key atgc into at c
match1 (0, 21, 28)
match2 (3, 10, 15, 17, 24)
possible matches for at c start at (0, 21)

breaking key atgc into atg
match1 (0, 28)
match2 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)
possible matches for atg  start at (0,)

----------Problem 4----------


breaking key atgc into  tgc
match1 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)
match2 (1, 8)
possible matches for  tgc start at (0, 7)

breaking key atgc into a gc
match1 (0, 14, 21, 23, 28, 31)
match2 (2, 9, 16)
possible matches for a gc start at (0, 14)

breaking key atgc into at c
match1 (0, 21, 28)
match2 (3, 10, 15, 17, 24)
possible matches for at c start at (0, 21)

breaking key atgc into atg
match1 (0, 28)
match2 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)
possible matches for atg  start at (0,)
(7, 14, 21)