Computational Genomics and Molecular Biology, Fall 2010 1Problem Set 0 Due Aug. 31stThis homework is intended to be a self-administered placement quiz, to help you (and me)determine if you have the background required for the course. Collaboration is not allowed onthis homework.1. Below you see a hypothetical stretch of genomic DNA that contains a protein coding sequenceinterrupted by an intron, shown in lower case.CTAAG ATGGT GCTAA Ggu xxxxxxxxxxxxxxxxxxxxx agG CCTAG TTAAC TCAAT1 6 11 16 17 23 28(a) Assume that the first start codon you see as you scan from left to right is the beginningof the open reading frame. Draw a box around the start and stop codons of this openreading frame.(b) What is the peptide enco ded by this open reading frame? Note: All letters shown inlower case case are part of the intron, not just the x’s.(c) Write down all codons and their associated amino acids that can result from a singlebase-pair replacement i n the third codon.Computational Genomics and Molecular Biology, Fall 2010 2(d) What is the probability that a single base change in this codon results in a substitutionof the associated amino acid for a different amino acid?(e) What is the probability that a single base change in this codon leaves the amino acidunchanged?(f) Suppose that an “A” is inserted between positions 14 and 15. How will the sequence ofamino acids encoded by the gene be changed?Computational Genomics and Molecular Biology, Fall 2010 32. Short questions: (One or two sentences per q uestion.)(a) What properties do viruses have in common with living organisms? In what way areviruses different from living organisms?(b) What is the relationship between the number of genes and the numb er of differentproteins in a prokaryotic organism?(c) What is the relationship between the number of genes and the number of differentproteins in a eukaryotic organism? If your answer is different, what accounts for thedifference?Computational Genomics and Molecular Biology, Fall 2010 4(d) State two basic differences between chromosomal organization in typical prokaryotes andtypical multicellular eukaryotes.(e) State two basic differences between protein synthesis in prokaryotes and eukaryotes.(f) What is the ribosome and what is its role in the cell?(g) What is the difference between mRNA and tRNA?Computational Genomics and Molecular Biology, Fall 2010 53. The ability to taste the chemical phenylthiocarbamide (PTC) is an autosomal dominantphenotype. The inability to taste it is recessive. A taster woman with a non-taster fathermarries a taster man who in a previous marriage had a non-taster daughter. What is theprobability that(a) their first child will be a non-taster girl?(b) their second child will be a taster boy?(c) their first two children will be tasters of any sex?(d) if they have a family of five children, only two will be tasters?Computational Genomics and Molecular Biology, Fall 2010 64. For many years, the ability to taste PTC was believed to follow a straightforward pattern ofMendelian inheritance as described in the previous question. However, a recent associationstudy shows that the situation is more complex.A 2003 Science article by Kim et al. describes an genetic study that found a statisticalassociation between a mutation in the bitter taste receptor gene, TAS2R38, and the abilityto taste PTC. Kim and colleagues tested 190 tasters and 74 non-tasters for the presence ofthe mutation. They found the mutation in 170 of their subjects; of these 166 were tasters.Assuming that the study population is representative of the population at large, what is theprobability that a child will be a non-taster even if she inherits the mutation from her parent?Computational Genomics and Molecular Biology, Fall 2010 75. A clique is an undirected graph G = (V, E) in which every pair of vertices is connected by anedge.(a) How many edges are there in a clique with n nodes?(b) What is the maximum number of edges you can remove from a clique with n nodes andstill have a connected graph?(c) What is the number of edges in edges in the breadth-first spanning tree of a clique ofsize n?(d) What is the depth of this breadth-first spanning tree?(e) How many edges are there in the depth-first spanning tree of a clique of size n?(f) What is the depth of this depth-first spanning tree?Computational Genomics and Molecular Biology, Fall 2010 86. A complete k-ary tree is a tree in which every node has either zero or k children.(a) What is the minimum number of leaves in a rooted, complete 3-ary tree of depth d?(b) What is the minimum number of nodes in a rooted, complete 3-ary tree of depth d?(c) What is the maximum number of leaves in a rooted, complete 3-ary tree of depth d?(d) What is the maximum number of nodes in a rooted, complete 3-ary tree of depth d?Computational Genomics and Molecular Biology, Fall 2010 97. Suppose you have n bacteria and a single virus in a Petri dish. In the first generation, thevirus kills one bacterium and doubles in number. The remaining bacteria also double innumber, resulting in 2n − 2 bacteria and two viruses. In the next generation, each virus killsone bacterium and then reproduces itself, resulting in total of four viruses. The remainingbacteria divide, yielding 4n − 8 bacteria. This pattern is repeated in subsequent generations.(a) Let B(t) and V (t) be the number of bacteria and of viruses in the Petri dish at generationt. Write down recurrence relations giving B(t) and V (t) in terms of B(t−1) and V (t−1).(b) Solve your recurrence relation. Give expressions for B(t) and V (t) in terms of n and t.(c) How many generations will it take for the viruses to e radicate the bacteria? Give youranswer in terms of n.Computational Genomics and Molecular Biology, Fall 2010 108. (a) Order the following functions by growth rate (use “<” and “=”): N,√N, N2, N log N,N log(log N), N log(N2), N(log N)2, 2N, N3, 3N(b) Order the following assymptotic functions by growth rate (use “<” and “=”): O(N ),O(√N), O(N2), O(N log N ), O(N log(log N)), O(N log(N2)), O(N (log N)2), O(2N ),O(N3),
View Full Document
Unlocking...