Needleman Wunsch Algorithm

The purpose of this assigment is to have you implement the Needleman-Wunsch global pairwise sequence alignment algorithm (dynamic programming). See this video for a walk through of the algorithm implementation

Note: All modules you need have already been imported.

• Complete the NeedlemanWunsch.align method found in the align/align.py
  • Finish the method for filling in the alignment and gap matrices for Needleman-Wunsch.
• Complete the NeedlemanWunsch._backtrace method found in align/align.py
  • Use the heuristic you have chosen to implement in the the NeedlemanWunsch.align method to implement the backtracing procedure.
• Complete the main function in main.py to
  1. align all provided species BRD2 sequences to the human BRD2 sequence and print the species in order of most similar to least similar with respect to human BRD2.
  2. print the alignment scores corresponding to each species alignment to the human BRD2 sequence.

• Complete the test_nw_alignment function in test/test_align.py to test for proper matrix filling in your NeedlemanWunsch.align method.
• Complete the test_nw_backtrace function in test/test_align.py to test for proper backtracing in your NeedlemanWunsch._backtrace method.

Note: To check that you have correclty implemented your algorithm the following information is provided

• test_seq3.fa and test_seq4.fa should have an alignment score of 17 and an alignment of:

  MAVHQLIRRP

  M---QLIRHP

• Ensure that it runs pytest

• make .toml file with flit and ensure that your package can be installed with pip

To get started you will need to fork this repository onto your own Github account. Work on the codebase from your own repo and commit changes.

The following packages will be needed:

• numpy
• pytest

Make sure to push all your code to Github, ensure that your unit tests are correct, and submit a link to your Github through the Google classroom assignment.

• Pairwise global alignment works properly (6)
  • Correct implementation of Needleman-Wunsch algorithm (4)
  • Produces correct order of species in main.py (1)
  • Produces correct NW alignment scores in main.py (1)

• test_nw_alignment function properly checks that matrices are filled in correctly for alignment of test_seq1.fa and test_seq2.fa (1)
• test_nw_backtrace function properly checks that backtrace works correctly (1)
• Ensure functionality with pytest (1)

• Readable code with clear comments and method descriptions (1)

• Github actions/workflow (0.5)