03-511/711 Computational Genomics and Molecular Biology, Fall 2011 1Problem Set 0Due Tuesday, September 6thThis homework is intended to be a se lf-administered placement quiz, to help you (and me)determine if you have the background for the course. You may consult textbooks and publishedmaterials, but you may not discuss it with other human beings. Collaboration is not allowed onthis homework.In order to get full credit, show your intermediate work.1. Provide a short answer (1 - 3 sentences) to each of these questions:(a) Consider translation as an algorithm. Describe initiation and elongation using pseudo-code.(b) The tertiary structure of a protein is largely determined by hydrophilic and hydrophobicresidues. Explain how these residues influence the structure.(c) Consider a cell where the end of a gene is still being transcribed to an RNA intermediate,while the other end of the same RNA molecule is already being translated into an aminoacid sequence. What type of cell must this be? Explain.(d) Is it always true that one gene will produce one protein? Explain.03-511/711 Computational Genomics and Molecular Biology, Fall 2011 22. To solve this problem, you will need a table of the genetic code and the following table givingthe physico-chemical properties of the 20 amino acids:small hydrophobic polar basic acidicGly Val Phe Asn Asp LysAla Cys Tyr Gln Glu ArgSer Ile Met HisThr Leu TrpProConsider the following sequence of genomic DNA which is a template strand containing thebeginning of the open reading frame for a gene:3’ TAAACTGTACAGGGCCATAACT... 5’(a) Find the open reading frame and identify the start codon by circling it.(b) Transcribe the open reading frame into a strand of mRNA. Identify the start codon bycircling it.(c) What is the peptide encoded by this strand of m RNA?03-511/711 Computational Genomics and Molecular Biology, Fall 2011 3(d) Now, consider the 2nd translated codon from the mRNA strand. What is the probabilitythat a single base change in any position of this codon would change the identity of thesecond amino acid in the protein sequence?(e) What is the probability that a single base change in any position in the 2nd codon wouldresult in an amino acid in a different physico-chemical class? Use the table given above.03-511/711 Computational Genomics and Molecular Biology, Fall 2011 43. An X-linked recessive allele Xcproduces a red-green colorblindness in humans. A normalwoman whose father was colorblind marries a colorblind man. The allele for normal vision isdenoted as XN.(a) What genotypes are possible for the mother of the colorblind man?(b) What are the chances that the first child from this marriage will be a colorblind boy?(Assume a 50-50 sex ratio at birth.)(c) Of the girls produced by these parents, w hat proportion can be expected to be colorblind?(d) What proportion of the children (sex unspecified) of these parents can be expected tohave normal color vision?03-511/711 Computational Genomics and Molecular Biology, Fall 2011 54. You are an intern to a medical doctor in an area with a high incidence of a particular virus.One out of every 75 people has it. The doctor has developed a procedure to determine ifsomeone has the virus. You are in charge of tabulating the data from the trials of this test.If the patient has the virus, the test will correctly give a positive result 98% of the time.However, in healthy people, the test incorrectly predicts that the patient has the virus 7% ofthe time.The doctor has just performed the procedure on a new patient and the results s how that thepatient has the virus. Given what you know about the error rates of this test, determine theprobability that the patient actually has the virus. (Hint: Use Bayes Rule)03-511/711 Computational Genomics and Molecular Biology, Fall 2011 65. A clique is an undirected graph G = (V, E) in which every pair of vertices is connected by anedge. Suppose |V | = n.(a) Give the number of edges in G in terms of n.(b) What is the degree of each vertex, v?(c) Let Tbbe the spanning tree obtained from a breadth first search of G. Give the numberof edges in Tbin terms of n.(d) The diameter of a tree is defined to be maxu,v∈V{the shortest path from u to v}. Whatis the diameter of Tb?(e) Let Tdbe the spanning tree obtained from a depth first search of G . Give the numberof edges in Tdin terms of n.(f) What is the diameter of Td?03-511/711 Computational Genomics and Molecular Biology, Fall 2011 76. Let T be a rooted, 3-ary tree, in which every node has e ither zero or three children. Let L bethe number of leaves in T .(a) Give an expression for N , the number of internal nodes and leaves in T , in terms of L.(b) Give an expression for E, the number of edges in T , in terms of L.(c) What is the minimum depth of T in terms of L?(d) What is the maximum depth of T in terms of L?03-511/711 Computational Genomics and Molecular Biology, Fall 2011 87. Algorithms(a) X and Y have worst case running times no greater than 64N ·log2N and N3, respectively.Which algorithm has better asymptotic running time? For which values of N would youchoose algorithm X over algorithm Y ? (You may give an algebraic or graphical answer.)(b) Suppose you have just come up with algorithm Z which has a running time of 48N ·√N.For w hat values of N should you use algorithm Z over the other
View Full Document
Unlocking...