USU CS 5050 Assignment 4

Created by Aaron Fine

A02224137

Assignment Description

1. Implement the basic Needlemann and Wunsch algorithm for aligning two different DNA sequences using the following scoring scheme

   	A	C	G	T	-
   A	5	-1	-2	-1	-3
   C	-1	5	-3	-2	-4
   G	-2	-3	5	-2	-2
   T	-1	-2	-2	5	-1
   -	-3	-4	-2	-1	*

2. Implement traceback routine to print out alignment vertically. Example:

   A = "ATAT"

   B = "TATA"

   A - _

   T - T

   A - A

   T - T

   _ - A

3. Determine how much space is taken up by the algorithm when both strings are the same size. Use this to estimate an upper bound on the string size.

4. Compute the distance between Human and Neandertal DNA sequences

5. Produce a table of distances between all pairwise distances between 10 different mitochondrial sequences

6. Produce a table of pairwise distances from the 6 great apes to the prototypical human sequence

7. Generate six text files each containing the alignments between the prototypical human and the 6 great ape sequences

8. Write a brief summary discussing your observations on the algorithm performance and the scientific impact of this efficient alignment algorithm

Code Details

The code for this assignment was written in Python 3 and has the following known dependencies

• Numpy
• Jupyer Lab
• MatPlotLib