Genome 540 Homework Assignment 2

Due Sunday Jan. 23

1. Write a program that
   • reads in the FASTA file of coding sequences for an organism (on the NCBI web site this file has the suffix .ffn, and you should be able to find it in the same place that you found the .fna file having the complete genome sequence);
   • computes a "codon usage table" that counts the total number of times each codon is used (in-frame) in all of the coding sequences (ignoring codons that contain ambiguous nucleotides -- N,R,Y, etc.); and
   • prints out (in the format described below)
     • the name of the FASTA file
     • the first line of the FASTA file
     • the number of sequences, and total number of codons, in the FASTA file
     • the number of times each codon is used
2. Write a program to find a list of non-overlapping predicted coding sequences in the organism. Specifically, this should
   • identify all ORFs (open reading frames) that start with the codon ATG, GTG, CTG, or TTG, end with a stop codon in the same reading frame (with no intervening in-frame stop codons), and have length at least 100 codons; be sure to do this for both strands of the genome sequence (i.e. the strand given in the .fna file, and its reverse complement); codons that contain ambiguous nucleotides should be counted when determining the length, but should not be eligible to be stop or start codons
   • prune this list of ORFs to eliminate overlapping sequences (removing the shorter one of an overlapping pair), by using the following procedure: first sort the list of ORFs by decreasing size (ORFs of the same size should be ordered by where they appear in the sequence, in forward-strand coordinates -- with ORFs nearest the beginning of the sequence appearing first); then work through the list one at a time (starting with the largest ORF), accepting an ORF if it does not overlap any previously accepted ORF, otherwise rejecting it (be sure to reject ORFs that overlap longer ORFs on the opposite strand as well as the same strand);
   • write out (in the format described below) the translation start and stop positions, in forward-strand co-ordinates, and the strand, of each accepted ORF;
   • write a FASTA file containing all the accepted ORFs.
3. Run the program you wrote in #1 above on the FASTA file you generated in #2, so as to generate codon counts for the ORFs you found.
4. For the homework assignment, you should run your programs on Salmonella typhimurium (strain LT2) (one of the organisms used in the first assignment). To test whether your program is working correctly, run it first on the test example Pseudomonas aeruginosa (strain PA01) to see whether you get the right answer.
5. You must turn in your results and your computer program, using the template (file format) described below. Please put everything into ONE file - do not send an archive of files or a tar file. After creating a plain text file (NOT a word processing document file) in this format, compress it (using either Unix compress, or gzip -- if you don't have access to either of these programs let us know), and send it as an attachment to both Phil at phg@u.washington.edu, and Tobias at mann@gs.washington.edu.