Project 5: Global Sequence Alignment

---

Started: Tuesday 11/2; Due: Monday 11/15

Overview

This assignment is also taken from the projects on the book's web site. In this case, the assignment is the Global Sequence Alignment. Be sure to read my comments below for some clarification and suggestions.

You should work on this project individually.

Getting started

You should get started by reading through Global Sequence Alignment and work through one or two examples by hand. In other words, come up with some short DNA sequences and compute their edit distance using the table method illustrated in the write-up for the sequences AACAGTTACC and TAAGGTCA. You do not have to hand this in, and you may work with a partner on this part.

Required structure

Instead of giving you a template Java file to work from, we are going to have you create the code more or less from scratch. However, in order to enforce some uniformity (which will make the grading easier), we request that you do certain things:

• The name of the Java project should be "Project5".
• The name of the main class should be "EditDistance".
• You should create a "documents" folder in Project5 where you will put a readme.txt file described in the "What you must do/hand in" section below.
• You should create a "lib" folder in Project5, put stdlib.jar into it, and put stdlib.jar into the build path for the project.
• You should have a "resources" folder in Project5 (just like in Project 2) that contains the contents of the sequence directory described in the write-up at the book's web site.
• Your final program should function as described at the bottom of the book site's (you choose which of the two output styles), with the following slight difference: you would get the described output by typing java -cp bin:lib/stdlib.jar EditDistance < resources/example10.txt. However, I recommend developing and testing it by setting the strings X and Y directly in main, as I did in the LCS.java file I described in class. By the way, you will probably want use LCS.java as a model for your programming.

Required methods

The class EditDistance should correctly implement the following methods:

	/**
	 * @param X a non-null String
	 * @param Y a non-null String
	 * @return the the edit distance between X and Y
	 * 
	 * This procedure should use a recursive, not dynamic programming, approach
	 * to compute the edit distance
	 */
	private static int recursiveEditDistance(String X, String Y)
	
	
	
	/**
	 * @param X a non-null String
	 * @param Y a non-null String
	 * @return the the edit distance between X and Y
	 * 
	 * This procedure should dynamic programming to compute the edit distance
	 */
	private static int editDistance(String X, String Y)
	
	
	
	/**
	 * @param X a non-null String
	 * @param Y a non-null String
	 * 
	 * This procedure should use dynamic programming to compute the edit distance
	 * and print it and the alignments in one of the two formats given at the
	 * bottom of the book's web page describing this problem
	 */
	private static void printEditDistance(String X, String Y)
	
	
	
	/**
	 * @param X a non-null String
	 * @param Y a non-null String
	 * 
	 * Prints out the edit distance between X and Y and the time taken to compute it
	 * using the recursive version recursiveEditDistance
	 */
	public static void timeRecursiveEditDistance(String X, String Y)
	
	
	
	/**
	 * @param X a non-null String
	 * @param Y a non-null String
	 * 
	 * Prints out the edit distance between X and Y and the time taken to compute it
	 * using the dynamic programming version editDistance
	 */
	public static void timeEditDistance(String X, String Y)
	
	
	
	/**
	 * @param dnaLength a non-negative int
	 * @return a random String of length dnaLength comprised of the four chars A, T, G, and C
	 */
	public static String randomDNAString(int dnaLength)
						

What you must do/hand in

Your program contain at least the methods given above and should meet the specifications give in Global Sequence Alignment. You should also fill out the following readme.txt file ad include it in the documents folder.

Gradesheet

We will use this gradesheet when grading your lab.

Submission

Use the procedure described in our instructions on submitting code document.