How I built a pure Python DNA Genome assembler using B&B

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