My attempt at solving the Shortest Common Superstring problem using graph theory and no additional libraries.
Overview
Assembling DNA Genome is a problem that consists in finding a superstring that includes millions of single DNA reads. The issue? The problem is NP-hard!
To tackle my first advanced Python project I decided to build everything from scratch:
I modeled the overlap between single DNA reads as a directed graph and by introducing a dummy node the Shortest Common Superstring becomes the much more famous Asymmetric TSP problem.
