Programming project 2

Programming project 2
Submission: ipython notebook with your code and result displayed. Part 1 A permutation 𝑝 of 𝑛 symbols is an ordered list of 𝑛 symbols (no repetitions). We call 𝑛 the length of the permutation. In the following, we use the symbols 𝑎,𝑏,𝑐,….. For example, 𝑝 = 𝑐𝑒𝑓𝑑𝑎𝑏 is a permutation of length 6 on the symbols 𝑎,𝑏,𝑐,𝑑,𝑒,𝑓. We denote by 𝑝[𝑖] the symbol of 𝑝 at position 𝑖, 𝑖 = 1,⋯,𝑛, and by 𝑝𝑜𝑠𝑝[𝑥] the position of symbol 𝑥 in 𝑝. If 𝑝 = 𝑐𝑑𝑎𝑏 is a permutation on 4 symbols we have 𝑝[3] = 𝑎 and 𝑝𝑜𝑠𝑝[𝑎] = 3. Given two permutations 𝑝 and 𝑞 of the same length n we want to compute their distance. Many definitions of distance between two permutations exist in the literature. In this project, we consider the following common definitions: Hamming distance, Kendall’s distance, Spearman distance. You have to write a Python program that takes two permutations from the standard input (use function input(), example code from example1.ipynb). The input permutations have length less than 26 and are on symbols of the English alphabet. It then: 1. checks that each input permutation is valid, i.e. there are no repeated symbols. If not the program stops. 2. checks that the permutations are on the same set of symbols. If not the program stops. 3. Computes and prints the above 3 distances between the input permutations: Hamming distance, Kendall’s distance, Spearman distance. Below are the definitions of the distances: Hamming distance: Given two permutations 𝑝 and 𝑞 of length 𝑛, it counts the number of positions at which 𝑝 and 𝑞 have a mismatch. Ex. 𝑝 = 𝑐𝑒𝑓𝑑𝑎𝑏 and 𝑞 = 𝑐𝑓𝑒𝑏𝑎𝑑 The Hamming distance of 𝑝 and 𝑞 is 4 since the two permutations differ in 4 positions; i.e. 2,3,4,5. What is the maximum value of the hamming distance between any two permutations as a function of n? No written answer is necessary, just think about it. Kendall’s distance: The Kendall’s tau distance KD counts the number of inversions occurring between two permutations, i.e. the number of pairs of symbols that appear in opposite order. Formally, 𝐾𝐷 = 𝑡ℎ𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑝𝑎𝑖𝑟𝑠 𝑜𝑓 𝑠𝑦𝑚𝑏𝑜𝑙𝑠 (𝑥,𝑦)such that (( 𝑝𝑜𝑠𝑝[𝑥] < 𝑝𝑜𝑠𝑝[𝑦] 𝑎𝑛𝑑 𝑝𝑜𝑠𝑞[𝑥] 𝑝𝑜𝑠𝑞[𝑦]) 𝑜𝑟 ( 𝑝𝑜𝑠𝑝 [𝑥] 𝑝𝑜𝑠𝑝[𝑦] 𝑎𝑛𝑑 𝑝𝑜𝑠𝑞[𝑥] < 𝑝𝑜𝑠𝑞[𝑦])).
Ex. 𝑝 = 𝑐𝑒𝑓𝑑𝑎𝑏 and 𝑞 = 𝑐𝑓𝑒𝑏𝑎𝑑 The distance is 4 since there are 4 inversions, precisely (e,f), (a,b), (b,d) (a,d) What is the maximum value of the Kendall distance between any two permutations as a function of n? No written answer is necessary, just think about it.
Implementation hint: (However, you can use any other way except, of course, functions in statistical packages) Represent permutation p by a precedence matrix P, that is a 𝑛 ×𝑛 matrix defined as follows: 𝑃[𝑥,𝑦] = 1 if symbol x precedes y, and 𝑃[𝑥,𝑦] = 0 otherwise. For example, the matrix P associated to 𝑝 = 𝑐𝑒𝑓𝑑𝑎𝑏 is
You can compute the Kendall distance between p and q as follows. Construct the two matrices P and Q as above and …. (you continue). Spearman distance: The Spearman distance or position-based distance is the sum of the absolute differences of the positions of the symbols, i.e
𝑆𝐹 = ∑ | 𝑝𝑜𝑠𝑝[𝑥]−𝑝𝑜𝑠𝑞[𝑥] 𝑥
|.
Ex. 𝑝 = 𝑐𝑒𝑓𝑑𝑎𝑏 and 𝑞 = 𝑐𝑓𝑒𝑏𝑎𝑑 The symbol a is at the same position 5 in both permutations and so is c. Thus, they contribute 0 to the above sum. The symbol b is at position 6 in p and 4 in q thus the absolute value of the difference in position is 2, and so on. In total, the Spearman distance of p and q is 6. What is the maximum value of the Spearman distance between any two permutations as a function of n? No written answer is necessary, just think about it. Problem 2. Given a set of t DNA strings of the same length n. The frequency of a base at position j is the number of times the base appears in position j in the set of DNA strings divided by the number t of DNA strings. Ex.
a b c d e f a 0 1 0 0 0 0 b 0 0 0 0 0 0 c 1 1 0 1 1 1 d 1 1 0 0 0 0 e 1 1 0 1 0 1 f 1 1 0 1 0 0
AAAGGTTTAA ATTTTCCCCC GGGGCCAAG ATTTTCAAAT ATTAACTCCT Here t=5 and n=10. The frequency of A at positions 0 to n-1= 9 are 4/5, 1/5, 1/5, 1/5, 1/5, 0, 1/5, 2/5, 3/5,1/5, respectively. The frequency of T at position 1 is 0, and so on. Let base A correspond to the integer 0, T to 1, G to 2, and C to 3. The frequency matrix is a 4× 𝑛 matrix M such that 𝑀[𝑖,𝑗] (i=0,⋯,3, j=0,⋯, n -1) is the frequency of base i in position j in the set of DNA strings. Note that the frequency is between 0 and 1. You have to write a program that takes as input the set of strings from the file “DNAsequences.txt”, computes and print the frequency matrix M. The program generates the following output (keep the fraction): Frequencies: A: 4/5, 1/5, 0, 1/5, 1/5, 0, 1/5, 2/5, 3/5,1/5 T: 0, … G: 1/5, … C: 0, …