(Solved): Problem 2 (10 points). Background: You are given two DNA sequences, sequence1 with size n characters ...

Problem 2 (10 points). Background: You are given two DNA sequences, sequence1 with size n characters and sequence 2 with m characters. DNA sequences are composed of the characters 'A', ' C ', ' G ', and ' T '. Each DNA sequence may contain two consecutive please note :Allowed programming languages: Python. Use Python version ? 3.4. You can run “python –version” to check the version. Please do not use any built-in functions unless they are explicitly stated in the provided code. Do not use any third-party packages other than the standard library sequences: sequence 1= sequence 11+ sequence 12 and sequence 2= sequence 21+ sequence 22 . For example, sequence1='AGACTACCG', sequence1 may contain two consecutive se- quences sequence 11= "' and sequence 12= 'AGACTACCG', or sequence 1 may contain two sequences sequence 11= ' A ' and sequence 12= ' GACTACCG ', dots or sequence 1 may contain two sequences sequence 11= 'AGACTACCG' and sequence 12=^(') '. Your task is to find two sequences, sequence12 and sequence22, such that: (1) The length of the longest common subsequence (LCS) of sequence12 and sequence 22 is equal to the length of the LCS of sequence1 and sequence2. (2) The total number of characters in sequence12 and sequence22 is minimized. The output should be the length of the LCS and the total length of the two sequences, sequence12 and sequence22, that you have found. An O(nm)-time algorithm is suffice to pass any feasible test cases. Hint: use the dynamic programming algorithm for longest common subsequence prob- lem. (a) Input You need to read the input from the console. It contains two lines, each containing one sequence. In the first line of the input, we have n characters; and in the second line of the input, we have m characters. You can assume that 1<=n<= 10000 and 1<=m<=10000. (b) Output You need to output to the console. The first line is an integer indicating the length of the LCS between the given two sequences. The second line is the total length of the two sequences, sequence12 and sequence22. Below are example for input and output: - Allowed programming languages: Python. Use Python version \( \geq 3.4 \). You can run "python -version" to check the version. Please do not use any built-in functions unless they are explicitly stated in the provided code. Do not use any third-party packages other than the standard library.