# Demo entry 3627799

project 2

Submitted by anonymous on Feb 15, 2016 at 05:07
Language: Python 3. Code size: 2.1 kB.

```"""
project2.py - Use this file to enter your answers, and turn in a printout of this file.

UVA CS 1120
Spring 2016

Project 2 -- Genomes Galore!

My name:    [Evan Bagley]
My UVA ID:  [emb2mg]
"""

### You should not need to edit the next five lines:

import sys # for setrecursionlimit
import memoize
import apoe

sys.setrecursionlimit(25000)

###

AUTHOR = "emb2mg"   # Put your UVA ID here

# Problem 1

def nucleotide_complement(base):
original_nucleotide = ['A', 'T', 'G', 'C']
complement_nucleotide = ['T', 'A', 'C', 'G']
return complement_nucleotide[original_nucleotide.index(base)]

# Problem 2

def sequence_complement(sequence):
new_list = []
for e in sequence:
new_list = new_list + [nucleotide_complement(e)]
return new_list

# Example test:
#print (sequence_complement(['A','C','A','T']))
# ['T', 'G', 'T', 'A']

# Problem 3

def count_matches(sequence, base):
count = 0
for e in sequence:
if e == base:
count = count + 1
return count

# Example test:
#print (count_matches(['A','C','A','T'], 'A'))
# 2

#print (count_matches('ACAT' , 'A'))

# Problem 4

def hamming_distance(seq1, seq2):
elements_that_dont_match = 0
pos2 = 0
for a in seq1:
if a != seq2[pos2]:
elements_that_dont_match = elements_that_dont_match + 1
pos2 = pos2 + 1
return elements_that_dont_match

# Example test:
#print (hamming_distance(['A', 'C', 'A', 'T'], ['A', 'C', 'T', 'A']))
# 2
#print (hamming_distance("erode", "geode"))
# 2

# Problem 5

@memoize.memoize
def edit_distance(x, y):

if len(x) == 0 or len(y) == 0:
return max(len(x), len(y))

a = max(len(x), len(y))

if x == y:
x1 = x[1:len(x)]
y1 = y[1:len(y)]
a = edit_distance(x1, y1)

b = edit_distance(x[1:len(x)], y) + 1
c = edit_distance(x, y[1:len(y)]) + 1
d = edit_distance(x[1:len(x)], y[1:len(y)]) +1
return min(a, b, c, d)

# Problem 6