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.
- To find the optimal TSP path I implemented a B&B Algorithm.
- As a lower bound for the B&B search I implemented Kruskal's MST algorithm.
I'm sure there are optimized libraries and better methods for DNA Genome assembly, but I wanted to implement everything from scratch to understand a possible way to approach an NP-hard problem.
This is my first complete Python project, so I'd love to get your feedback: especially I'm looking for performance bottlenecks in my implementation and better heuristics or relaxation techniques I could have used.
Check out the repo here: SCS Genome Assembler on GitHub
Top comments (0)