Question

Questions 33 to 35 refer to the following Longest Common Subsequence problem. Given two sequences X-XI, X2,..., ...., X and Y y, y......... ya. Let C[ij]be the length of Longest Common Subsequence of x1, x2,..., Xi and y, y,..... Then Cij] can be recursively defined as following: CO if i=0 or j = 0 Cli,j][i-1.j-1]+1 ifi.j> 0 and x = y, max{C[i-1.7].[1.j-1); if i j>0 and x*y 0 The following is an incomplete table for sequence of AATGTT and AGCT. A AT GTT 0 0 0 0 0 0 0111111 1 1 1 2 2 2 с 0 1 1 1 T 0 1 1 2 A G 0 25 25 33. The value of C[3, 4] is [A] 1 [B] 2 [C] 3 [D] 4 [E] 5 34. The length of longest common subsequence of AATGTT and AGCT is [A] 1 [B] 2 [C] 3 [D] 4 [E] 5 35. The longest common subsequence of AATGTT and AGCT is [A] AGCT [B] ATGT [C] AATG [D] AGC [E] AGT 2.5

Answer 1

33 . [B] 2

c[3,4] = max[ c[2,4] , c[3,3] ] ; xi not equals to yj

now from table we can see that c[2,4] = 2 , c[3,3] = 1

Therefore ,

c[3,4] = max[ 2 , 1 ] = 2

Therefore value of c[3,4] is 2. Hence B is correct option.

34. [C] 3

AATGTT and AGCT

See C is not present in AATGTT . Now AGT is present . So it means AGT is longest common subsequence of AATGTT and AGCT.

Therefore length of AGT is 3.

35. [E] AGT

As it is clear from above explanation AGT is longest common subsequence.