Here we look at a problem from bioinformatics. You can think of a DNA sequence as a sequence of characters from {a,c,g,t}.Suppose you are given DNA sequence D₁ of n₁ characters and DNA sequence D₂ of n₂ characters. You want to know if these sequences appear to be related. An alignment is defined by inserting by inserting any number of spaces in D₁ and D₂ so that the resulting strings D₁ and D₂ both have the same length (with the spaces included as part of the sequence).Each character of D₁(including each space as a character)has a corresponding character(matching or non-matching) in the same position D_2.for a particular alignment A we say cost (A) is the number of mismatches (where you can think of a space as just another character and hence a space matches a space but does not match one of the other 4 character). As an example, let D₁ be ctatg and D₂ be ttaagc. One possible (not necessarily optimal)alignment is given by: ct at g tta agc In the above both D₁ and D₂ have length 8.The cost is 5.(there is a mismatches in the positions 1,3,5,6 and 8) Given a dynamic programming algorithm to find the cost of an optimal alignment for this problem and analyze its time complexity as a function of n₁ and n₂.Remember to (1)Describe a subproblem in natural language (2)Give a recursive solution to compute the values of the subproblems (3)argue that the optimal substructure property holds, and (4)describe how to fill in the table Then describe at a high level how to modify your algorithm to find an optimal alignment Hint: consider the relationship between this problem and the longest commom subset (LCS) problem.