Recursion is a powerful technique that is widely used in addressing real world problems. Many real world problems can be solved using recursive algorithms that cut down computation significantly. The problem of finding the optimal alignment for two gene sequences is to find the alignment with the best alignment score. Note that it is allowed to insert gaps in either of the two gene sequences in the alignment. The alignment score is calculated based on the score at each position. See your lecture notes for more details regarding the alignment problem. (a). Suppose the two genes are as given as the following. Sequence 1: ACGT Sequence 2: ACGT List all possible alignments, as long as a gap is not aligned with a gap. In a valid alignment, a letter/symbol of one sequence can be aligned with a letter/symbol or a gap of the other sequence, but it is not allowed to have a gap in one sequence to align with a gap in the other sequence. How many possible alignments are there? (b). In general, let us suppose each of the two sequences has n letters. If the maximum number of gaps allowed to be inserted in each sequence is 2. How many possible alignments are there? Briefly explain. (c). Find the optimal alignment score and the corresponding alignment for two sequences using the recursive method of Needleman-Wunsch. Sequence 1: 1 TCACAGTAGGC Sequences 2: GCACTCGC Match score: 1 Mismatch score: 0 Gap score: -1 Your work needs to show the table and arrows marked in each cell of the table. Briefly explain how Needleman-Wunsch method works. Recursion is a powerful technique that is widely used in addressing real world problems. Many real world problems can be solved using recursive algorithms that cut down computation significantly. The problem of finding the optimal alignment for two gene sequences is to find the alignment with the best alignment score. Note that it is allowed to insert gaps in either of the two gene sequences in the alignment. The alignment score is calculated based on the score at each position. See your lecture notes for more details regarding the alignment problem. (a). Suppose the two genes are as given as the following. Sequence 1: ACGT Sequence 2: ACGT List all possible alignments, as long as a gap is not aligned with a gap. In a valid alignment, a letter/symbol of one sequence can be aligned with a letter/symbol or a gap of the other sequence, but it is not allowed to have a gap in one sequence to align with a gap in the other sequence. How many possible alignments are there? (b). In general, let us suppose each of the two sequences has n letters. If the maximum number of gaps allowed to be inserted in each sequence is 2. How many possible alignments are there? Briefly explain. (c). Find the optimal alignment score and the corresponding alignment for two sequences using the recursive method of Needleman-Wunsch. Sequence 1: 1 TCACAGTAGGC Sequences 2: GCACTCGC Match score: 1 Mismatch score: 0 Gap score: -1 Your work needs to show the table and arrows marked in each cell of the table. Briefly explain how Needleman-Wunsch method works