Genome 540 Homework Assignment 1

Due Saturday Jan. 13

Late homework policy is described on course web page.

1. 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).
2. Write a program that implements the method described in Lecture 1 to find the longest exactly matching subsequence between two sequences. 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 sequence name, with the sequence itself following on subsequent lines), each of which contains one of the sequences to be compared. As a data check, your program should count the number of bases of each type in each sequence. It should then use the described algorithm to find the longest subsequence present in both sequences. If there are several different perfectly repeated subsequences of the same length, find all of them. When you are looking for these, consider both strands of each sequence (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 subsequence happens to occur on different strands in the two sequences 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 + 4 (where the two input sequences have lengths N and M bases respectively) constructed by concatenating together the two sequences and their reverse complements (each terminated by a null character to terminate the strings, so that the lexicographic sort does not read across the sequence boundaries), and then create a single list of pointers to each position in this merged sequence, which you then sort.
3. Using this program, you should then find the longest exactly matching sequences in the second chromosome and megaplasmid of the bacterium Ralstonia eutropha strain JMP134 Once you find the longest match(es) using your program, you should then try to figure out what biological feature they correspond to. You can do this by exploring the organism page at TIGR's CMR web site.
4. To test whether your program is working correctly, run it first on the test example indicated below (with two different bacterial genomes) to see whether you get the right answer. 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). (To find the biological features, look 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. 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 Greg at gfinney@u.washington.edu. The indentation and line breaks below are for readability, and can be omitted. For instance, either of the following is okay: