CO4200: Aligning a suffix of X to a prefix of Y Report Writing - Mathematics Assignment Help

Assignment Task:

Task:

1. [25 marks] Aligning a suffix of X to a prefix of Y Assume we are given two protein sequences X of length n and Y of length m. In the solution to Worksheet 2, Question 2 we have developed the following algorithm for finding the best alignment of a suffix of X to a prefix of Y: F[0][0]=0 for i = 1..n: F[i][0]=0 for j = 1..m: F[0][j]=-j*d, P[0][j]=L for i = 1..n, j = 1..m: F[i][j] = max{ F[i-1][j-1]+s(X[i-1],Y[j-1]), F[i-1][j]-d, F[i][j-1]-d } P[i][j] = D, T or L according to which of the three expressions above is the maximum Start traceback at the largest value in the bottom row and stop traceback when column 0 is reached. Consider the inputs X=QRSWCHAW and Y=WHLAWT, and use the scoring model with substitution matrix BLOSUM50 and linear gap penalties with d=8.

(a) [15 marks] Give the matrices F and P that are computed by the algorithm above. You can indicate the entries of the matrix P by arrows drawn inside the matrix F. If there are different possible arrows in a position (because the maximum is not unique), draw all of them. Don't forget the arrows in the first row.

(b) [4 marks] Write down all the optimal alignments between a suffix of X and a prefix of Y, and give the optimal alignment score. (c) [2 marks] Explain how we can find the highest score of an alignment between a substring of X and the whole string Y in the matrix F that you have calculated in part (a). Write down an optimal alignment between a substring of X and the string Y. (d) [2 marks] Explain how we can find the highest score of an alignment between a suffix of X and the whole string Y in the matrix F that you have calculated in part (a). Write down an optimal alignment between a suffix of X and the string Y. (e) [2 marks] Explain how we can find the highest score of an alignment between a substring of X and a prefix of Y in the matrix F that you have calculated in part (a). Write down an optimal alignment between a substring of X and a prefix of Y. Marking criteria: Correct and clear answers will get full marks. Marks will be deducted for incorrect entries in the F matrix or in the traceback arrows. Partial marks will be given for correct parts or ideas.

2. [25 marks] Local alignment between X and Y, with prescribed exact matches at the start and end of the alignment We are given two protein sequences X of length n and Y of length m. As scoring model, we use a substitution matrix s and linear gap penalties with parameter d. We are looking for an alignment of highest score between any substring X' of X and any substring Y' of Y, among all local alignments that satisfy the following two properties:

1. The alignment of X' and Y' starts with an ungapped alignment of a substring RNC in X to a substring RNC in Y. \\

2. The alignment of X' and Y' ends with an ungapped alignment of a substring CQR in X to a substring CQR in Y. If no such alignment exists, the algorithm should detect this as well. For example, if X=TRNCWQCQRT and Y=SWTRNCQCQRST, then a local alignment that satisfies the two properties is: RNCWQCQR RNC-QCQR As another example, if X=TWRNCQR and Y=SRNCQRT, then the only local alignment that satisfies the two properties is: 16/02/2021 CO4200/CO7100/CO7200 Assignment 1 https://campus.cs.le.ac.uk/teaching/resources/CO7100/assignment1/tasks.html 2/3 RNCQR RNCQR Design an efficient algorithm to solve this problem optimally. If you use dynamic programming, it suffices to give the equations for computing the entries in the dynamic programming matrix (or matrices), and to specify where traceback starts and ends. Indicate why your algorithm is correct. What is the running-time of your algorithm? Marking criteria: Your algorithm will be marked based on correctness, clarity of presentation and efficiency (running-time). Partial marks will be given for correct parts or ideas.

3. [25 marks] Global alignment between X and Y, with a maximum number of identical matches We are given two protein sequences X of length n and Y of length m. We are looking for a highest-scoring global alignment of X and Y. If there are several highest-scoring global alignments, then we want to get one that has the largest number of columns in which a letter from X is aligned to an identical letter from Y. As scoring model, we use a substitution matrix s and linear gap penalties with parameter d. For example, if the two optimal alignments are (as in Worksheet 1, Question 4) RNQYYNQ-QNYNY and RNQYYN QQNYNY then the first alignment must be output, because it has two columns with identical matches, while the second alignment has only one such column. Design an efficient algorithm to solve this problem optimally. If you use dynamic programming as part of your solution, it suffices to give the equations for computing the entries in the dynamic programming matrix (or matrices), and to specify where traceback starts and ends. Justify at least briefly why your algorithm is correct. What is the running-time of your algorithm? Marking criteria: Your algorithm will be marked based on correctness, clarity of presentation and efficiency (running-time). Partial marks will be given for correct parts or ideas.

4. [25 marks] Markov Chains Consider the following Markov chain: At time 1, the Markov chain is in state B with probability 100%. The state of the Markov chain at time i is denoted by πi. Answer the following questions (and show your calculations, not only the final results): (a) [3 marks] What is the probability that the Markov chain is in state C at time 4? (b) [3 marks] What is the probability that the Markov chain is in state C at time 4 for the first time (i.e., it is never in state C before time 4)? (c) [5 marks] The Markov chain is in state C at time 4. What is the probability that the Markov chain was in state A at time 3? In other words, we want to calculate Pr[π3=A | π4=C]. (d) [10 marks] We are interested in an algorithm that can calculate, for any positive integer value n that we provide as input, which of the following two probabilities is higher: the probability that the Markov chain is in state A at time n the probability that the Markov chain is in state C at time n Describe an algorithm (in pseudo-code or natural language) that solves this problem in O(n) time.

e) [4 marks] For your algorithm from part (d), are there any potential issues with numerical instabilities for large values of n if you run the algorithm on a computer? If so, how could the algorithm be changed to alleviate these issues?

This CO4200: Mathematics Assignment has been solved by our Mathematics Experts at My Uni Paper. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK & US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics & referencing style.

Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.