Assignment 1

Write and document a Java program that implements the naive algorithm for building generalized suffix trees described in Section 6.4 of Gusfield (1997) and uses such trees to match patterns against a given set of DNA sequences. Each set of DNA sequences and patterns will be given in two files whose names will be read into your program as command-line arguments. The first line in the DNA sequence file will contain a number m giving the number of sequences in the files and the following m lines will contain the sequences, one per line, written in capital letters over the alphabet {A,C,T,G}. The first line of the pattern file will contain a number n giving the number of patterns in the file and the following n lines will contain the patterns, one per line. Your program should print the given DNA sequences and for each pattern, the pattern itself and all positions at which that pattern occurs in the given sequences (these positions must be sorted lexicographically by sequence-number and then pattern-position). You may assume that all sequences and patterns are less than 65 symbols long, a DNA sequence file contains at most 10 texts, no DNA sequence or pattern file is empty, and all files are formatted correctly.. Output for this program relative to the DNA sequence files DNAseq1.dat, DNAseq2.dat, and DNAseq3.dat and the pattern files DNApatt1.dat and DNApatt2.dat is given in script file out.PMGST.

Submission

Please hand in printed copies of your Java source code files. You must also submit these files electronically using the submit-assignment command. Note that each such file must have the following comment block at the top, where the X's are replaced with the appropriate information. For instance, my code for PMGST.java would begin with the following comment block:

/////////////////////////////////////////////////////////////////
//  CS 4762 (Winter 2005), Assignment #1                       //
//  Program File Name: PMGST.java                              //
//       Student Name: Todd Wareham                            //
//         Login Name: harold                                  //
//              MUN #: 8008765                                 //
/////////////////////////////////////////////////////////////////

You do not have to develop your code on our CS departmental systems. However, as your code will be compiled and tested on our CS departmental systems as part of the assignment marking process, you should ensure that your code compiles and runs correctly on at least one of these systems.

Additional Notes:

• Jan 15, 4:30pm
  Assignment #1 posted.

Created: November 25, 2004
Last Modified: January 25, 2004