Reference no: EM132475906

Problem 1 - Pairwise Alignment: Aligning X to a substring of Y

Your task is to implement an algorithm for pairwise alignment that computes, for two given protein sequences X and Y, a highest-scoring alignment between X and any substring of Y. The scoring model is given by a substitution matrix s (we use the BLOSUM50 matrix) and linear gap penalties with parameter d (we use d=8). You can use the implementation of the Needleman-Wunsch algorithm provided below as a starting point for your implementation. Your specific tasks are:

Q1: Implement an algorithm that computes an alignment of highest score among all alignments between X and any substring of Y, using the substitution matrix BLOSUM50 and linear gap penalties with parameter d.

Q2: Modify the program so that, in addition to a highest-scoring alignment between X and any substring of Y, it outputs the number of different such alignments. The program should output "There are x optimal alignments." where x is the number of different optimal alignments between X and a substring of Y.

Problem 2: Sorting by Reversals - Unsigned Model

Implement an algorithm for Sorting by Reversals (in the unsigned model of unichromosomal genomes) in a Java program. (If you want to use another programming language, please discuss it with the module convenor.) For any given permutation p of the numbers from 1 to n (where n is an arbitrary positive integer), the program should find a sequence of reversals that sorts p. You can use ideas from the algorithms discussed in the lectures (the greedy algorithm, the 4-approximation algorithm, or the 2-approximation algorithm) or design your own method. Your solution will be mainly marked based on the quality of the solutions produced (i.e. how many reversals does your program need to sort a given permutation), but also based on the general quality of your implementation (e.g. does your program work correctly in all cases, is the time that your program needs to find the solution appropriate for the quality of the solution, and is your implementation well structured and is your code clear and easy to read).

If you implement two or more algorithms, you can submit all of them (and you will receive at least the marks that the best of your algorithms would receive by itself).

Your program should output the original permutation as well as the permutation obtained after each individual reversal step. (This means that if your algorithm uses k steps to sort the permutation, it will output k+1 permutations: the initial permutation, and a further permutation after each of the k steps.) A permutation should be output in a single line, with genes separated by spaces. At the end, the algorithm should output "Finished after x reversals.", where x is to be replaced by the number of reversals used.

Attachment:- bioinformatics Assignment.rar