03-511/711 Computational Genomics and Molecular Biology, Fall 2002 1Problem Set 1Collaboration is allowed on this homework. You must hand in homeworks individually and list thenames of the people you worked with.You may not use a program to do this homework. Turn in your handwritten answers on theattached sheets. Extra alignment templates will be available on the website.Due in class on Tuesday, October 1st1. Alignment with affine gap penalties:(a) Compute the global alignment of “HIKER” with “MIMICKED”, using the followingscoring system: matches = 4, mismatches = -2, gaps = -4. Show your alignment matrixwith scores and traceback.(b) What is the score of the optimal alignment? How many different optimal alignments arethere? Show them.(c) Recompute the global alignment of “HIKER” with “MIMICKED” with an affine gapfunction with a gap opening penalty of -4 and a gap extension penalty of -1. Scorematches and mismatches as above. Show all three alignment matrices.(d) What is the score of the optimal alignment? How many different optimal alignments arethere? Show them.03-511/711 Computational Genomics and Molecular Biology, Fall 2002 22. Star alignment(a) Given, the sequences “BAG” “BRAIN” and “BARGAIN,” compute all pairwise align-ments, using the following distance function: mismatches = 1, gaps = 3.(b) For each sequence, compute the average distance to the other two. Which sequence isclosest to the others?03-511/711 Computational Genomics and Molecular Biology, Fall 2002 3(c) Select the sequence that is closest to the others as the “center”. Build multiple alignmentstarting with the lowest cost pairwise alignment. Merge the remaining sequence into thealignment using its pairwise alignment with the center sequence as a guide and followingthe “once a gap, always a gap” rule.Is the resulting alignment optimal? What is its total cost?(d) Compute the costs of the pairwise alignments induced by the heuristic multiple alignmentobtained above and compare them to the alignments obtained in (a).(e) Repeat (c) using the most distant sequence as the “center” and starting with the highestcost pairwise alignment. Do you get the same multiple alignment? What is its cost?03-511/711 Computational Genomics and Molecular Biology, Fall 2002 43. Aligning sequences and alignments. Align the sequence “BARGAIN” with the optimalpairwise alignment for the sequences “BAG” and “BRAIN” obtained in Problem 2(a). Showyour alignment matrix with scores and
View Full Document
Unlocking...