Alignment Problem

Overview

In this repository, you will find the code for the assignments of the Advanced Algorithms and Parallel Programming course I took during my MSc in Computer Science and Engineering @ Politecnico di Milano, during the A.Y. 2023/2024.

Assignment 1

Let’s assume we have two sequences of strings composed by any sequence of the following four characters: 'A', 'C', 'G', and 'T'.

• Adenine (A)
• Cytosine (C)
• Guanine (G)
• Thymine (T)

You would like to align those two sequences by inserting gaps or admitting differences.

• Any time you have a gap, an '_' is inserted in one of the sequences. Any '_' adds a cost of 2 units to the final solution.
• Any time you allow a difference, replace the two characters with a '*'. Any '*' adds a cost of 5 units to the final solution (10 on both strings).

Given two strings, X = x₁ x₂ ... x_m, and Y = y₁ y₂ ... y_n, write the algorithm that outputs the minimum cost-aligned strings. The two aligned strings generated have to have the same length.

Bonus

Given two numbers n and m, generate two strings composed of ‘A’, ‘T’, ‘G’, and ‘C’ characters that produce the maximum cost in the alignment problem. The gap and the replacement costs have to be parametric.