Genome 540 Homework Assignment 1

Due Sunday Jan. 16

Policy on late homework: It will be accepted, but penalized.

1. Read The evolutionary origin of complex features. R.E. Lenski, C. Ofria, R.T. Pennock, and C. Adami. Nature 423 (2003) 139-145
2. Download and begin reading Initial sequencing and analysis of the human genome. The Genome International Sequencing Consortium. Nature 409, 860-921 (15 February 2001) . (To print this out, I would recommend the pdf format which corresponds exactly to the printed version, rather than the html format.) For next week, read
   • introduction and background (pp. 860-863, up to but not including "Strategic issues")
   • the section "Broad genomic landscape" (pp. 875-879, up to but not including "Repeat content of the human genome")
   • the section "Gene content of the human genome" (starting p. 892) up to but not including "comparative proteome analysis" (p. 901).
3. Write a program that implements the method described in Lecture 2 to find the longest exactly matching sequence between two genomes. Specifically, your program should read two input files in "FASTA" format (i.e. having a header line which starts with the character ">" and includes the organism name, with the sequence itself following on subsequent lines), each of which contains the complete sequence for one of the genomes. As a data check, your program should count the number of bases of each type in each genome. It should then use the described algorithm to find the longest subsequence present in both genomes. If there are several different perfectly repeated sequences of the same length, find all of them. When you are looking for these, consider both strands of each genome (i.e. both the sequence given in the FASTA file, which is sometimes called the 'forward' strand, and its reverse complement, which is sometimes called the 'reverse' strand) simultaneously, so that if the repeated sequence happens to occur on different strands in the two genomes you will still find it. The easiest way to do this is to create and store in memory a single sequence of length 2N + 2M (where the two input genome sequences have lengths N and M bases respectively) constructed by concatenating together the two genome sequences and their reverse complements, and then create a single list of pointers to each position in this merged sequence, which you then sort.
4. Using this program, you should then find the longest exactly matching sequences in the genomes of Pseudomonas aeruginosa (strain PA01) and Salmonella typhimurium (strain LT2), which are two very distantly related bacteria. You can find the FASTA files for these and other bacterial genomes by going to the NCBI web site and following appropriate links. (On the NCBI site, the FASTA files containing the full genome sequences have the suffix .fna). Once you find the longest matches using your program, you should then determine what biological feature they correspond to. Do this by looking in the 'Genbank format' files for the organisms (which have the suffix .gbk on the NCBI site) and find the annotated 'feature' in each genome that overlaps the matching segment you found. You don't need to write a program to do this -- just can just read the .gbk file on the web site.
5. To test whether your program is working correctly, run it first on the test example indicated below (with two different Mycoplasma species) to see whether you get the right answer.
6. 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. The indentation and line breaks below are for readability, and can be omitted. For instance, either of the following is okay: